23605 1
71446072 805295056 273181976 250071397 736542935 13673913 450063916 92520146 481887400 118338085 889648107 523918873 152513094 989754606 50450487 645126829 413122874 498579719 643078581 887861245 108604447 906051897 371797956 460843888 657220121 289337319 525274328 959725427 573951984 322483161 351373189 714514089 666058176 183056905 452818572 296154355 262702940 276843953 463411674 973011717 293535651 950972647 686588777 764477852 317242298 911087479 751718840 988117666 721086172 355994518 933173938 522837966 433934907 815506990 804346520 473294873 81050702 693604803 849167979 13247040 189002070 866932042 837996829 426865037 910106029 638026198 691683383 892328949 242957255 962095595 26468908 393614410 158929302 458323924 346561859 771809988 741409370 967465354 308288538 204401203 34659025 255137369 276953764 906419073 404156655 97197586 873376061 297609013 892031499 993253814 553386788 488304239 563563757 830907283 594734984 771024993 838837860 741980799 285976060 622383332 434640163 782317593 780956867 982588185 531276057 947114077 341687538 643544749 138432437 622632356 921317084 159187515 90844673 74805529 718251231 885996673 182059960 677717609 420234300 467098967 779995125 263705163 147121785 331336741 172572375 422876077 915578969 109795831 329018003 867667155 478952731 601582461 58285147 362905940 358606848 432705170 509197699 970171098 417860413 784327037 32095995 923182247 69241145 327969161 574290974 522776661 182131560 830785744 675014016 656097832 37566952 227056830 270289916 837029758 49004448 490388675 532683941 289056521 651370902 250188119 621258045 385559580 475961658 100228502 89195608 754309867 988718195 645636561 254032244 311073756 867597641 413498876 639836368 650077273 963694870 226687130 319386725 380456084 192371427 267526562 377618067 900794221 863544458 477499205 471912568 87249815 883541851 356132021 355923749 251632994 55063253 609266621 800011005 253108270 748635723 505250514 356383592 14050338 61235816 312711328 619246936 840865765 599745823 283525498 972975912 232111179 384938291 364425387 722498774 691446400 247007316 804193117 347123117 423071670 107550315 290199175 388933585 411752358 995945106 884459536 294542725 522987252 297290420 686793705 444431892 585849491 605484570 730181209 198908465 989295227 970885765 163562527 890374466 295806630 689641087 145794565 919672692 214973077 663899072 54582540 934322555 6635961 466073923 187880374 808179486 729663420 654151217 555661203 561719154 886414692 282237494 521871729 692197396 793156254 593965796 316723720 802765876 764044033 397062231 109069711 881689121 884180415 874372639 679796003 959630717 908925432 464117343 398217257 595426851 805998110 592896000 607537355 687482422 518427579 430328202 664398315 187064129 757519262 839302056 107589157 987273111 687449127 928472749 139587863 502438958 505798384 254590287 564730969 774785607 906406240 484250374 833736341 539253835 855940539 436019463 598819145 139766197 103158190 808234691 873741102 757737022 9694962 47639957 222863274 758772724 665558576 149719641 626275019 326241340 383649636 541998652 49577056 971348236 940829799 775737172 666334544 372803970 724643876 441140402 181994380 992695900 202163198 582847185 384032636 799703920 547703652 275400836 797712683 256182890 156964541 829750399 975258051 906436860 338573462 305273398 799157840 628826484 689130747 169148073 935741205 312521022 421220961 150713546 43781327 904585269 721614903 590934799 661953651 201792212 139491218 735339429 586355798 569937772 953287293 759765428 981815399 698930957 632664981 377020679 15730080 514930743 473973014 501842729 819313869 808982370 126748013 22036844 788648857 134604710 333078307 730328588 935849134 389192314 776752914 71536476 6325327 211502904 816952919 317211141 524480821 167198499 162071322 167175919 263776518 132461231 427096930 989647146 659257630 532416657 247435546 158819128 279519004 948436558 943057141 277893458 582585422 510099628 648311450 30387263 523926788 426406720 713449698 990414480 888494656 958859765 278374708 978691078 438035347 372583703 485900131 75679936 907288975 317293372 368377904 372772327 927268732 196883886 691584860 979835402 291751842 276184862 743388015 766726096 128390268 900720102 662304701 409657057 889992414 731766471 67074207 983126257 700925328 794786163 416274243 492765269 511051701 531830818 315467023 439747664 962243452 27784616 749989032 760684936 187301956 815372124 287746127 377385224 669921972 972822555 764598274 17999862 289388514 694854613 484144211 20125459 605541991 399126128 968160800 357557594 448248852 661855602 989129573 684117801 192168588 939977228 393371622 274633784 24875740 316666625 893533221 624008996 610331458 520479809 476717376 974113368 329033268 232577423 786382264 64029812 764858025 263744940 78363469 129514120 41332832 668063596 632881315 941113318 814120925 502010014 428993831 895565270 670225687 829055773 775239435 110810581 570361697 868851180 231217060 10666424 914731026 649574583 839100749 280324245 243405395 29439365 224364933 523865031 995127729 961650041 714579073 707835864 895711253 11452738 205740902 775265253 780294156 355830754 259452994 674459175 326225702 663289014 368107161 370627730 941313515 517496971 271435812 62406071 419951782 151633265 272104854 963161318 250281527 150396735 238168019 204738494 159631099 943065457 941107085 924794400 796216567 180402377 27260910 128178827 588048819 563888957 25389317 394004526 465103921 34029782 487344993 749844146 791188393 779721738 642302969 287185098 816712976 149306962 997564194 224496836 267765571 652883645 338355307 928022575 295851743 170099181 328753708 543006799 946815652 746564208 246582659 894840892 206389575 51737978 488055489 382097432 991005593 47600811 390565289 264308680 139707553 290394317 687721405 882321437 320263660 952962680 874727788 275206081 144739996 121406444 623131486 222727713 111952451 67962559 839955031 613304839 143003505 378225289 319444833 297461297 523427437 187498040 314461975 984115755 232918581 839453531 494255228 236808773 859088099 287943927 34897778 915041218 275282319 465545418 881906045 893472398 833883429 376359110 368767925 112510779 544206679 24249012 808708813 715586659 946194480 47150649 91078349 469385908 189551505 760854751 732465280 321207752 940288930 660934867 275463890 737807499 585359909 620528593 906478526 933604107 893367505 534618480 685005504 623855921 278669329 377780615 61183739 278358229 439929131 457688934 623796577 559463205 557688419 346504018 871715683 108584873 631066400 408285049 342636384 598293205 613473768 583062180 985437313 527660777 94794649 162062881 112865195 985355703 91217750 914456813 717923238 151252495 256309076 239260944 45393948 249184086 40603019 193473337 545466062 56954416 76591810 64214684 99553907 810747405 442736677 422758433 386787692 176219746 174584254 712969556 258999374 534710196 92429003 676562397 662285518 968070045 628460104 707332743 169567043 230034906 483536641 394935650 512767418 94386872 839708405 800259366 712546282 34999806 933972731 708052645 577029478 146211836 485278958 842490916 799325827 463170116 971042759 587247115 905490891 204612221 67573275 106030892 299250062 469923645 617059868 211733910 89229646 978799340 162218295 628557384 281428235 446157676 836170780 98706229 217751860 886848794 387385135 750463432 347402132 678513935 735153507 746091848 75711657 822415927 385820507 737676735 708980853 178792308 481180933 559910091 622452266 600715435 216254527 760402713 833930068 521434953 462473381 947432353 860341276 646007408 350628498 283622391 77803601 326168747 947024155 455434865 835659812 913547960 494262728 827219385 572314965 578550973 910007294 768610861 509919059 383445506 499178309 499241782 728208457 4267789 138184312 663582081 295292288 667844140 90586578 968032311 699733051 754508676 758872383 565197878 43015562 441473893 115658762 797210318 477971750 57002074 886247465 271499284 37108394 263570812 63910497 651648004 881810746 519799031 340614819 499765668 262128021 558989489 898038786 822982224 912655091 615028581 749305066 316562904 617391324 355448791 580034750 508619699 823973529 421433558 163917923 885288994 88215254 945016372 214536027 808778966 857545342 146281086 804302939 130625626 806161926 731807442 117594714 181129263 26568975 91393849 348657102 671933237 359344224 591510222 847831909 936061064 678896735 763407958 743746886 527037176 43928320 139273044 520348058 111522683 624029093 910683534 81543273 347492774 43699493 917545435 62318182 694168382 658394825 613175202 895754615 773503585 625953210 139993594 728528333 373419570 202771678 92880513 8275440 401368862 804050287 628764319 85095113 636426797 81187349 322849464 414723196 104102274 758227163 777606361 291536961 565763431 24897642 454302714 118451444 199578708 536114973 13561807 604664407 710511708 68602603 246101287 330341023 11554764 246282325 136586877 67871427 23293661 741819424 975843313 422240081 189582735 293298501 665674281 959175012 721472067 175303237 261116361 957334062 87396296 92667119 419580836 500920376 953588008 536680008 555340418 493309396 25081950 3654131 481894113 73940517 237742082 188531335 694908951 557546363 648791585 222816232 517573065 500070324 733664546 426014264 46104731 894989698 274798290 141092250 824662392 323003732 808709258 297636691 708455883 996449168 806911278 440290883 621855123 748816280 411781912 910139060 826440512 561725584 224398535 524423546 350497350 590157301 113319014 367899318 348064188 286311888 80358897 266415141 128604943 105097446 104408225 511182410 371282547 411142954 310742038 118279051 731474597 230368604 359592544 160631779 633539315 864758527 19570703 289877713 56899929 372440765 441437949 98232095 646268064 102551925 783618649 714900610 913896620 64286717 786939659 424353107 461709874 658124059 67489361 281471859 484609228 531135671 234196279 362090332 497041157 39347260 489474346 437051932 631630407 191997272 497013741 255745743 954737598 743264829 664757997 768868852 109816703 417369525 766359183 660234368 678660446 224307800 926803875 805695973 653915585 390740872 395885625 821081301 208065493 921614358 926968309 938875714 687742357 108798368 536098624 875977266 507375260 537125582 357959475 21477305 132983701 193516698 842498129 761979184 313788722 563935532 80604527 67801195 964484133 655054890 563076102 936783842 493558831 298431347 583335447 281257322 298497196 781137313 470138299 453530866 888945083 878657851 249918304 921557084 124964786 57663146 986513817 873169545 691688305 300371596 214455157 931201227 907095132 626442615 955335730 906778291 132878764 580290569 255389293 951927251 450371008 641682882 243023626 168246195 986733304 129374255 336625115 385677458 830348178 902951709 358527765 855800229 919242187 108257067 471654618 965147667 567251187 761435980 750985186 910513866 323606518 399999680 309400077 93090241 893765304 826722390 549116988 775418944 775398035 882937519 433919753 104019894 851208198 209650024 172664529 544611715 547898993 24534465 723140748 802312118 640662753 589284316 213462240 844229180 642298538 156252767 171443045 631674072 572560103 652797825 829579747 383045656 851175651 379365031 738111677 298322121 542012744 118531227 399833329 386805542 427046518 546163447 50831967 435397767 174744320 295533344 179453175 921245860 821193987 901913299 185394465 823533336 652028147 308170194 754613637 628276085 509271903 2429914 679959006 924485351 942652447 205985556 91673196 247093012 319392419 752489677 175343830 932125640 433235984 297028828 536307815 601754052 787445684 935403157 723704532 785927621 320193953 59914123 411352507 800122608 271243603 824943895 503930535 662485375 188027199 958513838 408842292 621827534 941992541 683153910 531749719 336625462 494128768 567481605 930542452 138940096 139089930 518352191 62016012 452401682 3605134 871757742 277680000 824346064 728956959 355352102 523111884 144305669 786900128 346542177 276073758 124673777 590923295 22872711 665643032 675950823 236587429 402071074 676363572 440675978 368470228 282315657 253229497 807538201 671655395 96624598 745709753 546211221 74251727 859731977 720574517 969505535 127742551 578198356 385437840 550764846 119977341 448417729 791371387 941241702 119005785 253515726 720251180 913173641 873996529 220058467 340228819 997698883 650650575 460863519 338435628 393281784 929212827 905912598 533845486 849876679 919082270 57310496 579924134 448614350 712094417 313448379 861797946 652132115 335065051 303982639 102336976 5228926 658747384 496070454 789140982 210286801 335124431 454554481 216529397 294974550 124745015 334946776 350492872 315096363 226309082 840261613 861396271 4598643 993179575 358561841 57488669 786155545 766581558 112576831 4965355 493420252 395471450 757827244 71770054 600092257 914707466 94204196 345026708 656314583 379382534 497652214 690987756 730399979 587507683 691856366 713845150 206254856 109508968 23629088 992010592 919522643 510451497 346148266 567346051 33949267 54605452 748531739 587296785 341172337 620830028 526988611 486652000 488905420 201647835 373384010 194285492 251689421 968587199 402624968 50926816 998585612 506778514 821013969 135634957 981561977 489291688 23191429 605306240 797735416 63183523 471455005 538459530 911394150 871304820 647358645 307242038 662025301 598495839 916628256 550180490 431929801 335725935 660710024 464702179 896667662 2266651 17107070 436285237 732176778 831792653 742223965 952559967 755604666 664146566 842552451 230659032 962504429 538064563 766832461 990299352 818386734 93078513 855584951 448363581 110918874 482449140 655425018 289790465 634566226 758555894 165560959 920036205 269997019 551689845 695963828 871357551 980457302 93989898 665041974 972838908 935788511 60780680 328256095 927577516 809490129 147842465 286940145 145920980 696714060 188885278 932187577 678946112 805813873 189913718 734933375 841718697 129491698 75575634 730461133 44008970 602994194 832147576 451030078 405064749 343776270 335210029 338280147 772269176 727969622 344891927 328025025 334036712 747176352 378693272 668014126 81770166 853998584 541319076 469431904 311169373 200788865 242660661 212679263 822463841 294049696 805493671 792383615 261458867 274419263 623031844 128520327 562766364 237623792 636481140 87519204 113963389 613209837 101067745 632006185 375804356 27028282 3505109 326984508 987786437 699044567 28135558 876847137 42441465 641543673 249170631 509194058 262961104 532007073 476961798 415899438 578427772 894387126 655220783 801440102 422596918 155693438 245858759 710265500 552390250 159956444 390585861 912223863 977988262 748244999 489088261 725714442 682436854 554490326 877877870 447122887 239220267 981196457 266322568 908883648 397253551 17025582 154423923 144100119 566757652 65843499 763695792 849556095 672535262 835124154 32224599 881192460 296417384 753352289 417561423 307304259 608360821 584005617 393189131 64365015 690609750 735113304 973234020 426807485 832305590 346677373 474202872 98204309 978309378 903561750 100722541 959859364 947442283 525508207 246903882 398553578 295531843 732053693 558092526 755585354 859850678 27357488 900650276 676601631 234059341 388680095 418822617 865417380 418268233 754156274 617380736 177539693 732894942 854414630 537476018 823779440 591122937 17679649 898342897 994972713 363267642 49347893 219620706 446948827 376491814 945450446 708655444 618279711 886398155 631911813 841378400 587516275 467720697 598377310 511466574 569857581 234197221 220404526 97427189 686940362 637265336 383893519 776451912 471278941 612149419 710339331 662086675 908463892 43178986 572487977 259844513 838936510 763636608 257200846 797233834 83721403 983937930 434758190 979994904 785738060 550042010 281847182 735238340 181953926 583842253 776386759 577361321 167498424 742260124 528741476 423086263 56140071 530520432 88556587 5838550 885791774 201746028 311980209 471567589 434474052 618650199 998331766 515793290 71359434 774777067 264907954 392311240 634867440 195658619 53888912 611820513 504898148 269425810 365558706 492520814 122440258 714082542 625642678 737449629 857518332 158619331 299095253 829799709 664420122 350889631 804475219 582639789 127279651 826196214 232528989 675949701 898992116 662100498 100705491 505907506 588464857 25809954 719549266 965656666 712880661 31749017 62533581 625204801 280970382 975250512 831070676 483386995 708644841 695341904 631850253 602800628 193011624 570236902 619474643 856021338 2262475 103070290 43626115 785889395 717257431 57565763 21077232 609020637 278636393 929230348 21428765 492285957 173412477 41217423 514144043 535197038 890616540 300616704 439467554 716590309 974851514 507874622 503666808 881411071 983775985 99603669 50595884 540109582 116851755 423933742 135072443 577691046 967875311 581904205 797235129 209105460 268146669 651285755 147708251 663237793 998608757 249545818 444279681 280050608 825632636 238198935 564364092 267200791 60963819 472356080 931126592 192509046 690974229 950881045 631956944 300180797 756772806 452091492 303470366 951330604 350116458 830056984 578033739 957288068 392570946 926370585 766385407 472195644 293630595 6191863 857310682 877350842 48130845 327439993 236253345 394601417 948898174 544719971 990728334 218625153 156544465 543807740 456616682 795056295 172687281 626700557 686506044 165564105 693010892 843017671 512219832 979176121 114268694 599552198 561378281 465531136 422803627 260137203 165592070 104059980 62903959 682457858 702386436 279823349 952299429 131200777 380416008 254339162 153473616 677006790 534426509 623987569 145436067 617874155 299918263 216056976 666042598 491759544 346683691 485310794 948923358 832706933 907821487 818674064 460718 888597223 471726575 548206453 992480635 790717389 270354809 467690150 749709669 867988028 364411000 387931560 783204727 681785717 426470650 318907111 198737342 483991672 575152768 533874650 947457578 634889723 278011079 191564880 786576140 447883462 45530763 593132951 489976435 921233612 101513983 718336453 669246992 951390750 403585750 17540385 843297319 82589226 451416070 544486183 728534670 269647350 646138097 934399479 119636783 895145736 197154976 640103495 972489427 777914022 111978744 444751204 695073967 416635754 730444722 982917335 596589504 123079021 765925147 784370143 846175878 899829073 101738467 931359600 942943551 905990532 460884711 270112079 899017794 69087463 154685129 463794817 841135210 103124355 147305191 340955651 193811318 455846519 526439976 763259209 238952989 353777806 184368514 664127225 404727828 88725101 236943655 932006444 57283952 876423584 809814819 232808157 699947312 836312211 19237925 54670382 548882435 655609956 905079497 422056239 859178538 378824127 934683400 745421805 233413696 31313958 293012103 432468629 532757334 965987869 660405465 82756919 320455359 937911436 175495162 250005803 731849624 181606934 857033330 612587952 434789252 649485250 693630606 129703155 729076980 831839955 958973697 227284503 506066997 791290656 131853622 188909919 700297881 432209894 480746007 743051675 195402267 307024436 869502431 862735707 406683456 845186908 734325896 271987172 379764346 252042017 434284967 537848611 214467321 395628838 467331947 349930166 970911157 527393426 121185911 330286454 248406273 33633565 465731968 67602280 541948258 354723707 421893890 987148587 952068881 594714465 988063866 646824642 373855915 888853521 769883601 940635354 373830759 295070288 705347572 183452389 75131154 43988942 937213295 67195603 896904752 464174520 830942306 663425554 911015520 269235773 131435320 91569538 540256297 266357687 277077309 348403314 627139838 9061002 622351263 863295181 62524639 434727821 713943985 743710386 514181170 298352693 45672182 807497420 858903589 857602495 341959832 194989826 132085727 794886996 881514260 843856828 753132608 362627926 285577459 737061162 998011312 562027654 412786267 522149937 632800236 609466876 769712615 580410086 613924206 527557419 929744766 535415044 564390008 345664380 419270060 223700259 790987698 355200799 94390086 51611741 701234805 474042902 827174806 736276836 621536524 748885104 143202695 795434535 950907322 960850221 129231982 46042511 160314337 201630006 953863974 24609339 474536907 765743806 296529251 209853258 866944944 471575835 950754719 847336316 851972362 773080799 695712365 282498534 641511918 853980755 328898017 621339228 403148507 547303416 102331693 135717563 839486424 544281993 45723402 9903007 791061692 342388326 772630497 870915283 441574661 308304573 639427400 203112137 424997933 225021480 250570904 728818290 441818921 811700725 280431212 639650147 231822182 432382211 885126027 46782469 756187983 401505308 85214738 303886403 315198772 730923561 714183610 357789857 740609998 14775616 500642598 449262 899761855 839674914 652962354 338262542 248727700 631947928 533191355 920617581 179675626 294325889 424146000 24148668 565130901 853777300 227863589 321940806 695149714 848239449 606300059 934195620 719471638 221163688 561898806 440373098 445220720 501315521 879316221 154866065 608180423 165467582 645642668 74867428 658828384 518081378 482261760 209354283 443899803 6213696 328357769 457853191 329976828 505064870 186862584 911658353 127924086 879070735 666569044 974646062 227339566 885826855 655220438 105460753 693103911 881324938 228104668 202301862 851274874 839135005 771950727 313116463 22774857 468387015 529700771 624485650 958816000 418539717 695654613 844703275 888316359 796867026 294796178 292545345 418648735 28764093 8171077 204135020 74982527 849230992 792319411 431266035 100021394 773232449 28164161 934619755 257224435 422709348 195937997 736158702 192560011 738155265 923219836 55840417 730421641 856268347 789873930 208972833 196501894 440134349 739979942 260107687 567294419 994736441 691808625 469343418 735689084 890516692 244377519 618303590 419588087 664153798 375047080 80247695 109133087 50220750 656715568 392836898 637197075 371519186 260324867 700052735 886881124 548838603 554159622 792782507 524272719 414602393 340260912 771700734 848699564 407029845 303823295 349727391 745667207 118566070 53272392 440235151 450951870 587508902 627986118 190852700 500221947 647381242 50314372 967335297 270642372 383954766 747261134 359545752 784286937 750163625 250797970 852065597 833205572 272389500 271630596 148715797 534215398 939498032 875538618 806584913 336997299 988491559 874453702 210587274 138336982 123575684 307984190 207649643 348632768 235983290 705101774 614244989 183595937 366131582 859374917 424061701 597556878 530628422 723757462 1053677 182219848 220089835 139587700 6079899 196369188 524046672 590296341 542287175 217496602 258582175 210921294 153296127 892382046 10859653 464451894 612429201 839574255 346759328 459686837 789576474 171757908 158141996 884262715 197892100 746061084 317437599 795447637 746078044 392756899 85729479 499545243 16632852 943779693 644537037 335922598 747897627 710727962 651627546 356823530 10551268 409928217 468302103 60196881 874441479 854114364 234648491 738579828 540975064 338877922 573817855 620961731 323968842 562327539 128046485 720489134 457017659 896829192 55540997 370021279 459794452 398634940 646980863 674346231 265683261 497269316 624679205 294427505 104345212 53745391 520351569 289638420 481180411 858990951 634006225 790857722 631623592 130328244 133522017 308173195 730654645 774720803 659773144 972314122 906385326 508031981 870087831 381634634 333702244 790268707 91698398 833613316 37224106 798203004 949198265 403106821 28960922 640179312 474312017 721044890 749198214 626941759 709169682 350445952 339535685 28349145 477927403 557997431 600133734 702792089 841411914 680276873 858518977 244492671 681490366 329393585 580048017 735601123 185809422 983722279 961025663 330430456 752418471 979839875 950572440 579091660 51477886 733686858 323070617 699994893 146680187 651243676 216209907 306329731 729717155 845775590 715505269 30708423 185800226 167004954 827288098 965426626 799434130 989103396 976029365 236122537 645426588 270445428 660632216 162962309 209107537 480409557 14639666 919005530 259314284 291437160 608604486 616228918 968584738 905519761 319037549 363339418 67510782 594561092 137230112 159138215 152082530 343215024 706778487 787115136 410133764 607663795 866580108 212982123 731985932 835184856 108178073 897764193 317798537 274272820 222852900 394680337 646416911 985723771 662643777 25595006 343587351 99725795 33185068 766061969 216752626 522215521 806859620 106361794 393419722 389415485 148106366 13517970 793282055 981428726 1197532 125908201 366990368 469575724 23871761 198660267 719367178 369292855 953332432 339435750 991135611 759313906 966108059 967333856 394270948 774480502 481645413 714962418 100465954 428914104 461563071 769780310 682500277 15112549 839988854 164007245 945027954 793818269 957825980 654532637 580747438 411842657 300098066 242484652 130875758 421950291 595128111 540559099 582771632 669407846 964472011 707136496 479270122 651564709 845183176 788995853 206590494 423552208 564682564 5539451 519015108 968958413 941468362 143594567 556556501 987050736 558903633 468135208 979500880 705440821 9876666 869800553 247661239 805224173 924870556 448769491 7391928 534706499 118469316 522610146 797389067 810946360 248661209 199603878 263063663 559663593 407581229 17692811 927484472 118029632 214527351 468719820 661495991 310645252 51008824 227207116 787236009 335232687 845534309 532097053 979181237 286775283 864737178 391242559 396895322 138248492 35161306 491308533 261622300 826793425 936290688 490860633 887863519 543378676 751084039 722526806 471030535 573907396 160413681 401847311 98739005 214277712 221204668 598207646 378188427 413395970 712628776 260536905 266363279 387114138 7324398 799934856 750575242 314865737 363018304 860344725 6362866 143542217 653984294 888647350 754726670 893093166 996877094 614340378 827885849 256427562 517033302 285097584 147393895 78034822 163765884 223739049 375564769 680905219 654955957 374045705 17593988 336101275 272253937 88992228 489563754 310378539 784194182 332989229 214509435 454518760 394810475 772314399 388492873 89951594 2304830 569210539 602338995 885195732 455841285 906031962 112875714 967052541 288384899 581983102 381193167 61847427 535369702 947896103 522946704 600586706 189945827 966787527 384797699 959637292 882391732 469226575 423015208 753874425 96647453 252971689 215218738 308796521 452645371 931147836 593923554 285064854 305267060 536130759 60126335 850461089 484674533 36408672 333382196 14220195 771777722 743454388 687235792 132401530 384631948 411767941 955382523 754921676 434661205 342086735 786893584 271958810 952802315 677324276 33729651 786534710 173605964 488144020 616652882 365691573 68076276 721012059 738130135 985558303 744240885 548979368 247236013 56970367 246643288 10025802 15482297 362396601 378020462 788618923 136860427 568757219 543797944 773355100 671701456 666570581 887006755 96879401 930905580 77913333 585878474 921090768 966966081 502630240 551597633 73048652 572624939 284514479 411722077 813936252 646788121 985391233 576866297 207779601 783167158 878789860 56447130 206297433 659473227 246314568 615640274 196682936 856594787 690716721 74491726 136142648 947007974 806473353 224483309 888747655 244126194 988619722 473937649 160193735 69185512 204525201 507661432 275281956 42818855 234813801 976497382 687379870 574180412 328004718 87169556 674466195 992320117 741777964 211183950 509863833 820333706 358570937 135495497 918833328 25419958 24244452 43379948 345511089 719327228 376070625 607711639 59138971 64536448 433035613 158288330 204969243 245567865 285333955 708358165 222785840 766485369 843660728 219419610 825578784 31558536 122802623 261887602 283060106 594098312 240945076 540737373 687313230 550640129 942229884 745387583 925995078 56459591 483151236 998456991 382734900 525555578 488793825 385319860 707621662 165442288 721056868 104761328 916797314 723247171 526018937 87817617 366661009 875346180 553613912 418795789 735966295 395691050 884130502 298834345 172436182 278055848 156316820 891750026 908718531 697502324 178106138 136390610 55705056 293521263 553861516 999956474 327226986 13274746 551282913 774103917 278997878 100542255 726886030 710682757 966660877 835090558 129154926 861241732 626391673 883264490 353777913 735394354 807202876 699565653 35131972 297548825 522946185 172492166 858349482 868531444 513229353 23164163 153867453 858868491 881311095 981869748 716042354 128365854 849238538 362724266 502531514 436314614 929008651 704296189 321205225 351387295 515369170 299213581 57805427 383793801 697500824 43219793 281998553 837061370 441459312 646330183 999365609 372963481 616807736 276413189 435377796 814520397 618438870 396377710 287474862 795085861 248507428 967764398 192670431 185542892 360660828 117273224 280825099 540889422 74634021 633345731 300608925 721907299 297260848 672942776 602991472 438165261 143918629 102976041 891617045 143349435 329478826 227467243 288282582 755739529 864064460 296835603 219361011 571118798 845785397 992777134 252853856 135629840 220902296 798526828 673837398 781946367 693797225 33981937 243708999 75267415 417361778 558331362 212434791 776996042 592163628 384930105 392825239 163183889 105044681 957025900 76677563 272250613 463125029 244747448 332797420 359608000 302314147 704823159 815385070 345963363 970843481 805639397 526613947 150959158 167175779 674163868 16329155 649659660 376490649 739890382 102502912 849917428 725335330 751600713 962717264 685341627 280756764 951348955 503044346 78455526 381712259 391102045 823472677 158696634 58880685 172246277 985180810 497249215 378697793 292217417 484757752 426247958 50356007 987351960 664384772 604741781 749800772 948069645 208892545 899010572 552366430 238013434 161727638 594498330 260025052 136139045 865355395 818349814 220960558 805704914 58866576 721001941 301840537 979421271 428158684 296725910 324972067 497504950 794786294 331071209 764805661 314378515 157721114 746902643 412816753 172258038 437264002 619462037 731442992 813419114 29019478 386030866 357273847 413495385 688527090 778407451 589815649 730974674 686324320 450397430 505834739 897563718 725572379 82927580 710441565 774663895 807559021 583093849 854483221 259007461 458999464 122839271 774629943 208516220 411150681 631228566 206951367 251121055 353615046 807789501 418344967 538802764 758053918 569050163 377263429 907896158 992789648 439410157 318166262 963537593 710222598 145563505 433713458 452383256 982764241 452635737 744181667 324734671 95602992 878463978 509367719 931050913 880687695 799848065 614621629 890391625 615432075 292111286 634353257 927654626 741448403 608125148 926790979 851120691 852674076 397928307 156674035 548589257 318165066 17126099 110171235 343180074 596392804 566569140 221095897 855604507 891296969 777158665 673162523 733740239 72286263 828344989 148272328 814750001 773039989 397225569 66022858 886749378 534363494 593969843 80993068 479091999 127891638 800689721 385265762 559923936 511540412 538380802 116180879 583385611 890480151 960016323 881301947 239787969 393091783 750029805 277552415 551384955 84153780 773715846 850975713 947792462 871537404 415988976 80540411 825626409 84515639 484351487 420905200 14429075 833333715 488859198 10584737 314338539 883601886 581969843 426460455 351765833 569746920 982077357 576741832 973559633 278186621 928152850 106384285 17171566 934053883 215816653 393831917 298007640 267175515 344703596 848588851 918173155 334079865 241717151 596440922 189447028 592416809 279727537 218467482 270721182 746336063 691874837 951436207 262662600 641476907 188490688 338921124 30235480 707433466 77985547 523911430 513841894 763852604 928498367 47323692 258267393 410965735 137967359 580008859 226565210 269853819 435146456 397796750 455726512 102539182 551280024 191444913 685406729 287532467 958624658 580321356 957614643 297648279 127426420 47415338 570839775 339808818 577592655 855748271 627927748 608417264 915542577 271267753 276348108 559957939 484484734 366227970 337125306 254392796 326165085 974201602 954362824 783271863 724326551 931151485 158314312 496740078 824305288 235056145 719662620 359154431 41382403 572731143 344885478 92908616 898669286 516193281 144547348 593560870 894193544 909352063 558842785 569489390 777469716 78640570 708330392 20660152 39363105 696654616 130839181 612404715 791188686 154798534 676506437 541802943 828524898 591533543 58896106 3052354 144844929 709617163 770890439 496961418 839132122 515844793 895927779 779819455 738279329 623229265 858952657 932310748 749714012 332726342 400926825 948575464 745074456 89437802 206664503 338394033 171341995 712345746 521674778 338185191 753817605 595768512 430283907 176595756 163695857 976649736 131146912 794212156 957395767 718016412 512340877 573609612 751261615 850415665 765847201 124956202 171873118 251310496 387984887 776522729 963690307 95016548 207600634 552701623 742198632 534191679 860843703 617801330 888408556 374000067 744903967 219268722 393319917 297682835 708422782 265409856 308828119 280485387 409849951 529823134 838104145 857456505 883639791 757625375 339793753 248198924 569852834 64741204 361837412 243723044 691477445 430677337 46520493 273535493 899396570 397773201 676006558 178635226 227163737 764747832 957243291 114043200 171064956 190139912 231478191 61617841 604124625 816589687 420021061 243311628 98105415 991572821 156400407 69145259 36842475 752874707 923805164 552956972 655433812 214324233 83575230 758413345 17186976 550941981 973965033 125457665 718496651 801262081 166592869 616648541 317474657 781560607 424204417 571435341 483672663 46761767 576872737 398213401 359121075 837139427 403042476 353347369 884625390 215313354 205079688 204443648 156484649 471792456 790893855 797871906 439172495 575754094 666673444 43308190 271852234 73348523 530528442 243169837 126199156 695926788 163121200 452607516 854060494 298360306 449276474 8138708 917593055 439074951 396434542 924896548 204689220 518277451 678582739 19740153 743419022 39271473 997542031 145276057 398017958 73974959 676733352 645657666 136383681 284199724 814882665 148385768 447872503 29333317 505388098 544040914 289559124 250186979 948258419 489510425 450304412 114439579 32829097 541010238 28432366 546774561 456047412 162912732 837801930 554405571 10076589 642413519 27074794 459796517 938433591 204676995 822978562 312126358 321833909 928194534 846793637 901712254 43604148 543625783 867099318 655324777 625049228 204744023 450807123 979242168 590695154 288972525 777646121 719530293 496802361 220042168 70108 90278528 632538945 177559566 487438522 343567624 917822131 848369162 390882472 526294337 809709494 596433917 730786510 247542901 701969194 99956882 604349950 264676010 189269866 107968376 645520534 912055457 74523152 993635903 818590812 76392196 913312350 137755227 497198459 782655750 211931435 361898143 124054756 745797397 610517788 158523393 460323161 264917931 599936938 115268732 138142704 902988709 430041102 237708058 878707468 829813749 446373856 965299456 157864529 937793157 435903683 714575189 262323895 381964673 117440502 361449823 725645725 726862765 282825573 631790034 351473413 576901141 204117827 165704405 823430720 195534532 857607376 894908072 75763308 374327259 201946181 983142228 496632221 47591183 40673815 162160895 651146634 171295674 347146297 181444152 320530895 732735993 72301951 730371997 308716115 612147211 474783213 647820426 507289336 543204477 829228242 371384429 79266301 312748264 767137837 937085872 804287919 276947870 89085885 864487226 35963957 325534021 131341042 818570723 734877956 565360542 915222917 732948116 272909702 897580363 513367913 977379234 712056220 49634248 440396762 640362917 901470469 716849524 89134249 711658985 146487436 299321434 283413479 765162241 171390361 230238700 836524765 720436117 417374564 997636527 906509496 832051997 259366885 662495006 467545591 354410942 832084759 939385921 261179899 7124059 116467286 170580627 736516537 341787146 331509337 236728502 46321999 5963779 74054563 550441357 201406187 168194150 387177418 434984452 234249565 741104812 458650667 910758200 903939306 366960940 555518790 415036134 695740611 792628561 629747437 959327886 977785913 411884821 422835974 625673984 346390743 662576291 654491533 340440617 512740536 729687392 37948665 259231370 701805323 339298526 368902988 334832524 182793800 476908404 215504783 762235625 629646035 333499009 958404469 249467493 319582779 45947935 791744932 16448685 330926246 133079156 28728040 945640999 981029139 357615443 262512753 414125829 521592112 911254210 395854161 985088599 718104120 208787477 309884192 827813153 545338370 854969186 17026186 254857714 949411637 798033784 914324475 788707917 238195713 132175161 184713810 311487893 324344877 717548259 593669108 937872592 479314882 789652261 936839236 340370411 249407111 210312934 397993656 271388433 648035911 352655926 419143732 2676529 432308199 81516434 322538160 195852671 534851640 953269305 326554447 228330658 136267217 283639331 88692920 847570101 380951947 814449445 954485968 358485852 466780458 189687466 777121664 708266308 824028189 32213244 826779782 604666186 638761488 38518681 40722704 939320407 510936618 857126510 826038741 833349333 126685143 603915210 927619230 293748808 676859388 257788968 634364473 567356289 678605380 389197534 927090920 54443114 981362961 600263230 326369050 284272113 776373704 384221063 16001174 764591642 422500469 661905049 701803289 721027238 246763717 683636034 355160367 89952166 494363712 530137487 8483685 742221313 250458879 554547409 291369808 45677831 20942170 562903256 698802371 205895935 22339840 200563092 505229086 900473246 952859634 214992715 250908146 905465007 335568260 614452927 136142882 119423084 22260164 501128583 137820823 396953262 815583034 201348680 345727439 891703471 191501323 903967718 887891056 802469033 931010385 874987640 988913934 327239592 981945935 971618001 685353686 701392133 811964225 55069403 337396501 429790828 84457268 204279153 252656750 387997125 260223626 576696124 882128610 333697303 929859636 33748357 571504847 615641638 723685873 908147124 145522460 996609407 526799927 170300713 646691977 226180557 363886680 131075548 144699256 209089529 21814353 646724693 706401294 808151414 605965843 121021036 855755631 364669837 472307793 416686636 230785960 971939722 536021140 107943095 95349670 706499131 674282317 408955130 257372569 563653349 877041181 8839291 96802041 48473730 490407168 731682103 736068884 369134811 386670545 474745247 254605001 978551307 364918838 380658399 44376410 597067922 786212690 869622715 891496175 703447441 690932715 984770882 492259366 824151608 766023495 510484390 583535166 545051784 649993996 50260974 443322085 950492857 125624170 584103125 347201266 123180568 349912524 526629680 381126457 312410390 766968365 276682643 972935446 707677221 711449125 604075983 664929015 878380568 996829317 828397682 884232956 891239233 220837726 728306082 268484114 141701767 250812362 88486332 717501385 983607563 155446333 513007217 60343591 568116395 201658453 293521406 567138202 987288293 382524065 930215829 937815150 159696291 516019013 248740377 56510775 863093205 501845700 641592601 229168456 31051653 784721757 358095460 294902742 242303095 807644551 906292947 922908218 475639265 898969721 172183554 670851518 983092125 939828364 310712146 263771535 958881499 43117787 45359774 63123297 142832307 200972912 961318966 255519217 314488573 333274632 35228753 640503386 471183806 731084006 417473993 142561187 464700289 201755810 364614797 709190093 201707651 449610793 168679523 976423372 757360883 934926744 733440695 18936110 151787042 33164907 650773109 901721416 230897614 295358479 203692626 681091912 54743978 885826295 862796580 301572726 447391491 549855013 118762097 242245799 357753008 137750061 655436810 736315067 506742665 815155379 137734015 847908458 764785340 273776378 405135674 326257339 147588707 831292973 576038354 121489069 99413880 911620849 942382883 46720437 250136977 135850063 231090469 447784787 435451680 7393774 878228306 445310139 174463158 599060041 659284129 75648886 462443418 634522835 14585518 508879577 86215439 340699048 673725512 254802734 811080694 422957919 179135000 916645593 922700325 528081249 383352049 543721700 808091093 546166120 798112448 897221907 968853620 71344422 645348518 728896814 741014014 586728993 933063002 451581820 666121267 907017944 610500658 566477 622655894 120968211 574291451 758199399 362811749 510122753 436166057 371176082 94040480 319861523 813142604 954456130 195948879 566307157 152538885 296190851 636467157 348119948 104898268 621688217 701170594 217234412 751131516 904490534 762847080 697555571 749068144 364686083 210778082 654640312 639158825 438860560 944286281 190348579 229401320 913601479 980760492 96103225 513172361 353455814 630677759 155130205 494710586 746373848 741954913 503574437 253943580 478972027 204052477 765028955 479500424 828983834 627391656 529195071 831640281 817022816 782969730 825662770 385565182 57072415 760584356 618822105 82560111 775313074 278398144 451965936 834384332 758707337 596001295 899492010 852232052 860596302 37482539 701114108 6968712 806881126 111719056 464648694 833269360 522594656 572176302 542788353 308435807 467788930 469584513 20828149 839058116 292542054 118580179 218294099 822649362 752234390 466957680 187887898 164762582 331507354 952598838 769162347 360831612 529361826 685403562 958174996 157282133 992879650 486838108 607078210 832742168 565671231 255659451 845018225 334410859 322806949 922361993 860553042 848594041 348558170 602017485 993055555 237625084 386409739 28280314 300928192 562033307 286559472 282791457 489477163 546212570 730445722 330769978 121771470 569305028 322071182 486551697 470224210 372822524 193592440 936188078 209050300 477676680 996277091 249629639 810426036 263262799 249398870 778338414 177500086 154201321 77566410 216993735 469029351 55270625 650502971 760836500 894951581 161857214 688137221 807069055 894387779 212266441 466250503 826402300 390337630 142604292 242290702 429810091 71069841 114004059 53639720 689788610 746942680 900403988 523448876 779204666 858653088 394069335 607026532 832655268 702910729 603247036 370226509 769437847 149657207 565803378 987238349 85772240 176493498 719778373 795188402 64360335 309991712 84558778 171473922 418218862 426682521 920999868 956838084 756448205 669471837 912855625 797319838 133310921 523308868 868813788 89051666 592163668 346278395 761874181 429989409 201669448 922809085 168649631 503099944 630238559 24444899 713508347 369846149 218285980 629491797 621871262 474434789 42508206 562384544 986499498 321459447 5148093 191285549 406418896 937911592 418171289 930143114 230319881 951092012 57798512 678470284 777941795 142996284 86184037 435814204 323284083 156716597 750822396 637472436 121708506 501500371 705117906 903248198 473911555 591761140 364284418 79451395 307112625 885295649 578453397 994837928 130585653 705025661 258792694 228984927 164901409 635152047 968490534 192247067 27712795 534423672 371803322 336795402 778937652 957751766 515750048 875722204 699358525 877865500 872058519 230596170 375690 306185480 413843699 723309317 668931857 259098278 955478260 538274838 65810477 518092898 978567099 97755468 822255893 803581011 42104445 325077994 523227767 497261654 448958026 885366822 989058640 990235506 411564443 565468728 965380525 933190017 276754094 987818856 855900731 57848170 694110416 192613683 344967328 490893280 290670808 102278614 690373196 702514811 91174554 29076423 395241432 560916553 654834068 815621381 788396214 659275257 659571659 979761422 155660921 336119630 532340023 95254039 592457064 122575948 838953629 622575055 622332900 831967375 968244033 588051733 598518495 679681575 319013939 40892366 436457816 452388185 828897307 220141137 481151436 725762100 206702534 621916651 941271581 540704697 927237719 162316449 938135976 517485844 373566095 95145968 796519840 233844800 699239280 486203721 682878725 891113738 175202282 308543343 473134419 814063040 626259065 843967475 824434532 396981003 599221274 676827117 466569510 548798527 342481463 91899341 421874119 163879416 602245793 967078039 980409587 617573208 735066052 554676419 414043681 113577690 229951713 413272119 719206190 611543112 759026450 709504054 150406080 527526863 345164601 910011698 369889747 854327486 748934653 322347307 613793808 503186475 245122866 736178950 485250446 304970884 29736451 682841688 907757168 701136217 312758210 972552623 537429307 73467306 616667895 344907545 563180558 971166031 880501657 744375343 437429430 178597434 819458680 145831699 911497324 740138351 508323089 624722961 107640841 853313281 910501318 391575747 378911922 744328641 707122827 712860506 988106401 761296664 505269826 346178269 794243418 983402264 699610104 99610722 573417977 323039822 123337115 736119256 480720252 405424647 599579779 218150878 386396864 46233393 426564103 382223194 632730257 322753079 412604774 487078458 813064770 11193459 603378136 838904888 70339524 956210984 550264086 480669866 119967183 298391836 248552746 74834174 678772038 315990353 271025258 982770630 569488359 1749399 578424706 253003596 18230619 263526801 513702633 929432349 390913328 791584544 209589091 351340267 959629803 205136405 468820330 806724652 723043 117695701 367695306 128394233 9149165 968087771 379403322 290755748 877626261 619246684 138030712 35439537 588452647 597986374 417521926 646456693 314163014 378413762 313308202 56368466 84480135 837704736 804075533 291165165 522862450 14209507 838316636 293810187 859017293 978777899 754805992 805105470 898898731 509327785 921767399 16229695 676944533 797519686 25007373 341751374 792143572 461217572 915884443 342988894 235708937 802425347 844537855 322482949 454543435 957938237 32659278 568196085 987280463 796346297 134189134 258115633 226427741 20459450 55910980 154479430 516041749 926555859 737273447 178763258 752118399 219276587 601218738 409949500 52011005 201405877 439881514 132387679 988075981 380207868 278017133 174217752 840784527 68586749 881356636 866006353 879631207 285815557 107162842 425418986 740222444 854349188 917773968 775340228 836020965 639417500 570967919 526427063 988183957 131931065 770620206 337229241 346271720 579886367 956446004 810610901 381408819 932379887 707272464 218150910 413882899 889587397 61845364 10591215 619658225 539007808 160727360 971512035 89156128 612602800 589418057 31125926 821666267 593829160 2498282 190490491 98147277 451913786 971614706 110158310 11749460 933751595 122635727 940873573 589180377 562625278 770848500 71342818 482584377 647483261 164934753 326968158 642219398 534621794 376344026 372626299 998284918 282128306 154813187 598242190 585872144 444453251 521735063 282434271 82339915 938061159 335790912 662630063 845795373 121919439 856424405 265097705 402231654 222091514 911893078 44667091 407433725 995185221 186767052 259403567 990570713 159399502 741899650 781949436 245730520 498085554 34128521 860044295 414911969 726836465 874091704 539569152 284667463 716889919 359888384 580012366 587445185 959440956 904102244 967451530 948894486 362188343 474570435 63617038 759755805 468084146 499297641 106463111 573348256 779809211 139051209 779751372 340071879 150258553 279048544 226690362 448094155 367519396 691557660 245441179 778455347 823775216 277439263 838721478 962324204 146190265 615596657 977105653 936368613 328434836 300048858 657241244 229979126 211710570 484177243 302859339 694220379 920768529 43853233 23907365 788037771 652586982 465835868 31378540 161627203 322098788 385705148 471240086 11035219 973580706 891637099 285904614 586599152 401236963 818574128 442514945 277496051 586783272 259398394 757010408 907898120 85626698 879055091 87807574 337577211 594725623 421591341 413048332 548451619 656908999 984148061 343493283 665556607 585457191 272834748 379428489 120422398 945979386 725996901 560619808 157407589 30108121 163647510 144934004 417521307 441108331 40122165 74066461 466102882 707184212 787033947 35329852 509447096 244369362 250026207 949475565 215288603 119416399 968255556 101228761 837688962 698905707 900101932 981479881 452005995 461098580 812419816 319938489 890605785 105752352 755659377 942607109 901446 475177854 343987943 332695122 998566623 911587517 460257358 365734308 67292214 741862279 113794411 504279677 168829394 319624168 906937898 140509252 891947161 304800477 754922841 230167240 439056015 251424826 920727405 648917551 75046411 729349138 489218537 124790291 640842275 260865153 881851944 820319129 663602688 96494140 761045632 237918982 573801908 411770471 837478904 783528065 930067772 845535628 161287175 626105873 3361326 13060355 539414797 130611862 575447690 160236225 709183281 325569524 429404018 945656654 134726682 191129183 135800851 169046411 31307275 574101489 313130257 46630654 300633068 489646914 409733301 725299629 971032987 626735991 431617255 884305700 359462830 352112140 707324589 595270575 445869468 147356209 425092255 213067352 397756837 825490209 55289907 974988125 701983229 840006554 134154390 843003441 810109980 720603321 627311692 982962526 876301310 848315658 552511934 975500475 691357719 809877660 236256267 684111651 117799847 619853037 245509716 228757920 380477892 352723545 180314631 548910054 369413538 121877540 412605744 190348739 801990342 125461665 535524574 596014897 108533367 244729860 777148184 861399569 956674962 193581595 39420719 627938882 499294840 839981874 599069112 895330551 956429950 786123811 922218829 123050750 872999300 910190428 23937506 779655425 970922006 873468204 32556514 541863031 236207694 17466340 598483169 800712763 816500356 220224106 345683805 214431797 130586704 500180369 62982419 599451587 136298762 708801140 480694703 572145055 515777896 544948474 501695605 204186357 533732190 345035525 667077544 856916505 153123033 867929773 663280829 63602931 154340604 407768696 343707874 150166666 795315293 42323762 957878639 642483667 559348441 803982505 124296234 111570340 817958961 267832784 182605008 200532157 970662170 171066966 574956035 322541547 705062761 669854835 175911826 692005212 479841540 945685741 159413387 368772500 809603691 256737011 332035721 808522870 444266100 682431613 807868902 679827425 294766515 492295071 468469525 651197901 866562128 747920131 232025469 418058513 909034146 15626826 700509540 693169364 418404857 39005976 478852549 56316420 627309129 894741837 414787896 981614798 320997136 34061126 764731599 363282915 843445982 620580609 821997892 998113226 890943477 821064163 849246305 78920636 852335335 376231748 659635778 114512219 112148626 246871408 900593279 596808527 310092920 557108487 851231797 301563235 324641791 342811134 113513873 627460859 842547569 279763642 778659460 988694080 425139314 126235013 82034594 175623034 110018665 746768658 764088685 376524133 317318858 729367724 191253426 590424934 920395306 716780859 92129831 689693962 224796624 977055981 127950624 441917078 897681383 680045977 66045660 44953252 855071938 31170412 137977886 841311666 300021308 225797536 856760971 556324991 409166896 626630015 261455487 790148400 809335714 708438140 729194450 313609504 863737266 14611059 879884971 639324300 131306036 85297767 147602907 212479878 301923773 138185964 213488153 628773135 402641351 668154026 525207484 290716954 860335219 850606256 919794559 557212087 116320538 259650317 651340373 799054029 774326284 67382398 422342635 847246287 40098552 917892342 173795297 879592829 693520140 444561520 528438630 646492632 885342891 713449592 750738191 932893568 365134698 993481078 117811837 335657502 449254366 530186519 172044141 703200678 873870191 338071256 993988740 275181575 477824640 65665015 310663712 102310400 71716723 569295690 396903667 540305636 692464503 495755440 186472600 406999485 91442639 318944010 573442953 27750467 504283192 996665104 379458310 111611210 27404440 335085929 440041770 140166778 571020354 455249483 534473538 57487083 893626671 613787527 875903125 286061033 2832028 574051447 989501333 533441034 547135254 748268886 675745763 581916170 514181591 677582731 256617513 431790364 486671448 58592819 287874734 81155204 313681521 431942230 830201251 906931680 995846728 531756074 306232868 480503753 239907167 241982387 370858177 514860269 118602082 373085015 612738326 635959696 731520117 95119670 441609114 568975259 749387020 775458593 55349040 19632008 314042977 295570253 933397292 752243144 673723059 351929438 55220550 743850319 683147033 167525501 310939324 384759185 734380798 560789437 566812337 601444513 788688185 455668775 136438902 440945154 624591541 187616437 625099359 85723262 972044385 121646750 46861293 81510582 798227320 674616062 266914605 107162464 317968203 318255120 430717798 702746734 343840474 326903027 684355328 26662285 318771054 434127905 92539679 828763641 716857641 414325987 985688084 115197432 318620367 914503720 454419900 672806786 170357695 978502778 644631041 984858628 655775121 844622194 89406405 147031397 45929169 328502234 21858239 144477852 778513413 81026993 387067208 529440762 864719824 888050162 494416726 563859256 181240237 62625061 101156763 959499617 999877871 801102409 199913373 437317913 226405918 513692575 282941666 987997948 494477468 247772023 679474257 268982331 296452450 582773155 332266173 418642081 697542988 713931728 111822628 380475156 30135698 389125087 389007686 332875915 781122630 966293567 33688519 898277118 148033887 133686879 171508491 46341390 320878059 616403353 652577661 4757547 469404056 694087374 888693848 6667130 237530345 636449353 569004957 709240368 906410210 166913707 40266258 735603691 382881778 504891292 946204768 871848252 808519073 252316506 372259526 906726962 681687447 373845415 158442935 984502489 262385328 660900099 659237194 462277091 987465686 218787042 15157676 189893019 564163643 597657572 547040928 36855176 607021386 811168118 730730133 746518651 526394453 476756881 908837279 909066142 371555324 374982855 960301107 33863151 48578666 906420611 907902693 305760484 897575041 88393080 258006145 564867407 490478018 138756236 827460665 776877708 958578304 265102390 25796097 562903241 498735935 848788076 63788896 98564076 441687354 8885749 989584830 193418029 927845981 571329890 229133284 295002466 446501976 629166509 97301572 796222640 513330274 577690711 115382230 536352152 701281366 901025522 448488910 973423359 645404060 611470575 615499450 524960110 509572679 773244314 567252778 73470442 347039989 15798771 598458991 704673565 556190087 80710046 349426770 281532262 534313220 955950268 892418886 767739011 610457242 453562823 483362572 697040164 616559589 352298242 154364985 802966408 727545945 892760608 795763506 21737974 594250849 714317614 37520767 987484500 692655379 843062190 198980679 337647579 357890816 272756072 915925654 739341811 582947837 543990663 281381187 413067501 636262536 558528983 779022724 187363118 540826125 59225587 591933817 570079211 406677045 408881400 489601623 407674252 731039206 829664949 60643993 587789007 895777304 722223154 548511863 339653935 722294167 959222924 91370246 241391186 830517468 258082185 162871955 778749144 899142956 702579086 106681868 758112671 75924275 220643421 455567850 93941323 349076855 191136839 218109210 486725005 870695721 677465025 2932108 206158185 349427062 808359244 386083746 82336676 118593822 906812557 880093977 745826677 492541367 984260803 380627063 242128648 671740436 935898377 447482095 718465337 452636455 240984180 475420830 365090716 334686420 322771175 959797413 342687591 997651465 762453837 157822295 104634468 654608689 315056132 653035848 398197022 132868078 916379618 352071887 919940356 916605491 254678140 829657493 587001614 477338532 799224601 721230755 181458659 693854150 220196518 42887367 322915175 779412340 31411446 785943804 924965485 987571989 771825792 736421847 999463585 61381569 639554216 895262706 322924805 637061949 598765540 838534695 830430025 805944682 35585412 44141736 35270656 90473670 675753739 887103790 667064688 623096068 891352099 389570829 631354460 852438646 385301664 238030927 734872733 92543479 353349184 959869545 513637467 234669823 977649728 658557448 817781283 984587808 703998122 719320814 917038788 255987812 981346452 990563782 647883291 363485269 662921841 919111819 961820821 523159433 46668808 785295601 4989807 515962450 756995510 801440603 346961228 633009286 82532186 418864009 727147013 106951088 624846968 323432220 947754312 473930860 620595243 522898317 412794656 296055559 55941799 701668393 660929565 159999581 671319083 538108638 613715259 719706876 912790528 143882152 140571255 599169668 309849957 75690619 516483251 195580348 311936325 977709084 482768498 110870008 693427906 479783197 307890308 535546760 604988990 975449540 417241515 495241088 594711696 498695944 547152946 83804858 661418661 616197560 343726923 857278339 774085405 433681714 132643463 460619634 480649760 197080494 737125239 665581645 503314685 415721422 290762790 936330123 473235731 387005115 165525306 78121757 29132393 777270098 927496597 249123522 686212540 991312130 583573584 778541429 364452448 884978870 502481352 536888592 724008088 333874266 530586871 167376968 838463279 304119778 350515703 187859102 409513749 685882718 308182968 967489190 22631516 481514759 192157400 990002665 738205621 564811541 871621532 435494023 351805658 99886461 571728600 475153037 478773918 276469293 255857544 768891909 502440252 718476636 504334313 415735234 284425244 114568944 408391374 222674518 423361956 600768793 108523463 672493063 740780628 366826517 534132711 492620769 464304962 654409850 583426728 33661451 309509357 296835701 336225679 897066612 373867362 98461618 695286168 245029727 51056704 389298092 582487167 944519488 857150872 260147816 626796726 225774536 171582206 496969278 462588024 998437580 564490921 965976834 531048470 862687505 291979330 595676863 575769884 669791778 336882291 898171311 516920955 387202637 376529206 609190863 418543585 526860046 186352440 669882926 720084549 825671649 510588869 687494459 630089639 856821711 611637339 233166908 880050751 992637063 556575693 92492958 47538514 476540557 513301802 963120468 467730265 624551275 605498235 217309709 181642546 994844625 828341851 19563964 900775127 94039632 604806120 760631807 546157281 936011438 353936027 568909229 8336857 497289975 512881459 433288116 976667372 563212273 330785965 693317377 562810941 789673159 175033375 285453524 897895846 412079019 856132694 181549722 670667139 698747714 661770868 238325459 103442204 678965868 28398664 214430666 43808132 913228419 619753851 531293100 37179449 660265915 256678749 155011594 67469645 786753024 21960833 264443959 379699724 909012166 558698844 559371278 812616532 599557021 76794028 5969281 773974186 618216520 779307848 386056719 413946043 409749790 407112672 497668316 838373264 267704564 411483429 896874654 239530526 590649668 434761807 873806227 94734610 434949864 397727509 155111348 840964676 760018224 720641510 865033284 650146357 718132816 281877451 367007448 880991309 404448688 436279496 381158025 64513857 746352026 388088629 895702369 199549483 80667390 348831488 834873054 284413072 215649470 642419453 683838514 985632254 302085281 740032113 262610070 620510471 240355771 973617958 212612082 700966933 433751408 490726261 397387485 802228012 934588363 219123483 365864354 211769926 217628187 34701977 61702403 562615537 946100699 240574423 654657202 361819775 93640639 698068785 533206287 792063320 900725298 723030806 734380881 237476001 702568227 337533172 683018047 919865730 752238997 17653724 980213017 213099204 192791132 266988612 214177261 704144006 705928820 489745635 301401665 426925882 54243056 408217668 735785536 49442311 308887933 978530062 528241994 262909207 949856920 733066768 814203366 43247405 383622477 859839781 57401898 769766707 199864939 925069199 1897461 521751073 84523261 121916083 295211550 431842382 241390578 974078512 865765745 215434246 429827519 638675756 929209305 402895347 527231353 996026755 74966909 314215547 24242182 902478360 885473134 979158521 601459983 152817428 824836899 949102872 596245780 557281542 874909589 901646610 636872072 813037360 91500422 641341593 500263782 256809839 572037474 233335618 340980579 153776399 209533410 653962779 577146856 29386941 121075860 311977167 809958885 222928863 829715762 154124286 557500811 691661257 602758873 469062406 3282140 24224606 398864720 959609934 920177684 534294731 857840817 279763951 322667206 164243444 510434147 840657192 31622125 584489361 241562383 714785085 877639902 946341048 891302385 323373845 480818663 776230039 806109477 216766412 514156015 596261568 967525406 137603667 391882346 932357889 324345522 947314417 266907207 255974724 809730866 915455728 271100126 891445824 103737371 896871037 572015585 158640197 818937054 620201178 948281269 18075551 163000549 939968357 448902345 643854094 179838703 975311287 901516127 288530761 280720026 607851419 291554939 816444069 66967961 820811740 46331036 705916073 519747019 811644941 777004426 480374536 294557474 73529732 721875339 748891061 396287675 105072898 39843385 304227214 846052285 949942898 442545287 833100946 845986686 202670616 752105348 659731506 65112215 428796127 443467703 612999510 778117796 316769657 605396856 494252956 392337914 758344924 210612269 540721708 232392927 170800255 254910253 692653914 303549226 928026782 73732804 420955054 794632154 750122780 780875304 529909269 900703210 109118092 533724998 482854320 464488743 188468279 567595009 183271660 659401453 170451896 151101144 72319388 331307229 319761404 528573792 592935335 186499868 679277031 471485175 183347366 925862324 709102575 983877100 939645694 186472202 954273477 448783162 917074892 582715016 517382896 517281689 570171922 843164623 44285589 317719112 838618851 350231053 230662441 785231648 929073423 284453348 542378381 106861445 428565665 863717148 751243945 717498596 223246313 218387000 530400883 974608174 688617978 997912350 516540627 824565459 783788740 674399511 895589817 768148303 960103248 650531878 418853830 912662656 71225905 694202232 363603793 737041688 866223273 284549496 753267119 807348139 938222183 910729777 63704711 938951136 512705441 212638945 586560453 559340197 643017760 648271065 623563673 77726768 25635171 174989669 594000137 5991376 627356758 365980172 364232331 518250739 471832971 956279057 469818606 210930126 239913149 295792455 966816383 403240803 806001876 662778865 267430063 144774248 271641449 400216918 318458113 229407016 304822831 703647241 176485976 713187610 521805475 985244712 941171904 306114064 311294588 368301118 815983046 473648871 92928980 726179582 93073871 815972840 317548581 554153011 527965876 849628121 834894736 504915514 752680580 799504659 790759347 23131489 29122499 749747290 898396306 534787218 448158295 619242070 629754574 677664222 732509791 422440546 386836855 12759040 142733482 76395097 680371714 74603169 454296107 41788248 855955873 302708515 344382822 383383531 160489899 605851883 941567410 754215423 31355837 363205404 790483387 773666757 875497860 475753088 773283 866542356 561853817 253301294 719052009 744204553 42723210 267953735 716658718 177741265 740211619 671605415 247189727 176626509 606297395 110164238 471510119 938109444 120099760 533485918 880545440 409321899 906831282 221993225 95546227 238366333 860984987 736655014 987019371 535853473 753947172 333465963 470698160 109454814 597850483 801104466 611991561 828379710 531340113 474952002 2136951 381972871 200199497 492386938 664540014 486689489 651440743 793303066 292118276 253269442 160223134 19227846 527085826 737433384 428173724 745529695 548829250 861537850 137183850 664049353 237737197 700660844 973715051 687383346 938069501 227898227 996847418 869906446 899837280 901905015 955737736 978564973 195416650 179305157 279967825 4769340 58866262 471451740 195994102 928759471 151631096 519825645 570576289 468241207 538326518 865150742 164784710 248931484 698874511 173934402 37066262 647611709 34878997 281398472 726892991 153355929 108922113 122268676 620983461 839238087 971668974 719433449 367580208 729077106 873255257 583304071 141495862 276051489 418419146 919138818 588230777 190346071 22286424 546292071 880569856 541158968 830478099 252467615 107111058 43789880 829446910 724521414 194749014 554709480 641846873 158170799 71815386 259963082 711928778 309676567 22661933 120293164 442569743 102276973 193345793 472568116 903125925 915881318 578583714 854545260 704564137 197595312 960006407 901656288 863603825 603186867 389106437 308149776 627292770 927829397 776586237 244292890 827561475 716495589 194629694 411151407 561592274 286384198 368719552 86563593 885504889 843328038 933326594 834417702 800181534 684942033 616628940 999489397 47468776 826692903 473727484 572609022 150385047 294205324 844791198 457892270 365082355 896281677 83951935 460712060 259952805 234026507 917944931 378593600 53488776 839393466 869116095 687342006 105520481 935711597 826086153 99865559 95120849 673192337 646318310 795506759 508964525 565024271 785823155 634152640 273952697 783355575 374575886 174964008 454126130 992545572 179467971 444212313 537501438 102505719 433001782 257948973 841942310 150964734 156653641 739983288 118860186 307389240 840611340 359897249 663018588 547375483 916041384 560360907 525768347 647671478 124030504 838762120 481875109 610624585 887376740 256897544 26825252 702908965 140937572 593626059 945644278 638320818 268925617 430754112 796955027 948433451 661356576 970556508 470088643 711252651 54186309 846375123 902635898 676330019 910623972 14482462 304386990 902346399 679210717 906064007 964800868 897162343 348609849 996199357 245798588 587843575 456344528 605244558 496167838 89720927 176296046 459244848 72928351 749921539 911145158 730827762 963049810 501602971 536384287 376454399 601945680 811451944 900897968 146010371 707628481 417381448 405790143 933188340 676423368 246421344 757624075 356527736 314575687 954214371 376203114 177455133 554117519 707638915 199061518 339741981 514492460 942590606 21144237 729938123 120337081 129444418 587382843 832097454 277798806 212644575 106720481 387872216 347833034 922361209 826148711 58215940 927638525 383516814 545250748 250225448 21819246 321027436 934070922 932311790 649233905 694302441 972002273 943464155 699649353 781630611 828868543 675018652 42750351 593720197 696793670 341948056 351730959 137414424 43624067 559107180 115662237 570629339 374647686 521633469 632899895 452273471 594952496 846666505 839968470 499515198 82245204 91339325 678399840 696584537 372108177 831638661 927481842 771861219 90047179 802571025 468292984 722583174 600394087 478056459 565411890 677718616 446803123 921717141 182961095 169412692 130464119 468334060 387228131 128866263 385855242 754599750 91473691 513846361 246456410 501114885 233310515 514709780 163074198 653670365 937258901 328906670 446815215 820177615 418083783 570183267 211879738 930782751 516348572 96383621 390790971 868543229 867367557 175908815 260803611 588866045 809073934 100979438 405532699 573412616 148027816 528879999 789492424 244589985 77469255 418447752 766669930 288337299 562602698 54389363 75162387 381915050 806098711 979697218 693975246 225575190 764414086 422406095 112829078 198201234 182390870 295492273 387059427 161123670 929042082 430587943 713828502 781229919 807408211 481436780 83017704 603716747 291711269 338607088 103779897 41071815 311098687 780849432 280498996 93325388 546195445 545683873 853259577 559378900 803189153 819334966 827015169 111616575 508325404 358896270 873876835 722122788 95572583 704396846 878533342 235050682 433647753 839288873 766061694 43291814 392701915 30634235 382675228 843933339 5531967 315040288 830873712 793312778 811061365 358347419 898766287 588385135 405788651 179328840 790016496 354507100 823714120 188723259 974701850 358706962 716375201 23574726 902106892 664141595 962411922 2522555 348429407 902214800 424278549 428994351 187500677 203566560 227906900 101333105 477700312 164805439 989884944 603622881 401514622 383074742 827119471 23171369 641847148 738343377 388568520 376704503 299360402 297003757 285606719 490527018 965904710 601603595 668234607 308564981 232402832 572704052 148347444 47325108 48474062 989493546 725948479 271569589 85307283 175470081 195820348 469238933 54302803 532288296 858753300 780549302 532066405 563927632 97368697 746520383 606422760 116824352 319549011 374690300 236046076 708714902 763659392 770202175 653134266 205856564 783703646 127894674 805108573 424198498 110278598 164146957 281056263 9227529 873591972 957078285 98125529 977072863 649678603 747215457 426393317 126541193 577743308 360571735 839038610 347861107 970981639 649500264 80201527 938056250 521980466 408080088 941445254 783675242 84086809 760275427 836948695 193881021 439163082 833318251 69735287 440064755 437378694 474144534 452445711 261591880 314087083 8540189 706173248 401335357 759524323 637096498 442928640 576229014 984336832 5782828 45852494 171856173 597445547 476537328 519409659 254440792 383694021 42799044 738613983 274468532 562562391 897000311 609770698 722490842 290722697 26052487 163153662 415259978 632788891 552453816 650913454 574253403 17945382 479117308 602419793 598054563 932734912 470417040 937573677 341885682 618667390 951041766 401591014 476281794 975798878 751120931 859185526 259838572 955289332 288762504 116020460 100119320 345417042 801265658 562294400 277233104 432772700 677072448 231550215 970154688 244160805 772163502 171311386 996245302 941556808 19747814 955566409 431262209 534326777 987694160 164906822 346296653 837298774 89177413 594052872 370633668 291581482 447426578 386118384 923528583 815818272 277563558 512068748 682189085 980486998 838213561 939236327 466879525 533402858 858100530 844975074 710770011 218004966 207916841 495072610 465895491 251324274 979566044 365550262 534884147 548316169 788262547 780671329 959804784 553123524 843301594 78320224 141524928 472911377 348853705 914668164 632501422 683828887 318638665 920386744 601636613 894983677 429318136 287227025 229789457 662075139 593353966 489814846 278577603 154179772 678231039 919294217 652690192 717796362 641075585 383901822 941860934 844445099 590925829 853547755 784972259 972067155 344136601 133397554 551112459 893261291 362308197 166516027 530894231 463355332 996439186 815917037 283272485 879559251 239866551 17051394 354688010 870960572 905274818 578063989 532038033 594929715 229663916 764851632 666625322 552670321 800125573 66485090 250238574 171947378 22773698 921793850 392532001 247919805 364642328 967249544 510621865 139825769 193711158 437760997 836613251 372006463 390916783 908843455 728561219 686744533 443870842 986454147 329961212 170111862 529556455 357333402 601414537 984695516 95994976 259678166 102688854 107237786 588775784 27219830 488936952 267472000 679683631 626087167 47807885 254282274 797504021 946576892 518974381 708476887 491844089 847134040 89728738 52505410 651565303 336050187 642111578 947936771 392598855 371988156 703807044 230636018 825915783 886437066 971591969 945357479 645425815 267425562 375336591 871440986 117407492 392201898 486978126 41394145 831779722 213186894 713158192 436360533 59567922 435410588 584472764 184127800 960522717 967019958 687694146 311475877 889713562 737631094 460815671 922356431 222398686 713417967 449522886 525236206 9984782 765162602 270667457 433134057 475145587 268393188 13591418 819427112 98432008 841765019 836982033 845878819 532412587 191314770 879187950 51872623 508287485 442051915 35761949 66779810 764761113 581641544 436688954 864014716 762598159 893595178 276304834 76596295 371436018 630556808 173066718 795540276 24327378 300245739 859308015 807552645 37225818 39445128 54748256 342007247 215008820 96559413 867102852 49352774 664491819 133667045 630459058 8389827 876172950 904125529 722413100 281882708 750759663 996260011 492180806 653897788 81605724 397171597 340563321 272953807 374190842 719122594 448613906 387944744 740173692 442282448 587985195 369391192 572992580 783536055 457245888 99715830 473800236 5575157 558395380 878973526 970551373 51850936 55884295 539297206 43643497 357847396 94472166 319990746 53824789 678275996 770626108 469436882 819319006 973172026 419002464 859108106 192337445 654428657 5111442 158542803 347725612 791587861 299097299 204416488 313272569 801471009 559329903 487141988 95341956 124516069 151207583 668705148 487872836 483670548 540685700 768969633 533497470 377990383 497080090 971323693 998601232 106628655 417696475 640120949 923627242 956088900 819662046 141474567 386882905 886832632 257823995 771618090 456571636 681846711 939651144 721343252 421461397 751787397 388014839 391436380 500329740 384047181 165442864 546771423 722359979 189374097 29638664 843121403 967933811 846065790 224658023 596890843 44400174 348431919 969542371 652820475 241121809 639572787 119320715 582771596 489697286 820425061 684746882 592484709 753784369 257684744 978910685 653481436 71513827 579900842 978908691 956062622 76831766 625864005 817127919 438419273 858517864 311780518 644958101 763927999 699351244 434168701 68232621 69756764 672496311 554018237 120221211 542129714 747529310 556961574 358775047 384861451 741062366 249058651 299323787 826318536 151768418 479644678 822225847 139878949 626369164 351486722 160695882 858444227 383211847 651437859 242162830 489854363 34944940 54625981 174135846 258508483 340674780 414661 586621351 110263612 424316694 587128777 718994992 906045490 613717934 280433211 546324223 865923116 841917481 931833013 855920978 504939113 30781132 877507141 845719685 154487112 369310710 504138821 246512636 911738000 174778158 930257234 73009922 854237238 760166884 103661783 784117314 941686842 414308007 299904915 698657042 152797174 522875482 756238539 175054021 121685629 29168172 917914073 807198672 397445497 89603004 149640534 235202681 132905369 745666890 190481263 4686608 379389568 851202316 316120982 97697986 303176402 262134881 487661860 304564574 718312164 433833848 797207461 844878478 980014976 939255513 746156855 171013134 446688590 571051790 286563720 570250365 254877415 503876425 369542178 327625706 755641236 707752515 992721927 420563981 796908216 154441424 13396984 638670911 715071759 924921318 688857160 321128323 747590912 283156908 264823312 286164728 287844538 777891696 867480836 784233282 884131972 811841847 574842077 972618833 524133648 919865119 294825967 182266327 282716803 336512199 563485981 119149271 641039766 445745627 313063523 362276937 777563651 892734886 857812602 508787048 622426909 501330278 831654565 743142419 512474648 88336381 263778698 354799655 484616505 770745909 456708050 414925930 492782825 311764510 810530330 771677285 196791661 93512944 799459678 890385332 243546983 502631293 501909133 938007166 511698292 179667019 889258714 936269787 992388028 497383965 351092159 493160336 985802255 452001103 121737084 535887861 386858952 977593958 909952529 627285574 368590528 326346992 870955594 228643518 131013621 267251388 472628111 905870522 19504006 563373632 973305581 558044178 245018676 476129579 401711402 346806323 698146785 877847090 618155598 317328543 799711298 295495006 470014273 390504907 762411802 199501306 522907434 732240786 559473932 831854077 811195364 358193926 360915973 18999556 197521132 984741358 356727778 445047925 126698600 161656904 970543984 253275874 402392181 244278079 592739507 772757075 473616222 899871930 661410 650007186 484238360 215247781 746646777 709886169 522733939 781875921 355016171 263193702 72531972 149916190 274358091 175921945 99308217 472501341 324571897 7507586 275701843 434276641 363107870 362056825 922801064 644037939 880403776 154661416 401057730 168380353 378399790 193435618 321352930 284661530 388446293 731894708 42625653 536339222 897964252 725617368 67772608 319325875 141713047 936842706 426972522 669766147 246949074 983950663 903127042 388363119 529860573 987010622 925170505 614759905 696929101 122103034 520521873 90310599 96436044 816320702 22620546 136602557 506259486 659541702 328462757 212015324 932647027 467868492 127438963 120952276 584331619 836315488 939613188 141608259 684153498 547774455 325681941 273132394 292858229 306813080 966278608 172233322 883673143 856536171 618717227 265376606 376650163 434479975 849378074 120821625 731326402 39195908 89152854 491377279 216410845 500995355 509020062 519089880 643784740 991532966 146590983 140464611 156052541 468229905 228523536 16199572 992639229 639931269 482493044 519842595 354396997 528120550 959281795 871006697 272023789 192231628 395888261 78112153 599122940 536997069 696012863 933604327 155177786 678446100 145750243 41592707 988500672 72630249 725407710 251761399 223475217 189496180 532535857 781321868 405712255 693809760 782337061 392645025 890812810 805265971 533551395 459086336 454697355 151538974 393328296 261823244 410622488 358531060 670141666 635646143 795788204 792140899 654768779 285617181 311339581 774252090 208132960 583639860 278999402 49935555 79534560 370960115 537980017 796734684 401824290 565835679 206323390 436771660 561005403 206748028 918365095 585236520 560207344 844091086 679975426 280475178 494914789 871802124 556811288 405718480 819227657 904849395 771121155 743508047 20054823 995289439 745480088 472490371 311804793 698307515 562840438 661950235 402547446 636268709 489680095 72886095 37134269 449994943 512438755 570479990 823108883 169324138 219656390 615185247 178281665 434146293 137336181 680708516 180744795 764569975 675721545 231874986 693118744 906821561 107184659 881561052 699492979 40306259 426503070 446741402 92732784 607217820 929256058 604072256 928244303 409575790 632280062 310046698 419204557 934835590 746494556 172806918 21344387 73312577 540064789 835743382 645177619 23211863 534530785 491078280 424747886 419287723 227303004 677173930 21756710 86718252 466920180 579152514 365820456 728002541 255149643 746411778 149550526 866167523 467543287 796156908 489350743 348814038 434982665 691581306 741746978 908740868 835347572 620245578 900631690 761612740 402311754 475336016 543213440 132326746 354743754 622387880 138752658 491512259 921992607 361248464 496456052 798763477 386429546 986371431 230777801 508596058 995707223 117371039 239897351 883466589 328475236 745695256 398355712 695713549 63031500 40795692 566778449 570164039 769939828 696184033 394074596 735578797 177377836 431382980 513243160 947029702 938379859 139997233 479152892 494146534 277366924 250462254 904787864 606756471 341591487 484713549 938963981 363011282 159119320 819844388 294047581 63152828 742761870 419161015 924690173 429916401 543064234 817703436 781630006 131160686 278816657 640322640 766802294 875121946 754183772 762202805 1231739 64883419 156703255 600008129 731430281 154631056 919320945 417235316 418612102 293885079 949087792 372733522 982618997 85753162 642372568 764888727 119536712 758116620 140942209 524438451 981239243 569336899 349941213 65310874 636314025 289802247 433116584 408693458 213335794 895207396 127208547 488851030 887392098 730873876 895775944 102124290 502676843 173969062 166419012 354232443 531373144 317320701 589694210 550608396 364045822 415316212 355681072 654245365 617322325 31650357 178268548 621022096 130241242 771042142 273675402 269527212 502130380 206871909 518270143 505584263 87549454 310787570 21262321 416542217 437323823 398876711 156851651 237417169 609701116 418298557 350491044 948795394 26102720 242926548 304857364 889081799 356790566 963799032 339449182 229639499 367345604 124227048 462263660 674890567 945737080 170798644 437737007 18543745 827167979 837170903 876245338 186051233 948843914 829529268 822990422 708970997 41532695 593526814 783539920 865836880 980927470 486861173 182711634 999743722 505811039 91688181 271835857 973601397 368443721 616886984 114185253 544891317 543818281 936804170 249269844 540506502 531351653 739364174 7262777 5943514 987504927 665592860 930831266 968435146 501112279 962175637 19430016 840182633 492032245 859358481 374764246 734421952 759802867 252753062 740454708 188445419 118155666 618712789 383966761 651181544 297942460 371791678 988348862 421941527 411398688 784704486 923530844 858129721 99174313 342123463 737199290 975677403 168328165 173749043 160419199 176002623 800755852 871097947 331703812 812237935 244911276 701375225 950313122 490502182 800510869 177019827 66716900 228676752 669029948 987443029 203552229 226457956 48840512 771232272 452397653 45698523 658596408 215932394 703566978 783535542 12591424 303200343 933463988 519940375 375401368 82176491 673586 62505863 681421881 263159544 11971178 528347186 356885321 210162578 877582194 20304916 900675886 736903906 875222421 755552287 981730377 460201337 561751304 507155434 740892184 704766952 894352492 656704188 686529550 832566280 80053870 368244651 828622275 796112783 86725894 724152881 977410424 699905134 611757733 57321432 493154598 159601317 488110843 818193187 517261616 477125916 908993286 831675801 216549986 676989062 831321451 538077011 128011724 525096618 351715594 941703185 929465960 478963931 465892681 519134646 228625148 661323177 347175897 621028133 465428866 706313951 735085751 705882195 969251121 708843921 449774125 658981612 49872869 436753113 481626656 170592449 194799558 127411981 425162808 505114563 981575606 244657790 200784803 31891434 754085051 807179932 252386969 173136394 27966217 869250638 515453078 545643805 834460487 819121122 657197638 669362419 557734122 520811076 439930647 149524117 177345049 57450114 376938818 954621725 791626683 287162532 711512940 207729117 464359950 971336988 391931204 263148468 688656854 736102221 302222584 252912161 841667280 891651788 301286627 93737214 819647244 335561116 270317015 678409345 555493268 641809813 614680783 347395252 166316420 271663421 486767202 447785009 109007269 962051869 332714491 51620513 341856558 633216693 163017174 3670196 427964637 943125677 781246477 424035514 678913374 48200284 165969295 360888855 347606611 448518083 311801956 698980494 939328258 202495846 832624048 510903002 179084 592871679 579288322 960435878 139296800 297960287 888241860 350248610 223964456 117025694 784027331 51539187 573537252 401135892 806029359 159700367 57798761 964890958 663113237 903377490 153591361 265207243 463707574 429329850 369187476 700105442 53833167 160676767 220019558 958709721 109652185 827048136 888416026 988840293 424806466 842001997 90903335 767217673 855813358 689735827 608719497 117246389 771582150 871845792 73723363 61901136 550144775 845725854 86429413 507340627 796850413 446006006 752867060 454076135 117191687 506005145 266974783 699138835 340211396 992121342 852806237 717377657 652798229 719232442 627520277 249547091 6114841 279177288 525755019 119964608 64626840 262314941 779641134 600805372 279406326 832998756 114021782 368363783 620083907 826552136 753640463 126896788 791266458 487497919 218914829 603352360 110728671 335166051 674304136 338584909 236187487 152481686 360243196 720457045 279871579 142276228 36964619 952722287 890299185 758328162 863796424 478254952 490991919 807946426 587105757 84285103 935172124 2840336 974254571 336287743 362132379 522617430 556114759 756119925 571361065 686605577 974716883 271575874 397165971 732702350 237814486 628554320 931495131 227646508 653271421 793855552 308441103 102172228 701243855 272916492 472147350 724849306 537114165 679616113 940145631 208159875 839039581 908570757 171699954 18869424 816826364 25228068 52490530 832434144 995888870 473028231 42296326 263374522 975202926 224910006 967090735 718353106 796397219 954130445 399985223 391672836 333799054 6338991 502549189 127901687 831210887 965143326 655513768 444380066 615913322 114957837 876938504 281713574 403043017 637760493 119238816 694357028 522055697 469463269 769102084 666524832 291575789 768288912 162183291 852380194 260951396 583312844 216434969 465636572 741337059 986690325 571549541 368508482 385007048 143909970 108749084 375229020 144029455 662901248 356167059 492537406 323758194 485996485 249501604 775379340 177275040 151941234 775265875 459451272 325837365 13568599 428391961 223351080 553139544 86942791 598619303 94346517 120185035 942897222 744260075 891454712 249115236 664809989 93015090 398973892 231440 983979111 95193929 816059260 778449411 453486484 262335792 614110407 197550124 696398003 209006700 966465720 575777052 89297086 848620312 426574102 716315779 926910948 322938083 850014718 374678148 119489073 988236743 322449871 230645383 596497527 203120874 204317602 319066696 721560171 849790479 913617918 101615479 980284640 154240172 352680442 300402904 893078483 203469954 385181881 621564691 589546197 455620254 967312089 735673236 80168964 874668512 36338661 261417715 454328548 657113747 772366852 331356225 275392994 105891994 277330868 610822950 617323498 314927498 151632181 275952352 136480878 507296206 712189026 525902038 812621602 247934937 181458232 150298762 265418833 959019306 988283911 306948953 410156401 452327420 277287830 300075423 848330745 636457038 871898752 421044361 44031059 725695423 275414079 474803500 806129400 271294375 760659622 574265874 750554805 600327076 357013178 965981508 34943353 874495088 417262362 924335676 58914652 732905973 433379826 427753899 53614387 757158111 391967280 787647163 719270683 443319381 58143628 577369651 230011103 301835874 697115021 686823301 146202899 3273026 302286859 599134210 990817315 176639046 691242618 133133700 622226136 174606742 561547321 54596735 206441515 111892849 852001518 415765091 586546797 294129243 501795474 471033908 884065817 764160241 58378316 313498843 441322377 198118196 458051527 720087512 728031729 327661326 820681917 59714907 109684138 94980106 593228002 33036976 803113310 451971142 790471481 851738818 865711507 135058577 749073278 349783556 486698424 94283453 260047729 544274700 134099151 813621208 114139452 657777858 786399477 930541723 840887726 34606417 377971591 778303671 189066942 358791653 733870724 755354878 39805996 236009481 151891784 801485396 785337687 237579246 310408316 502720769 657611148 629713229 511203071 817280014 255001908 680177847 974966835 54162756 175697078 749781192 735093942 190792372 745236488 774859399 878195213 651296047 447005860 337625977 657375396 286215132 934617647 304960159 149499106 804230370 194758158 697250018 660752746 874193782 854265960 77087829 566993671 85497830 743920951 44169997 57077625 812857219 365952277 604094165 847578542 823255512 475588815 894614737 921577308 563480355 850100325 204630892 319670463 430689774 533916605 258813428 258650587 453810725 75312037 535774498 431043017 47932272 853459697 181101514 126149370 684800491 129211292 585283765 779503666 496528208 54716881 629878044 216898274 75292693 728265929 116014756 516979210 93842031 490675806 248088382 284366725 388469222 818263623 76626968 825413098 583862442 926705314 269893679 954569615 171017336 938467726 40902981 968473397 685447834 343414196 672323927 309108108 9414957 833603013 389773704 169180473 939527283 59737545 978678917 296236566 57696857 928266213 34296766 994853294 933307084 456415353 478758755 891482974 657010303 269505723 455516615 512880046 9315217 674690205 785100287 864799427 424243159 584120675 640185942 678466074 892813592 744582654 328740291 575474922 986766967 917863137 389397647 217109751 931035203 128570960 284989356 92565751 611397258 694229591 408658532 579724270 487371409 488941457 609847995 523181622 578019872 197132340 523562721 444371370 555886240 408400140 766565139 385296650 654780192 169551246 301362751 315244920 184122165 333775751 442736437 165990714 190652921 834171444 857298043 330695741 420094508 19929002 388396375 73526499 713401955 667914849 707651060 931113192 372379632 364115747 820093221 74974078 108006967 153837724 260886904 316188221 715501960 846584338 865416093 112880843 956500758 794861276 505024747 605536858 593521056 474781484 780186997 64766875 885647250 701974053 130183497 914112877 398194500 308856094 28821058 205049547 385213942 585038416 563336691 923257563 572301352 562434437 980816922 999999934 374324321 453412077 820428389 579125406 244251012 557377646 420428012 461804937 697518597 721218468 575765052 39152325 353218279 713726544 749783388 549486241 232920693 564913502 72029415 870053308 553109190 469130765 22247715 723982526 224319442 28755062 134778937 307230930 996549949 75272894 85837239 969514823 485621113 886824663 670384700 75586194 846894660 641393498 359458211 530076226 289698207 229471321 671665629 329047125 204739324 929628450 444361180 859311424 184026427 578397692 481317525 906242900 754721058 352533078 945696029 865586301 914189207 245112078 557425452 248347735 735042052 841649671 432456383 442355024 548915596 917730569 735604300 11378514 619056723 38532154 477860873 963421811 612714806 986546219 204528489 634843625 844851625 296648771 95466048 425120157 489926437 167294672 298845607 25935210 546923497 503621910 675863609 579119255 496794550 232756949 869277567 880813683 806266678 31680030 444142239 454641241 383447822 282558424 191179318 799460278 938750866 463367381 732594630 412638292 527783290 8099618 847238221 625201187 617142286 520012835 499623758 660001718 248184054 843531509 762043061 221508237 34433839 884371820 372382679 277084254 805118878 179270788 104383909 987089039 814826171 211611959 829773948 782303319 26151394 931784915 353944055 537862871 791775588 956765620 97700070 437348590 284180152 626786634 241685927 615416491 298772003 174979388 941138632 993669083 882365905 292394993 726752358 187390130 22622788 221339968 653973466 649611423 321608587 221928175 732334080 509537675 300158220 972066167 353790478 786999064 16938072 101792968 427786872 371600484 296604081 991341081 264219105 144863212 202611467 633460979 65921840 992814515 566202470 602371726 77060928 446331525 94242782 651556070 176323377 945287436 647265181 138935452 138761714 45132602 257820821 585668837 159910217 990109288 401265125 971220687 56748519 649389656 871942082 997545059 67716408 271150748 867526087 157480243 804253654 723372672 676844213 741963950 4965599 361130667 671034322 440852428 547721486 375194037 219445412 934334312 312423744 931280548 636575497 690950280 339008532 259817292 320805661 306148077 96348028 242356460 431752776 350836951 430600557 588108365 695757872 834588818 186730163 181947288 558117407 78784545 38953991 20287430 853192027 298456958 12809014 518068097 666256326 363070160 371592349 503098541 590160621 718410233 26259607 890802507 960394654 423299759 926017311 888970378 686689553 157120388 189074225 837197042 457910929 180793674 812066336 458916293 48148775 406372135 783889943 484901576 109991176 241681812 555344552 642386316 420793174 867686624 282548918 868134232 51981843 366932302 260289608 922007468 306260601 967294420 620651088 347216524 591881690 99499739 258170046 832461713 15472287 165982893 796143226 525299808 336589584 616116779 833521830 429345729 307787276 104210072 400339711 602069260 851993753 260301381 922878754 438886608 940613705 851779700 813905142 140314441 975982034 481248868 87182516 890137359 440271032 192093325 153783235 22024381 222161536 250783762 437921014 138176608 630914059 265502397 713509776 164059231 381192581 195889643 730035304 166272934 124800063 529049432 369112333 50513039 777918935 743883612 387714946 350440857 271995713 878862600 64457000 155624582 450433693 628157036 820793984 908966449 347078705 720801865 297558373 860326800 491731225 486470950 434625697 233414124 444306883 148569430 34183149 372268115 148381150 237009190 297033769 280722139 246896350 649727068 763022797 172472410 335529558 630701453 563584996 446054367 245762586 391716404 997090433 327646585 46389871 582815769 921634748 586756179 241396368 886712464 271332393 296829650 96103936 816043974 911094081 690970022 980253241 373299581 934115165 472616253 200481290 982815154 434176211 938612831 95708746 338015988 41918325 392364504 995465559 685359528 183685553 352586988 665101840 99472128 885281480 899694347 849288276 361347487 357976190 233850827 535088921 960333521 493068269 543777653 331716419 51196014 747574888 352640870 532515515 549068733 725797258 235906655 927945461 671551575 669025509 711119561 394386461 118298313 182858214 297804631 218447992 550952871 336258989 861448563 4577029 225122545 490129910 69083641 402332661 528584109 374436186 701176333 552762540 854648357 528738534 284498705 671302800 316516897 384564441 705360645 853815350 426318232 99680815 732862504 756861956 716410892 504006233 287458159 339607498 125260380 686906302 593846012 665703730 615929747 523443586 996735389 252572697 251313625 727364733 799854040 936975864 967904329 397550570 604373965 939893747 51834670 381805154 795675200 472115646 346638172 794836863 79747946 62508490 635189790 207468719 645279505 352181524 838100184 49610056 474604088 871779062 675033321 717618694 528774497 930379011 814078498 807578360 966999031 259923408 122492867 223680009 634995666 605802856 199441756 474348393 466012293 421413832 43030500 474021390 474849886 87899020 418185274 19417476 604317766 36454157 658689485 110952162 599343120 241373743 58116916 686757558 300514658 533299438 713491883 283236933 86916279 591933355 252299301 563454626 217759879 582691712 234354453 50444954 893201269 823397591 154860037 725261 794277954 797492210 63173548 671686252 447078185 210011398 748624500 400114998 977044017 314374532 681277984 395540952 397492928 595017493 446085322 317887109 252421497 53590112 396073278 390183400 50801558 316518381 879676205 249874949 596233547 312262126 587412386 248133222 206118000 204025345 140667567 143606367 95122459 141156292 146281576 811269081 322059188 475608992 308759710 632041315 50704745 238147557 691180648 392987057 736058934 376634897 751116627 401301422 508944731 894377337 781250455 3229951 849944437 61256683 661353040 687297510 55905838 136268414 56980227 265291085 613558465 447893268 856541088 388295067 116991998 437531716 326721128 497717457 14347515 560918003 905997970 358433058 869011118 12366161 439551562 367964563 599910535 70181108 56881723 38779817 544729504 701191740 558448783 577825422 262317343 868497936 915573631 202888350 4802637 808047502 438226512 520262064 470371754 640107804 610862513 460830302 838272671 290963614 923765392 964248341 166580375 462609284 448348264 660284953 936072977 537553536 746482352 305873991 534452936 140040539 950241723 58852531 267751220 77240632 268259998 762417215 574804013 834416579 771697718 868476621 980387274 294774393 367645168 330380596 396882879 14237917 170953002 996851374 331527041 466091504 442406210 268537333 172194450 519657816 35057538 341579763 826089908 70105002 913495800 162387040 181932366 520835225 957577868 802704443 565166637 865163588 327380557 205289382 6522906 213447851 249286085 292457754 18637364 103833589 640607750 444350978 809700163 213823435 503388935 349013814 941789125 135896528 391362924 875214548 832712144 78952210 866901431 973444966 758515965 777447095 195508552 117205067 532545077 42541756 711668754 506513732 953384055 779084589 347880088 926468746 785771401 256161493 207175468 119249058 237518060 217464091 206359487 876629025 589276611 306562235 968865177 228986721 522178672 526786463 143333945 265957701 907823476 486901923 350043982 580766077 447423558 300476167 962389736 745958066 41960669 484191764 551371696 401761487 295623977 564951405 363943893 16667536 786019077 331452017 833290299 555576535 972518617 419350843 8525016 666509330 835143007 424922006 984609957 864375928 446968811 554775799 680219145 719785284 894189161 855526240 709718402 732237604 415196793 598445767 739321454 261682829 415608564 560202950 599316360 915246041 812522576 891081469 520054108 580299919 418589090 869106735 719985424 574143512 911408130 201856636 135591438 401577038 3384418 962781408 226165016 286554757 698587230 392156041 955947004 182646485 134052253 662733942 706290414 105985917 664869428 212929891 605007621 557615174 730703161 483230588 446560529 327004115 555449532 732034583 95358003 12108043 3483890 847336253 542371999 223060562 10292589 708828382 780979860 282797272 880983600 477068693 163085474 137726412 464615816 733129966 532480234 577118851 690591945 585145220 382346654 659178574 171907841 452201428 76190107 366392008 941008718 511562641 804148629 32037501 293978728 849062178 665012222 196529916 628071644 744788521 438878864 620797486 300854385 666438492 684538884 557128547 52223243 470045828 147949099 282557575 915755580 670761492 375824354 866110659 320668903 181877904 473416004 45332873 261058092 318674923 50877393 166758336 764634578 331041332 343510583 491970689 36087012 762707891 573047448 739855179 510385737 116244357 588062207 633395856 667344179 935878884 787387482 764619965 197893894 886833661 456899515 374656210 65071520 200893849 916366196 586015083 648462728 951528024 936201676 588169312 692486687 964698218 396024573 14808530 37102457 303751147 443241790 964823201 739955640 770598089 943308367 903664878 375409574 302305466 346442477 221335856 904673520 75684327 990862448 382112338 3954422 315148158 927665819 933233338 984394931 678221785 520843870 283519634 176804729 941380918 99366959 515525807 853584968 974161856 367671925 987341609 133254747 380264427 12914571 508698970 267472184 812862200 350037456 735297999 671652009 697485665 7327839 283541970 889823510 967667266 780394344 565302711 205959594 756571743 587571888 827174049 730124454 269152858 957677890 250283412 690791887 943739947 692922051 392530748 720307709 760499570 50833024 775644930 683181575 856414147 328856338 637198169 372761892 804237894 546622343 409885044 684887656 829476402 492429855 60715870 531774194 96050938 584247298 410603875 200343387 828108652 624688819 742471614 877042446 90391438 987688768 269209657 622268927 272788237 930797018 797833996 190892640 318060435 594555725 857843955 965495242 258302945 702659802 27175081 159635344 626909645 648350456 232696728 239407326 586676291 381552576 734274425 925265669 276378282 618508727 301723366 387534306 147978033 139626300 924123961 978346226 732330688 150332235 258726742 329428765 968528916 543606531 1337257 311594168 849185760 865723743 594786925 257902461 398904340 909265976 691595964 128078667 32933999 113439388 323716063 563905096 350715746 620336213 153986173 206977034 834846344 731038062 119727096 694979336 380236699 276393249 519756018 79389204 442423534 604621524 982607978 804683610 384607413 61449942 446951404 939266142 582448067 696915805 648959904 68649459 176084653 332022212 489394233 152514727 487674647 701035312 408190056 293461939 96507823 28765160 540315787 723433171 452312139 859174642 942406899 479874536 553827998 792344390 351407163 68141539 302362457 70518025 772153565 33515146 929996319 96428855 95628098 384367130 822730984 702925168 913858103 257658602 359809349 857564884 293928607 375743832 560386475 45552075 283514332 55762235 241201105 429138399 799309714 947426330 175899259 324383908 813174330 618880367 995194588 588443094 781179635 471873210 501612958 483970042 584075813 636068963 755876182 291683957 980615310 896420254 361274598 236228911 208295723 503808754 73359191 587912511 30785930 615766765 64798997 197473099 503226538 926885800 705763557 105733356 858471810 50916664 548860446 786246971 485142322 697343885 589141387 969671444 637793702 254546741 898433123 694142270 17703055 715534380 718621636 594432105 188415957 881474605 844713409 197895949 435343938 407755662 476997933 822075956 463747392 907636305 922724220 790553869 106066862 250486427 833371817 524367088 812785000 834913074 199274904 623312055 546010751 778439759 120685572 403736244 969865103 541198515 126410064 698302771 963789424 88605511 388460126 205098384 927961698 343987922 734931307 750692628 109027855 135259365 308954805 822065957 871323974 383526193 846829554 927150279 600773331 566651103 817282707 189227830 541226224 462211632 651906773 331066995 647477457 437582924 308862562 220112984 847705316 215247702 96124940 526594731 447758680 962289749 273465889 465920916 860292840 495616320 191816807 490831581 378536708 593075860 996847626 449135302 496367023 486189518 929455480 47231700 368974295 958184141 219093867 224011709 227996889 732535538 645042611 329012183 390135848 960989056 216904349 824202303 609470627 925345248 255311974 4792338 86507544 224024259 365973040 39641593 331544643 32634061 375818754 312866670 841907742 959317885 66521551 851330400 72589587 881020782 516786409 105115601 72046996 445890681 167248886 41991536 623302053 283349377 798941175 469210088 133572202 941553712 544652607 654096825 20899675 517635121 988267408 795420978 834154413 986553050 926404270 959833151 845194545 166448170 470205100 170720333 482407803 318007501 628416053 983018627 575145322 915099848 929528883 264795568 579165832 331414714 845093569 876292729 572038855 184776637 110950042 196837439 690983365 949898438 755332876 162534722 200761176 506522770 374813937 199239892 553892344 696128518 81862502 18781359 214608834 414910778 799677147 728667450 355642484 88671626 356516530 60087170 796508842 879436027 952612930 259182394 52120682 25658415 121363133 422542278 389071995 485552506 116803802 751231719 522986292 348053054 86300942 111151789 457850088 80785157 522969691 462459590 729689135 719198130 547899711 968044833 881829271 306736175 941779466 946162315 443384585 557965 774996125 524328576 886378926 662168439 101091096 503114639 471890963 276665701 339756489 863183401 886431029 495933326 339703947 450448991 971990767 843247213 282557158 868492797 497897770 351370326 511059069 381761276 437428082 713596775 470170243 167230681 396750373 70134760 371113954 400491845 915561360 810999857 585651621 866541345 460195344 757395961 425005992 861166144 59062671 828731200 64027393 51349234 131899484 142883288 902072252 902054973 192262921 388352857 193231183 397015115 560906209 821581978 146082891 801890149 470139462 936572470 903148260 223388727 716423889 488831226 572255267 878254983 645745206 233924518 484155719 83936583 978042728 79183661 278665085 814664119 655065935 249424515 755331435 94810301 796021952 883778917 917972070 236403674 650403246 83673847 613097303 524584248 586832430 820744377 259875118 705914989 872192865 17892375 599203342 318868383 199427944 314656527 426545759 110803763 212300431 877489170 690335078 489770048 262150532 509900315 693712287 931482857 988483126 859152783 234337808 606232859 739116698 804939836 983783562 730161202 957458947 905823458 608909238 443974123 837150162 307012594 664558692 362569682 829681903 308175677 40678057 674965683 999516850 39812712 157250063 7218027 296388924 165030696 820801886 29345296 169791588 880691335 695178664 398298933 152578475 271042784 936591693 770153362 101194792 436957308 3219543 692179814 679148849 56628261 118199457 353059395 895333007 203954361 557969306 323129241 159537257 22144108 571993420 5612852 30082646 91422513 952846527 599483433 698948244 638085096 694902470 283003556 528225717 619983832 764333082 234167441 139867488 944011674 400657093 296549169 192742709 405767422 908175185 889707080 78149939 147695261 838195707 621507805 981891375 724962325 727049142 885760630 417567091 817927800 495785415 28521949 443484381 503987277 146738770 342600381 237166234 505572096 10539289 98541749 580767674 193790707 514374015 771181862 916936790 598910934 482617206 397456584 968534963 551924289 443939382 366679096 76099817 804424053 368774380 2069802 258606432 431672228 380642431 670727476 304938152 466287639 866669319 993940023 881497590 878180661 694695642 826129562 452414807 369668120 216177935 359293602 211731156 313782074 679458945 440232440 141690713 367718405 526616197 10838396 548052796 893936968 761115632 987993921 624496047 701279987 321004325 118190568 840705154 509307347 992680791 571415887 952143638 771323921 667097689 258376033 754362823 117301290 737739744 21695656 246573917 974669592 121675878 310647213 331064675 899262361 474305111 908727908 263763865 682596572 431578376 793507512 936474538 472978706 109928166 202541483 147004504 992504475 671860214 912857712 130550328 157183195 763796583 266677313 475930518 801323571 619682822 360031054 81822785 396795081 276234070 130262915 517440621 770615812 423013820 722232994 362027026 142315467 259227381 278142563 450184191 155368905 160428702 643709799 40815278 505486511 635328659 103676010 589090851 804875215 513684214 122695880 237428303 289449858 418964977 55110165 835385967 218421045 341322113 258418518 593450519 976859399 633219157 231364210 560096191 231718100 186776810 222829530 690201498 162700472 353455478 695236714 453452640 366834740 275635977 463479168 304742249 261364500 8442084 247229605 348641455 580238587 96671853 143221020 997102242 131268858 477761963 396754274 122567062 8645161 874167972 839913828 779576957 578786927 761208977 49185454 175667200 891197614 555142050 275189768 343161584 303162739 765093450 915060221 768933246 15201601 710222706 833778669 677481964 241610243 40942298 157596842 736405764 230853821 853804907 582155697 287390429 705540040 280909718 730307999 443342920 91134729 152915078 163663546 731307788 666714229 370262176 170699522 17905823 977011712 338992242 478041409 237388826 698420106 181999989 142714013 472783995 788072160 350615629 810109806 275961749 477888462 479858231 140275153 611617064 403571008 514436080 73339674 17502082 37881964 701150835 955203719 612480338 117485085 75785122 628848682 805841530 4810696 87602861 803280963 7555541 562622431 919122424 277881465 68838539 995106037 357035426 193533691 440174819 736894804 185095190 16682374 64507487 976928007 188248651 215770070 245020503 608179227 31445351 337619467 693566370 539277590 960700114 341168792 773666195 672645909 708080665 677912237 782367278 778359454 104170189 48737408 316259602 994769384 617599206 620960574 621966811 66636832 35581572 354950469 312489228 57277450 79956283 566383826 183771073 93805318 575870402 915337254 425620584 835845631 600570313 304723615 692506003 608387952 265494733 865947040 653962768 960168394 451098967 307701401 902011328 588636838 25622861 984498141 745878064 147054077 630987651 590542620 720947022 303260478 815341016 220870557 283349898 170475834 38360087 720164154 533917889 286537253 704990892 651787731 5430727 644861789 398274166 544081063 337828744 255971342 240234751 475462197 111259951 328580713 139837283 761173961 272422995 14475791 666072931 354000876 653315728 67059825 366813552 791315823 601986309 844335588 734132369 368585779 673898644 246064513 910569231 142553451 83812632 580005441 753837169 339368340 924810135 680195005 969636908 241797392 80714000 592422116 298806904 2097888 377184017 724878778 72805052 943855068 454048192 499443026 42208759 518053774 82831653 814607402 952617657 62710447 480321659 327117415 123140158 207893055 878438357 156359969 4264565 275035431 8698515 289117798 286754389 426716416 414162131 974281330 380814093 372507631 236294743 250566037 468786513 128756286 204423401 590869702 732134995 79256765 704998420 354037132 181638725 19315424 267642674 396616337 112967051 492270286 696761245 952254613 402318722 13189062 114920382 761076121 976988352 258977040 558292702 337562419 829023891 548927178 25256342 146358631 304655921 427151521 904635831 734173644 985072263 998906985 795791187 510631289 459194892 628583101 922405593 718366578 934590993 656442078 366391329 165509653 805852569 436536585 646616802 636066207 833155993 2722609 266574199 928512104 455913124 342442295 239921153 276977536 979513735 146589442 526584320 461879244 746250406 313810863 95922522 780807687 216963033 544306770 846989820 111794582 496378105 98523271 195310990 217515875 629227660 697512426 535245400 105410325 152382377 101515 483261557 654696887 814550063 597011289 634765204 997645144 359136966 477205862 84004174 130934978 415778538 492260795 1884189 694388941 587227003 908164142 170012703 454425200 767949561 729939427 758967132 681468522 953647983 106736246 330105996 146768213 473942082 787369883 352420567 871034424 634516747 996756415 256183878 890237494 587382704 630511039 871560249 241345421 300155511 695616532 100599740 276273624 435389697 128385148 19305545 143401415 524449518 690119586 150116266 624375350 57263797 935806734 660480693 720044498 937022264 452867889 380729719 564174011 5484668 517739677 705620176 280202971 815008112 932844566 865526686 926573595 843320237 220808160 461287202 70048900 814618283 424668571 614905858 683286042 53570627 604443336 966675066 711385228 236836525 497481327 253358764 981605557 121552396 976059606 219147052 778032102 152198263 180684738 64366955 80073978 471078415 557475108 479727665 579355239 952913421 725480287 695183521 129194976 195143898 189764928 425546863 807219858 757330582 126322175 976828356 671547566 14171409 927561570 642174269 936526109 280145526 945909313 664778820 444112136 829667060 872109080 682789294 566857742 758695903 375827898 471254110 119211717 634682813 370903238 731678540 448713926 712251929 403172030 332405321 468379412 944235497 741584813 78706902 771717208 636756049 860182721 877906727 1649847 417590623 867878643 665764600 721641910 823187972 444608898 144649387 294651427 219416962 728332017 973790049 862315373 856831741 554417534 810384612 694008376 139850146 375649816 139873834 250887571 360541369 835088598 857963851 562119492 110776380 563807042 603069999 693842930 969494221 971759315 502953071 845349946 390148763 555860756 966174820 810058099 153674137 346549226 255596745 786697223 282131194 949839694 497597883 481719971 347023681 732152154 531259500 466956554 266595298 612908806 657122542 888616029 957653929 648072414 692426570 363127919 34714126 362445614 668266812 245317364 889999096 544710780 649649743 437786040 863988827 18738728 397988194 559756202 595299247 632986395 981682138 413963670 368669845 739731829 498166104 575721757 901191117 283234496 813307738 188419300 861974967 177790174 991422675 987870551 114797872 980739779 72986522 7961495 39031319 713414543 208399837 104893091 238941269 356062330 716725094 416723829 142880952 357405609 918149745 464338905 308864932 566468535 805343775 312389913 63668739 764575721 311743278 60662637 311927257 740673167 320688770 302497996 701691641 729496389 233169610 917813646 528189757 371648167 248462226 716335642 9588173 458219383 821232079 61203429 691257962 331502701 112777451 198764383 936200200 189951414 500875691 367926361 866842974 669920650 342955653 149167908 261814271 31602006 172067423 81908416 670054000 216455004 301758784 700700984 537445412 975381079 527771564 441597628 799579699 225262645 911743475 365100455 538609656 864071374 352448046 492680726 721462137 188907762 571104295 639341158 784409040 533900367 352363412 243740033 745550939 561979636 772563456 434921398 440653746 442614833 221251027 915232973 104232665 709079890 709319094 709035269 844108546 162752819 795801317 564399537 291377009 624943691 55882643 157726245 817842646 72280413 436881948 110573060 280854544 218998155 70341094 744357204 281872601 742231952 113414344 971854613 524478441 35205354 381577227 334535936 671287236 236788578 326395116 326662942 465382620 27289875 523793855 918335405 659884858 454646002 662896940 646848505 621738576 992348157 10486563 992155456 596590554 659963728 759630015 27976765 393542013 881773700 570399660 233700593 889360418 163337688 400646316 414388463 965707696 863689758 800912006 305497703 677390539 899480320 648888063 661123337 521608069 638939546 294312202 12123889 686795828 580394640 358107788 17901616 494686404 516678910 724030502 54085676 48977229 942259104 717276362 542863080 976766485 742868903 33171255 932608562 125064815 910265534 138873342 627617223 223730062 119492464 94388690 534467209 549882529 63997407 850978930 107520089 709174284 428955780 200910073 145939839 95827661 438700023 843697552 441792703 953846140 879050952 614857488 203626344 358597477 475107912 318021369 431161800 391316950 707214632 50046162 492745462 973797806 351062543 275396888 389483397 975673628 64350755 573348117 293360251 965455486 399061835 144754252 567553264 518879811 332899183 896983287 919765213 146771905 420799152 78524994 875820059 16406630 447107477 313643753 520001625 76924329 798193676 112800066 443048536 870402109 41928220 212023597 749746528 962303805 656770732 759928396 969309288 636187988 140016752 939943850 372632395 264766268 654452864 889378368 474872500 222691695 430963873 897367705 662871687 737142511 934041455 165777259 304301007 583816268 810175874 983988750 533173369 270893502 266849159 308576886 833184194 302308944 904429070 800830140 955309966 845100664 4301280 746248111 566836721 919303435 111643398 958608137 336636929 335769891 593681284 999684770 372980903 995643570 779003711 638987567 66622766 664270950 934985092 735276271 373058905 1576726 486131617 482246747 820040944 612581740 466826474 444531277 905203374 288387517 404052148 111316357 679307437 850759666 124681004 163547149 730410681 646167423 622586073 690176530 19304908 323159822 263089256 189371484 478258949 236400367 980839229 959554120 804064941 301264370 181080301 568190047 652399466 753220160 658820856 186035734 520993225 349236658 655882022 307405434 233318970 490385808 580247363 504118479 836774638 596686127 168854348 451632419 608215582 347052833 553053973 118877764 588095754 911746596 738019464 301354487 932385187 377175296 784633650 127026326 469956140 823716289 697538970 972823790 151886797 492963717 687909944 119312445 398504903 736287590 1722457 723762717 873399711 782926075 237636346 571108133 569516165 282040061 920253130 539942006 497137897 660466815 715929501 221506679 825947602 178094533 689684346 452752583 83925963 500936518 564258301 275402635 872077347 885716677 778287035 643913185 89684536 285559566 38816220 506155102 260414522 345104240 693072696 479664676 325447510 11200975 747262452 651062804 239896819 809717298 80788626 910556708 340474813 912575415 200814023 159863591 29626099 971268472 101564914 312491436 922488952 250843128 916236698 997499188 143938270 952411917 304204105 500970080 11277189 315327286 273378437 822320246 513204984 264666051 143004338 21607006 777447940 282784053 931426955 496947197 312624645 341229756 922769442 179167339 666631861 805801937 705067275 609820786 861965567 414229554 287286804 953099312 895910678 734958734 339774691 264808841 171874715 693949661 418627815 746495551 712188749 375539709 81943815 920750043 55880525 863812904 131292756 321632902 968157574 816639221 201661842 19974769 879618930 256307857 770809421 110287612 791246220 605829 314693399 348247746 337091723 446134006 211485323 575346336 576347671 575982479 385133334 935290367 214687653 651245076 750528190 629606970 661515595 395367789 789684789 234365241 383110655 171511543 272857664 383705969 597415242 593613105 962860932 756156336 918614917 54248395 729928029 427164412 459483138 145855222 473587887 573434869 362577609 703491946 840587588 931560482 300441747 910254773 668876321 477636235 244972135 840301841 416775007 302425113 742313961 830740767 425765286 535889950 532298404 808702610 100314533 800975255 982695206 83749061 527675949 675539756 108269532 836245946 497376296 301498400 162419905 804591499 616394474 843355187 781760824 883457634 717087976 111997989 780653982 940777660 494804182 856488480 265554352 347629869 943865920 573794486 436302768 838883983 376830749 754140376 803320556 420482066 730102631 62895392 956498325 914036668 317042704 255765866 83567342 691590601 934354614 118577586 345064336 381115539 262398987 547204362 395006328 178386933 651669880 705489791 937135900 570826086 288996467 603994813 395782574 973607663 391740959 122980162 833227761 640097727 481408997 498303295 223018584 617866969 484341419 568712340 790442359 884788721 888285507 234900202 625403364 61610242 271633805 312374299 480959654 740829988 142746383 978947830 303156504 360090137 509585404 653478413 380163928 782733098 564283544 427436052 774218609 122249774 305200438 255618460 852992534 161546837 697184085 359787309 352375843 272622086 603123979 251522689 553941162 297346627 493892064 165661339 9396466 332504326 76181258 540491671 878442940 275537033 812592318 25826524 739754732 898502188 115003209 898031561 90658553 175855221 533181956 934976361 935683189 854972667 885913488 324700451 482856178 900432058 284299066 74496419 824761177 929125072 700664847 299026375 62500009 795192505 708416096 201078959 371384714 176350941 549900230 206341639 98161770 93043545 203644922 559985902 256859531 749856848 85790290 901177438 544118598 716773483 840252448 923427431 493494087 313430010 862830925 804391494 923247553 374831832 752302376 704829064 690927941 875419835 303403297 685108805 246633817 357692301 642856966 894886012 534094995 390471126 507601730 365196684 687093300 160423963 258300190 855492045 758375653 390803439 304780044 702500455 894473215 100514675 619986688 760158249 574102164 969825685 623901608 159136704 236958422 901430935 458890064 989708744 311014561 25832608 203512201 744636602 863667089 232746491 891639117 865130181 462283669 505659143 591420039 454332561 888800064 768834048 986978654 194728977 824478212 286990744 681607690 908900404 24876560 296921431 434491016 28762471 835447430 404926687 373454944 369228013 313414289 412518249 482976450 873557078 886322508 652350952 187854654 386061091 82130881 536854975 986332361 130844030 83328529 577804023 488043130 253421394 366527547 955028972 408622549 262307108 652644027 143322356 238449725 580985356 557718002 770204127 228869440 66747745 899244469 80829737 476054756 130092285 604559405 798149664 549832181 130092429 501676976 719840864 897334730 53159680 90358909 378909522 573454336 630998461 990262060 136171747 917711691 220735292 444600165 611451759 5879166 468517984 877751657 592007673 40312512 71926130 76255020 232586917 324113747 444129846 633072273 976755699 850244244 652240750 300315735 148094250 339345464 578022711 690112506 912500474 396948653 369760722 542466211 323575397 2281750 589946196 539209822 712152272 526990469 264355166 191415822 205556958 490452673 70321038 650824214 219295441 170458374 114781709 87336192 242094883 247347424 121386763 521905835 5562124 383351759 470574065 492102461 508516578 827597218 122008676 563567220 28450408 9413139 189846151 972489811 46565973 510166070 965924057 595166663 776342179 606724550 46299209 139423107 337946639 481526049 684963706 982711940 388063836 560963290 142121940 482380739 106690234 325283314 950068097 765161871 966552698 907754178 563078642 983170117 986348791 691759608 778082678 493778298 12340236 606225701 781628907 134738446 945309094 251623034 463136193 352751920 806116321 622913488 772994345 122271723 509457807 47934525 957717383 903812313 167761693 694785310 213383695 21006243 694177030 808273208 745330069 853598975 246851395 790744892 628480508 829277432 541470481 705770162 427594345 7175939 864829016 747622350 665622375 997911972 996881249 82299635 894656286 287739362 465494370 898059022 541758127 394511127 973800500 289938002 650058508 778529334 139739696 81275770 652560739 353455107 260208263 362681484 583233786 817246572 865484170 713242684 740763931 540686643 604130463 505101885 428043373 692927941 67715561 898395650 993664759 741436475 772138549 974051092 52048957 513234637 683545409 647073393 912499978 793469677 281659498 833562056 13793456 385379403 578175459 188704680 255778660 153105121 582473015 915792169 444855104 153669101 113800242 758877644 959293491 348882913 789284854 898821930 900880784 732731047 840791274 41652429 510641804 559621407 703589485 54266092 275038895 862148420 708349779 916549338 18253476 730226179 213497009 332222450 123921435 592860549 565344200 351812898 827725138 755777555 890325405 182510403 101207387 277758205 578865386 318450627 892985482 511010877 860871 742007477 122100040 85200338 627195475 98131885 512791289 46021519 150433758 846914406 460276838 490712436 230940078 129933364 640549863 264766547 486149241 885013866 318256737 44609318 891621524 302041270 245447734 180149768 635870381 947353203 418934494 7843195 282160245 569959962 922854163 675614396 717813071 832375137 396752286 862709846 375149006 8684638 197554276 838277083 266094044 852174334 555730275 248188575 612429762 412816867 696650786 919964129 681956873 79717107 433804025 454548859 558410498 45212412 135760989 539044814 332190264 533505479 689292325 935924384 26148360 311471807 643920898 918220994 166469105 179401373 757972873 72658196 613197867 432283263 377091649 577182246 968550244 780977438 877679521 173780797 573223819 997606439 910277037 129985451 108458758 192304789 828285121 855301334 232335636 883089696 615508295 473158021 172406085 254491874 274571597 647206195 626350745 566499590 578647175 925712590 893021993 239837518 928001482 637749393 557039302 739908339 682625182 424925489 170163304 233026071 938857259 915059185 327370540 52989472 486719157 470720793 863940122 424459426 454756754 939659397 917634898 535831954 42436093 812003810 498362099 785088931 34070954 669030205 26856686 437033425 424516894 652488747 410561899 273256942 427834441 407199072 882877851 284378744 595672368 669769265 582166804 692976204 988336786 242328215 456017709 633991763 679635398 882140517 886552335 238071861 341026894 9446134 143556044 138524201 173046898 234454208 605642680 602721219 704505199 244300436 774418104 379055314 528749203 919823210 900108324 57285533 724125955 190055448 217126444 464356722 482067487 764165030 505404924 290581649 510978001 331091728 589844164 266039769 996655212 754067480 636408892 602680867 239305103 409988275 178490384 28078798 246622032 853349374 684918098 550075333 111228060 893749561 277150453 114451124 963297638 948194644 675795308 976488103 31937255 744569537 567392985 18815482 271477542 274497564 165006932 310372945 57880210 269301730 969991824 936638989 503941680 655928572 938933963 766068633 681925722 124060771 493716941 815905488 595608733 601883903 863461709 194791729 11321880 813240170 108596672 375713027 949082578 173865818 916531953 954811478 790816650 61690806 177622616 958768840 386806420 168600126 758118085 51940684 229497627 141297744 357861181 433331089 577991761 766687141 145380867 247665932 528751809 1517600 950052688 534416854 832151334 50386387 723391652 610918000 72892526 687538063 448313500 934442281 275893342 748663137 737168 556207840 552297315 441506920 217728365 818280137 936945783 299613279 238056500 4445098 634401070 532362288 1539940 261797595 102448748 456003524 243138725 732863480 875131288 26955106 531776936 477932703 890162384 68719143 544820440 538889413 58293865 703809490 194187453 133900532 258762528 712921629 754774274 279977475 644420051 247468865 186264845 424954412 884712059 447075554 827747003 58397183 868405713 851584648 174354010 572811672 339082049 88519688 95235 935429505 265173678 78819351 917234267 408965728 468186067 583566490 514455481 873405974 613087786 59723410 491030288 256329473 586986221 63167713 628737829 966843682 50911039 786096417 402838187 322340040 48137316 410861171 922718793 758208852 870859478 96236980 393779887 754342253 643279579 48874947 787276438 662956547 114559553 975567010 205211005 468170398 81364597 885170244 480641820 306954421 778652816 205622010 630014671 29887197 912657756 144151024 306856829 393545989 250017542 31175103 643208098 964727711 23503893 42107355 597268472 424958338 709819681 246082848 839366189 330012733 968079398 456362144 116389108 6279977 497357503 402802850 328680175 195452631 123639595 926732811 203386416 702252238 671473655 189359354 732171084 938069200 959965161 416978430 813578825 739810193 876651947 909874236 180663597 581212190 590679656 843947473 159985831 370448556 160786667 854122301 58638344 201969273 990133332 876526350 731881922 955363968 138053764 888902781 328430405 713064555 635399410 155189609 882047677 577531488 526726185 784936151 886949036 63089405 391547095 948275520 955744926 232805006 512285666 163535784 815020280 412183529 662313028 596467041 900561748 225318068 756350903 282655460 861833561 824561661 71938656 361593786 421479790 826685010 922459543 998163859 240927895 88473606 9887110 139654723 31551585 249896392 787570382 329723649 584953735 998442805 450774105 70098723 119454426 674054818 435606256 181401894 728614513 202018512 191415204 622458916 126198972 797096201 912783646 873366545 940225803 579651948 988998915 308271431 975935611 158572344 688254837 752791099 347391671 159171376 913183811 661289102 180762858 160925284 241644766 469494964 233288454 301027135 193566256 788565293 241397342 518384381 450493731 6730231 275807521 767671517 871850495 86911543 904994923 866582787 854288484 293949418 963103371 869424273 912054510 900441472 312973310 425512016 520322099 537915219 485012932 450852030 391139699 517670255 992721851 185206945 743277511 510618135 607731954 124330382 24005846 256070505 889126501 126317874 187218840 937957069 273251673 217877068 719577100 509978706 950958029 348048567 801423554 313706828 728887822 654252591 293851137 88474869 57810910 546046141 479266150 578475072 622820952 432989746 147524098 682169721 895167257 403448672 783784403 659917611 744726285 152224958 809782468 316168503 240902966 824854110 579642020 977917451 38848748 490298961 593248975 469215911 961555682 355173650 190144523 341248619 570948659 442939382 754610369 419127467 505939017 296550233 941119154 601618794 249327830 493820409 531317806 282039979 823885128 850588970 432895053 287211752 750241045 622255161 125931684 305287622 553854101 988061188 251305607 572457481 280195768 153861942 482218993 214213312 721886220 422801692 306705473 592626411 308720684 909566907 388558826 463719818 393316034 637915554 305650405 383812953 583368196 626998393 259271849 810038076 77147860 963393038 599034124 63336865 305954054 61177008 778895771 833842549 579616784 945340315 317830417 601509851 419432008 722053384 717208170 633287843 832726846 515934754 27479067 240245805 593683297 393399840 742738746 86420814 157552340 808682907 305186261 396967753 774024694 69631353 734640450 580854784 90144643 698896322 707258055 29764873 584321945 899162301 125778234 629705407 817811178 518318326 145720961 160496910 396105309 743767302 433953251 462644880 494967130 666246419 280452545 88047 366117375 694015553 491674527 675321185 615694583 37587659 708180639 736792183 142872315 739515815 864856526 229730658 363063743 965992709 654355030 867101847 438751909 609534881 383437667 712687150 907276036 45903693 604080521 78221885 732471947 993373233 999308753 920041732 327733625 799183867 809447010 70902765 352315215 135376842 735143766 39251537 182748136 433696323 710246803 270643748 113539012 242704547 643793201 666346533 594872685 415781934 902886398 956565445 612015864 106197148 716709288 8144866 262485942 264406230 382747795 60900089 723209989 604386310 413008602 156344982 948323708 623381030 231704993 212151789 824144875 175597187 263736082 661072732 500737228 976338656 333457143 915900827 293523464 917814377 953865394 355001638 324311530 561681592 122190810 481328226 799297302 659458044 908635178 213663232 471968107 852315058 162094315 478197611 618390000 367708223 806426358 798348870 713941218 355442938 809405231 338022116 678115154 30203049 33897623 346145089 828920048 336658134 320545908 375891051 337887826 77309557 622924883 621788896 886432403 104028609 572799719 510902019 263121476 28163219 217602735 788835191 410947605 625256440 94892898 412076758 719135120 546299762 137119719 397200790 247944455 210573829 57429821 812026808 828624300 922888601 357664594 401817532 977063857 697894459 939814114 569842165 419499628 565780195 918487056 462704556 45618765 194597319 392053670 162358569 24539500 743249954 23154714 866765671 888311502 72173057 774860350 832448521 696806363 575654891 560184731 210722787 534953177 32543728 744962527 319989873 206525931 411642759 213356272 812197999 23396835 871314513 269189731 733064990 955058316 863774281 739718368 815451613 739757194 978732374 994099861 344875321 632839904 733466719 547427332 848044088 465854457 815660024 394686390 13127324 654199278 914572890 258062942 240312079 364189073 316730519 754157362 38868453 270286117 863123167 576330092 99440123 599836252 349164071 615003784 252680879 646191324 552353897 405055756 543941515 893798855 288805757 950381843 405774371 591823004 113700015 239367711 520623043 316234681 436249337 249477472 325994558 886585016 137709398 879576836 258481115 561607092 399572196 939304009 255168058 705030470 5332126 997540574 856770554 774780670 551831800 155455593 763809064 249946125 359083731 516222704 3762506 594107888 856611687 959867591 158466860 867144343 888132772 54780248 444598247 250424149 931627947 917152472 276512403 790102253 251569458 30008745 639041862 776764430 746362170 560294907 612288944 992199089 155967293 749064949 877549190 862539885 839115265 234323889 582045368 215890414 437446007 237293656 966107540 530366651 775645801 852866040 298784333 671757329 848239704 643815815 911775926 419577083 560559108 126276136 752817614 11134304 372300635 880231150 493939534 916846910 572752744 508415363 324944295 961372662 583638520 312257953 946002097 14370028 357781325 84786363 425893443 578257537 709605819 36680807 556853167 642543336 886337675 482179936 135749703 888653593 375432669 629329055 754229181 233326124 840406021 856088654 472564277 785607390 216481980 859987775 102219796 617409039 92707107 647962604 512771607 652685437 526266469 938633531 24360532 812754255 792655936 279716970 560541027 886488427 897104725 116990773 188837850 153151927 697020414 577368528 477961200 57882847 628330163 173488266 449460058 100125752 534823133 336040874 51951070 737701114 610917203 333798204 861053914 183363061 357922266 755670770 362049877 801499117 196453857 831047119 507057803 207560537 162991406 885953791 927844147 2712593 204864451 575627785 723809411 472957806 567425671 552156110 572195672 268587117 813413913 41355311 959722530 236239061 242328516 677851193 448107496 801721872 290644880 73302943 477323581 242418839 620491284 866089549 638242060 409183542 953741819 863372148 206224107 423865339 431743488 656172680 280795734 163026124 687652085 163284032 93195412 356166481 257383321 819672582 94677309 795019725 661268706 556608410 985106161 468055421 89415287 236266250 251144578 149680072 276634452 323323719 386612473 103494629 767937210 749760532 447018743 29528367 364107188 575520941 962107837 254393661 515184376 902469561 869128296 677918556 903756676 504809523 413721912 480124572 233110505 379271886 784185173 303609148 527273757 956077843 606185743 264524505 16469207 122757863 388023604 44543969 850631460 547904514 626872009 67105971 590822423 305091583 694239499 215542580 785838255 386805920 857749939 556066781 881046631 637099074 877045903 739353200 405326816 877277998 823379998 286043410 624031907 518199379 236872012 139376891 574193099 464388725 401987739 114719445 719144772 368727870 202779627 747841762 150099854 860433128 327020624 604698998 309011176 219608973 204564735 160457380 644047938 130454114 782638462 976937767 556358649 290315701 794423237 332747392 529241586 104725437 731718051 886255573 50664454 124715953 51337881 174071699 686463484 776246864 204782113 263168895 483632810 705897291 383035765 750257643 864489478 587829753 447773910 285663925 444718421 370853352 564578550 552817648 382681532 853654243 978516786 906408715 53392483 821382555 999128587 132628592 141874725 397131177 557527825 356479609 596768614 279351071 773867392 310730145 951736821 616365906 750645074 731283631 273525569 561333588 287097320 783745674 183394916 942890339 75000185 47382403 28979406 367848359 764659899 320327361 305234960 303237448 443335813 969456668 58978961 32794996 549695080 485353381 482457600 613757825 632687151 286913370 21365390 919601746 880812321 285041645 627779960 624186939 64044991 991056317 523522892 600100917 109494224 774897658 695148445 901262435 639813859 975316208 717067542 816810833 387412217 521990409 616437041 878540995 746693979 258721745 516462306 492551960 327926091 641321312 693046266 520006880 180900428 48646352 672206122 295152646 587211593 643618735 212844754 147382785 880697447 941042575 68105019 452530705 679650183 325645613 743509230 628829480 98996174 512901024 746767954 272801477 993900044 358033955 447564152 195692658 480243985 989940286 754970136 474558958 935415701 377422003 206644472 337791967 465627830 116777286 515429622 549127126 548101272 394994256 774001687 973293053 30098754 445066415 362263255 958191392 511503148 203752763 374747459 208081272 220222895 327027170 817045586 738752776 840935361 959498727 201195171 48822989 137715396 577007620 329561026 660637469 462322567 504114523 315745380 78608829 21561920 196674529 699806712 541252096 459818601 758299029 896507998 555822358 171318599 521523919 638639706 723552560 898731262 693551196 622135159 947813708 256405452 894915179 127218772 258776500 118332800 22237261 944880826 644759160 296341555 83338518 948907032 202379391 29473494 850611594 978593048 118600285 60744738 641407035 478555249 267479463 490262986 253278789 907631753 853192397 206498283 180468327 147791147 582388858 775819316 832429207 701006316 332508265 379254370 791075321 550432634 675245667 924415681 119562822 369039276 227194877 478181656 730460639 234475105 266395648 30005600 203883863 110046999 965285155 728970077 73618169 736330121 144021531 816144957 351351640 976282720 456405538 354109123 613610678 241287160 727908088 451676852 619792929 166705414 724435682 236451256 786113851 226651891 316122243 882980129 553550300 611159783 945628444 45849281 321303153 505251287 491345791 989588723 908858701 126202762 256860885 834959180 494383563 20615019 166434337 897047631 644020470 583841639 344457157 279492002 439175668 549144319 6002109 280798297 745609109 55945757 307054477 504279442 479927413 26189698 327573369 730697957 242640183 179731206 678290088 626307255 966006756 440989771 261699155 991971690 852983263 195891965 972071596 828704907 516104640 866379726 383356660 762674025 829872109 158806749 634990934 715351828 153855236 758495114 881118598 770596438 558786908 801049704 645088385 428046368 666729853 558037498 289299935 949800587 433721234 562123381 530394162 866489103 654239595 75672910 451516596 930194541 637748262 353250871 74380568 122382277 973880825 665433956 165900475 591572332 468055215 179518643 146267456 864348060 935756311 865715857 782059884 927480946 618344683 378279301 334318314 871695156 497093815 271291581 563362717 372176117 168450029 667844920 651782202 129595035 408955888 600595911 663164609 581085467 748832036 495836975 530250019 982351879 715628575 654123356 523856449 633437723 2616009 233177105 301653000 67834485 522387580 671481792 394400666 786807164 913120227 872612737 36384766 629772798 141655172 228802063 554105703 506249036 854376677 137722814 817379060 492389984 355170934 349554721 187549849 452804673 186505630 441569538 94398760 282673256 361058326 69131052 976404288 302865064 348648466 162024890 643103298 808357081 849934427 810070287 527679927 952384576 863619107 506164855 157899770 464647492 665424061 817491295 12619779 181793325 334481688 650800333 494288022 898691353 193641348 486832667 776763069 268679847 765392385 20432369 17241283 768930898 695279805 675494411 334967703 662565533 780337623 815340912 470943465 205475983 563873105 278847266 278087317 800534843 600088125 611280569 664694213 968499624 631306572 626831027 717276800 848766050 659012915 306674004 277240855 518382098 304340113 930025498 574966252 810831432 525724859 121176835 412332493 951528440 174596896 918364419 256943987 338570639 174055488 225134938 219296911 969169783 807273807 28440787 407214415 651593302 780301238 569205935 571411629 379400663 926476982 142122414 840774058 921780365 889771704 508869165 482377096 919671141 692932369 527170868 581121366 907151122 299061972 803152119 71098034 498802514 701232951 374784946 683963313 809872342 911170907 145385989 610933060 406183369 832332193 740933591 816623771 494887437 742549464 835266613 946729469 543873221 394624924 417811946 718629416 849194126 450885096 144661516 69045193 833914955 15457899 447857601 521170016 473255359 379090319 648940285 888310331 872989495 403446532 372298526 676340199 328868737 337651473 366939165 642711445 775852021 572618348 316270447 647339482 871636477 66238304 26606574 319404406 433856760 170559227 490505992 628209354 818873203 206060592 574405821 946168507 293589245 334239528 973074919 516723608 383924763 24017715 741350638 306748150 467029249 698500707 630512706 605198164 842077751 135030034 624290220 872884691 510915297 779751371 816730560 39960621 303277995 792046150 558694363 418296744 863488007 680908710 806118859 69284631 429540145 339435583 851829740 801187313 747033534 77545949 660335603 62310962 955040348 443099689 723432526 186148740 730964407 796619316 395617333 316687453 386168495 305253787 598716539 684603449 721185624 312236859 299670468 380590168 313765471 818893993 781604412 780521387 401733527 911737250 128334918 484430069 851563384 604924164 111452569 799280011 170250265 340303600 942630919 943084737 616802319 378148588 432582259 640467596 56410966 437325682 480279351 659285845 386731903 255124106 606000472 945420411 383157655 872204391 756881900 907373455 749800622 402686839 225813087 866885840 221142766 969005071 85303866 97907786 154201382 39898238 157976798 551288417 627175721 556290680 274128108 214400432 189907991 314420108 783372041 423524146 359816455 363207305 152559183 431651628 931303617 141768929 545159105 540197800 246044956 124787853 626707230 416769502 273995492 251218670 235752506 721004279 500568796 125190338 419124232 97429690 270322187 454583623 136452108 452819508 287784491 424060045 449088508 651408059 67679350 428064956 760023315 99174842 682597342 282093082 868039762 128922954 362952689 529716488 792186622 570287934 691826093 118921244 137829172 422578569 203479191 400578263 593440509 734342064 980968844 483297846 426276786 797496489 384654298 855736338 954287838 958360989 857846018 590429402 12594770 390713817 891476833 616257231 871489964 334469837 976496752 433057204 449618723 967107450 675749665 865850666 726876624 437138150 308927643 436904356 26415738 663168841 200844620 148652476 950923023 478706056 280477855 375102301 226527790 499218510 938322344 700127927 633118438 240799963 39644577 500172348 371358132 291937164 70334798 670494693 923401313 778047115 316953130 99499352 724967509 974764824 926712384 370767836 918046799 12934426 167740274 348813027 258770930 838885721 151600506 992242317 362342887 251241037 155558030 8420316 780427953 912417991 720195041 197532624 551822627 89691431 121056483 981987367 402318578 365376374 330804594 847806027 673468855 337997266 525844086 633027019 627917088 80254668 184273248 901759818 929958374 986557002 560412860 995296178 630985580 319327237 640373594 184513722 219902101 409631988 721708910 853553018 781116900 338066102 933501400 964695629 660182362 624668513 618239836 178433846 682114001 222222487 577816959 405534063 499728827 42833203 719034950 586179288 218951338 91649848 741616947 319865186 466282744 997590233 109149160 217661508 253688495 531568879 608414621 630349175 510391131 345531552 947553553 138925211 675319920 840229021 572000278 680167372 202297528 339022034 356582804 423952519 860733801 460515166 42811187 734026943 766811083 816777801 980386203 736417319 91181110 390478301 263296905 171389027 872494747 947798474 907871854 843880721 770238892 692665776 770471920 920184096 713125541 986692327 498661704 413316301 569430893 956899912 145990218 798899570 212808036 221952869 819368411 977728890 538738755 536345836 760251901 972806466 254367214 380151953 181409869 262369536 66041762 134286326 508393659 235292114 600803266 414898237 29565486 258964205 477704699 416971221 590724383 492425082 667138557 454882386 53328854 601657882 787612170 813501 880914170 391067046 461645162 752182715 786849382 355632118 396985438 973275164 102912066 249717279 883238489 390348161 290857314 765144635 175694318 987443975 269936689 553399629 27038805 10328583 169242031 862150323 598580975 344815845 182836587 52223168 224790211 27004567 472500213 539133586 884141428 779625740 471033724 407262785 779641471 141748611 487262189 390458782 595700797 68293002 609192616 464940759 389667819 806172276 890796614 281772446 988323729 291531045 756689245 829305247 326295642 260231245 797457283 527156981 80275039 944359930 108861200 158708767 25139341 52496618 831977671 509777072 379438536 626239805 722768242 762613615 669583675 755500119 534917638 405469903 192393453 542267150 295087566 583664449 402156656 451576504 802048653 699823999 429720718 379346425 239076137 826508108 132937623 433277677 34267719 57614135 289572845 898871328 919124991 78497474 68563017 955424027 188237734 434574328 596027734 866768351 614534726 272667835 854757350 848532180 940534955 170419989 726954029 266907387 590437093 699646810 824101297 980902909 699492561 626258880 569614012 360434529 836513590 952749241 317044950 754808237 385775621 815404810 237047288 160078572 419980033 997169002 742476584 492944079 495891814 135110876 211893723 899059905 11598951 539066144 213811847 758852331 190754460 270397020 795167749 223528159 789849069 370225571 903124776 575563023 24737383 90928782 30593259 12536374 931836846 147191366 400101669 450531063 659742638 772009989 184053337 76439544 629018096 841596688 489158260 793446395 725342520 790926863 961813622 192217339 785375069 835065207 455594840 654707912 174625500 476993409 542030186 156410498 579915751 468671241 164282767 241731381 597951552 162574337 571423398 292670261 14494609 249271564 874782971 201132319 599695493 833662743 641075012 751540195 266348387 470003412 681269374 17655078 787321379 691118685 853311584 951251674 126931704 381788413 219522388 132470533 10527044 389138090 352494398 758537808 536934993 183506221 148594873 524748298 948367077 594087066 762702552 886242268 397497008 32365781 318439167 917276136 293410253 392967361 749111761 349327139 924837176 878480938 136397833 24250467 106985961 704319945 355897262 876623798 43813423 817063534 11465063 137799675 88596382 175986266 241880599 661264946 43148603 157777901 91612042 377990734 711411288 274877329 387425042 128563168 903683716 383115313 904920579 238698242 565260089 341295307 951311003 611536731 975123289 24493793 960800653 702678976 878887085 586225433 828219882 779706062 595368186 290885489 899637759 634328442 349028587 562971686 814061038 990274383 514333154 380185149 860175737 737079668 492714600 757506998 469420161 932343735 804336651 321244595 255669054 541005858 309786878 446023657 169380175 634324685 33090123 227179692 920019242 575766121 12592619 551929532 614428742 532175536 552460626 508753189 302140105 870425467 591051846 893899617 945826328 33140309 327484472 311499057 899413306 117224310 527153820 368084700 26238963 692488078 955939850 768345378 378335862 156124702 897087998 282832021 369380747 717962587 876868302 559988325 949121240 858422152 409364668 433869321 28813514 3824726 579700158 597203547 494154403 21363420 3583888 562566060 20389351 437698154 812633547 313561463 202054131 785810088 61661934 983043615 257759449 715960348 866042609 287077242 189578704 657601542 902627865 228666587 823870012 398548266 666126916 377764544 44922828 581433187 293855326 256736746 889642423 303852141 564985834 441118041 121348004 687308282 976346452 587164798 861290472 181533741 272320466 484915209 603114508 51908856 476219322 240645526 156216011 685853176 739774929 323388827 427069063 47110989 15336636 292831378 745622856 845887236 392045463 686496918 735086985 713727928 198362750 882341438 899735950 8813052 502848303 236355375 907695222 28076201 431545548 876545842 222440366 362586056 817099327 504185555 951066116 653574515 839945083 823733310 241862166 873586987 432619490 835765357 881170018 383144762 606060153 510956108 848545327 810345132 5717957 279621141 290732948 70144984 730734048 909456220 732953983 989228831 428052842 874313117 274738553 920075338 763646394 818130184 672724525 315235498 383629319 16855939 782819679 245576676 302463975 396215041 354590404 327730616 22978315 708730261 451798202 91055650 773342303 239365514 752549237 717257259 48212453 618396147 839072450 93072963 773786331 172960497 744376844 690536486 179605197 401916038 877813605 495970663 470718317 243237541 827043008 354430645 385518893 872543851 881450562 511331102 642305384 436172653 1877717 60157269 306107982 22138180 797733938 922954987 116788100 913650043 261677576 134273926 903715629 899098793 28721086 36869184 884237644 824751438 809719976 457569377 525217163 986592475 403769654 710547271 564422478 856484317 187124467 147094679 268743248 291822346 995406907 720315602 723153781 536707117 164890165 343775260 446080674 398235503 851960669 268820102 220127213 209342060 85256931 167265614 885118375 614387019 595016345 817555781 146193222 241054472 994755078 614057243 543645172 73886339 293787098 121553154 595098623 928768548 908373412 7786232 746330837 180099061 366109963 229619725 206211910 817176642 263645864 623291654 997214444 692126275 63720859 16206334 146664763 531647993 717859936 551107735 394922919 877332144 13794732 583547632 110488015 328576697 975099140 973706137 896416226 672765520 444766610 733524751 871132907 754580734 964947172 12720500 382071452 35584221 836297501 976358940 95332514 694441001 690808640 329029607 860544226 640902690 821046086 407282383 858327029 481465531 896907087 275058186 497745937 873834265 618038116 548146287 7168797 582893060 687931790 760960509 421746929 93073093 888553157 203026797 701215163 847355546 399828217 631921250 86110685 502333242 192355474 542613542 162640003 196220491 255219771 107533849 99087137 507201811 122375690 687394698 172262001 799947044 775141103 834852210 941276216 905117080 942217542 551086524 941428838 701034000 664812736 230844955 856470342 807611126 973067712 335183533 189981475 374829678 694784813 850597738 980347555 104076297 795558401 167420361 234653076 397237345 944876969 857539892 759502770 723099353 207359763 331577846 370427867 797482362 757210739 412032800 856112503 226154312 339258766 782689844 272271264 629489943 468791817 757527469 497880845 845423252 258663108 377319258 274866877 159760380 20759799 774986595 353743282 460116563 942603529 766058685 387928905 282553313 454862590 159859114 913863477 117928343 239589083 62473694 338785723 293053856 155666943 705488511 934436182 545478948 72581660 882837246 250748994 448941388 546270718 18301274 733076026 142316321 636115348 863788431 240681421 914493013 190543225 794110566 792848069 897753910 776777089 746303025 80720487 987924672 258308024 527586127 14349467 302381768 794289642 775940419 610383712 776006042 258797962 244991004 372976250 297719771 248585974 742530621 725624060 358907966 166505093 870360532 476704005 677393584 398998877 444825260 737119808 21144527 869866449 458477322 165520848 179884571 660614295 451959924 405724464 12234005 622831669 875422927 353853107 796752858 816556940 530488914 731684894 824334887 260138594 400212871 512814068 317878050 336309483 796379422 423737773 290395977 596939924 77154573 669431229 168044299 326310524 832812986 641986798 907878268 917700953 143648985 382073688 38951341 296415870 861027344 951583171 631465811 622784266 797262876 572069977 77475889 76822612 169545606 53115067 718282287 401541838 63414484 359442226 975283152 362808867 305285833 404164003 569498273 232506262 287912325 270124774 755511361 393228044 527350335 463526213 731266885 996826457 294906114 978486192 413081468 203028972 940854008 533955721 577728345 197982560 402688089 944526466 988067877 144100466 801557023 337417963 245360714 405620185 984416363 73856043 595297448 497720401 790078474 590273936 788041713 745843381 327916001 275882027 751671549 600059614 807250133 744729895 303979984 836536255 272954401 859531041 605176809 358752079 713600090 858794045 59934415 787314429 165885620 81752386 327494054 528057388 655607793 841681497 21051053 707613614 872065790 913416213 451164079 402504448 740787887 443703665 739140610 783554181 772812335 892723298 147032179 835929687 909596230 844798940 304189258 981915478 997337651 238151683 761175310 895112017 842698418 164480342 495607068 943704897 780326303 744507993 274169413 574315428 147332789 276993936 758516542 588262234 557245007 588240872 918213378 260606656 131229638 366018777 252049708 316898308 429540536 644959833 789416131 432826629 669937934 227232147 610671679 279975813 928503685 66534950 298507206 546968922 236990434 510829605 769168670 714945514 598719744 119226973 548156462 355730126 594637591 8798579 993625384 87574774 350989430 427523174 496668597 358581774 747758214 497983866 36428067 849311460 127129533 698851885 305151292 155560923 997015102 172137425 534934476 642839787 866711457 674669092 857615932 803776235 619125653 208628162 685457970 978196821 129333389 566297548 752000161 510495148 117286190 154954305 897353607 200059319 944462388 139346475 572711965 614265085 702350042 184090103 855112975 881495615 606282611 87062439 212996980 350497759 116995822 856297128 441767138 938916066 166362252 387372793 49517359 243834229 902948569 66333331 755821635 781392941 629896533 383045552 556019073 177252283 346838438 466337243 399604335 733748994 622140295 828182132 616021566 60178613 31075519 755041198 528102764 137101229 941420887 426346976 388615893 331859884 997264955 407308785 184545828 667490881 422674997 530397688 475709220 466311638 862050120 920395254 109963830 493306323 38315701 623390959 587320372 458610621 524061718 87252588 686913066 980075524 383057979 89110519 908404670 121625747 217201864 446339110 432424068 194543552 15061678 639377457 627311894 773501105 767280002 762320785 24686176 550204750 125635506 517670317 285283090 813101644 965482920 530635867 695877911 480941218 794747702 871306063 304710761 351829898 8679616 498670690 860564490 184256633 640767515 87586299 996269127 301472431 541113898 102409676 780256729 950012500 985530414 53602096 392989235 127549180 824442556 387590902 873868873 356099849 99027124 553808927 874639396 186122621 704424297 35919416 610969283 159990688 131806892 690240826 16622872 129637008 618016006 22875757 362283277 572786358 826117769 411486110 879583437 684010488 579146804 983516014 747983251 804645097 758271902 73676864 916097005 653783866 570152082 279598304 273210584 642493920 622506907 457817000 338374153 947098435 958053346 795077049 553265931 841252244 963077215 895178701 722612139 410011923 147305332 416307493 236114213 19945023 877528885 208264181 708282996 780311799 607668440 108674789 316061658 573458338 429795654 563816333 546840045 880473970 58447435 752128636 263910527 579076250 718458938 343933243 325449813 811828914 280480926 246713705 208484989 226833246 502408568 570841602 239126487 921253006 173471914 388275529 693533924 767579487 724422196 391368278 742361856 155232449 577537059 932630535 185862028 580988527 985013031 782511483 539511246 282215434 189195173 599347807 493851687 137739942 825101164 851585420 124499419 313567742 969991203 685390343 92649204 482052886 499048269 51235953 505336476 988760781 566967352 903545529 293867388 561548293 931088198 862958909 860645166 531349214 834705576 751008283 345794420 754348324 440813924 486363170 806683160 742940099 157569581 53005133 445953356 707738384 512310800 677898622 821438592 957511498 986981260 318483484 818742131 23764120 632356731 816240685 865816532 42476755 397083621 169129888 622642019 847569377 703919581 183063211 406128569 83690598 105150773 497974290 554855506 311976717 116790932 472588284 875874399 757543864 545647480 874276108 556451149 359202129 185761058 691645042 852620632 156716413 252980222 795720444 443655354 257048067 800364660 870902816 900948124 986782219 240466712 780166628 351537193 981095505 508009362 152900287 384454290 443796919 774858846 942381244 506779809 952526064 828558997 488893275 745092079 309343951 911123970 88088570 643997987 338902015 787998721 279974086 105452778 499052266 558212738 923058486 486565997 576256482 202319834 892256520 32589060 70012496 526822163 231874260 144333406 441057862 328519051 528729433 328208268 507418647 604183167 717453586 271053291 429153040 111561732 254130690 347220523 420408647 360784579 976740027 355552183 173474495 999184560 6215636 160275046 56045699 287800927 536535864 216258231 929122421 782986772 171106876 851978420 951962390 792803446 812437076 87419394 116780873 457130677 183065770 406983005 206734287 601339876 702925363 338322146 357269584 598625535 984222024 559421990 445559624 530283441 543937211 903082737 869140717 665484564 830157338 206155958 972448984 837529474 934593729 349048383 136831661 279017056 446409893 387579251 200545964 659646138 624983182 588481180 195687555 377643589 760959563 685636161 119378758 418067698 491745933 828191224 368187450 912072286 233099144 586727318 401213869 404644302 407246139 540878405 717370709 597544785 737430614 575066560 146424459 358639292 52441428 756663307 416725238 342893884 749757643 245100991 978778271 117009255 97102213 163725674 597242607 943263762 686534467 742027183 781539855 893195527 321748706 406018848 348345906 744953611 422964169 32076183 274962765 825145486 515813879 17456432 884772493 422866062 317286812 891910162 997554433 911023523 729206208 189516378 56498763 153709687 925446251 789450986 234108046 170215071 638069981 612458984 459174445 485642642 53074795 992799214 272714584 240681988 105436829 971232628 847989275 746445851 685562907 244081307 125660819 897552854 666550366 804613812 150698653 571476208 403876124 853336863 674703830 117968842 248556661 744068569 305681199 601426180 514736825 26959249 416957437 477920271 781792661 254112143 280532735 865900392 770628270 478637910 872488206 176545994 226378222 801098390 834471069 632000547 958062420 34041853 116414170 24797200 425528575 15483914 219457401 757182717 539811535 527839911 24239665 328271634 406552288 222686893 123273859 85932333 978877430 236060194 562814512 704808947 967630658 93792522 408325139 305700256 152482940 330643116 780294043 851645549 805000626 769159147 281424984 843653403 643019450 357365837 58828684 929710534 567685585 211739696 63551657 983951627 487290803 283100705 675680207 338327376 645739634 927821782 423974222 304444588 801526842 7810418 105985634 967145909 564561307 261974114 419289099 707954775 355688993 831190861 51598472 384447304 519084083 14782086 722996832 907992617 698944895 979499923 666477985 217606828 957717861 295220745 606444108 880579229 134135434 325040307 194936492 297554774 748189173 228620765 374919529 345242203 975444533 914957850 171716208 787440741 759976674 235458220 463736376 183511248 519767407 841121941 315698891 391653703 552593412 678016518 550122250 540584952 246473276 133651641 81211155 739751857 264383100 343483688 803882742 892268416 560723145 877201827 506699633 808163588 544344504 203187163 379024608 635402417 158515721 7008243 554587358 690057194 357763375 481601877 90945252 733320399 649215041 904451035 610277087 70005621 526408645 838580040 123643893 194020829 530731236 257394310 129306775 407503095 406902559 887843443 809214231 481289824 7025072 617193926 622047401 878676472 612119674 532264125 990208902 316120017 76212145 597246052 470865240 164240750 349191929 487653083 537117312 334413449 692153340 856814986 791174217 113707868 871721851 141508718 870353111 458946833 549992419 16303236 479095834 50908214 590148258 816109038 813174187 221748689 678363066 122156596 393904117 455475914 515906715 179779693 201905238 211196742 471258516 996194683 16116409 200301520 724342397 493815865 676871142 89346207 886010481 561936051 177936937 938182195 221549828 851390316 834592642 409321231 995086233 116801039 513535924 561739445 279028572 403508127 524316520 540618578 172821577 905268225 873434561 328403289 330885614 338084938 380978401 958439899 627612080 533269708 667142459 674047346 192737136 816868640 181981618 657166937 46355694 959034845 233103543 578179774 631608150 93226583 279533860 504088810 857074649 622119718 161081090 921857795 903356414 466780044 127954695 972933827 731928843 643482500 130294143 826275456 552195142 283315490 539331535 631877451 955784650 899901307 751061599 869232275 260720747 101101318 871791671 23034135 224012447 476202614 918499412 412562129 62855135 511839788 653427970 662030698 626166071 104344566 999378458 567353189 800314237 941291083 297462359 741588464 350650116 144779378 887158875 22233828 777043929 247965133 912404307 598216788 819439977 439398597 370324400 814290700 948120838 505504745 776576511 955582901 950152550 356583604 724971296 433970757 259194944 48874340 661193350 256510326 716028491 474260588 889300416 626357253 838566898 907002928 192172909 84970957 136206996 859908851 221570842 582368708 384327706 609061720 597662265 276108731 51817186 91169038 6083701 360930450 519340507 136160010 405609111 577040724 358727274 362156477 172465772 567915291 907912040 542547282 412984455 338319072 575843780 884337077 495814017 115889969 898274684 824789513 790870346 140748939 426191443 545303176 363679000 888315331 718991024 772344463 849794082 51924338 754640903 712808661 852885514 438596571 680571423 498568181 361046626 284198980 844224510 31677446 988593009 205534027 527390635 290269808 228463386 774214669 481883853 892814596 20190194 338803063 173338158 65409936 692240818 729681977 609944803 593743688 649726861 362497472 486091918 432701700 676113153 576164093 491865447 933022497 741345474 685959851 102763472 546366584 67886888 655485930 741487025 914096785 185842673 651582623 142077934 368806099 62484653 87264962 704612148 608975024 36838681 131250175 774248662 888916911 112321761 375813109 228012124 623184772 427628055 63168313 275106178 724838691 436638809 871389136 455625620 458708484 623799393 335412620 620291452 129273091 371310554 895699175 921372837 754944079 742834778 234074782 825214600 768350203 846844158 534451325 461200502 41729812 518893302 370740233 498817348 326317553 628880101 897476804 849837187 900522830 488998897 300638836 42638942 662326140 588688787 225105474 684624662 946383971 214920201 507122369 243906155 990290005 196568241 63633100 901780877 515859086 392421336 260763958 127800574 800452351 609580201 848758043 660296493 238920829 384270174 615130923 45729195 370799369 612184646 438353445 281530673 84885622 125044740 189098503 396548987 220635504 215597298 754724820 335160847 593278386 600559267 777768877 243325198 53386435 877951639 477532794 932128093 323103458 904124546 155771836 756534357 907920441 514269772 611475956 443662010 220773889 753462926 96981398 766111561 327091770 145536199 282444948 119471085 470390401 308648970 855103575 743288685 630430482 750654675 138022306 466446707 354943464 30475998 48526937 486734630 761312545 186532106 397418526 229725216 605601737 859309230 354415108 385121320 231944760 199772602 391891226 72668353 90437901 123899377 134793997 495777023 655713154 322011456 536291943 278473434 865885589 705130633 773666879 117427822 289300797 322202428 703221832 641155292 1690519 158910683 478406861 649159844 269970809 239980393 911743794 8977056 741375408 295647203 474788432 192845228 917955043 791867768 840893922 388276984 219902182 37504837 723866115 109833906 400660037 922793848 319584918 527303276 98280027 174802286 963162203 552980087 268126065 900679661 506759811 830059772 63702909 740948162 509300767 118426896 337158723 960070190 660025731 292985999 493241855 509078277 295144441 808875731 879076420 768690376 984322762 418657539 830397610 453886354 576530809 604833825 792756133 114135425 361132334 188567463 803744689 165659950 401328245 133299817 458046135 871342048 558375502 328422070 547055591 975185404 58805889 168534393 217772159 429123387 50460987 848561353 508539060 991767534 556332011 709992207 958060378 123296237 880661914 482071325 799364257 710766563 353755854 696710410 394605826 803562594 873960439 864044903 30040634 42054515 370505523 458498983 136296961 362883830 411107589 643762741 743866580 936670566 957724623 692254167 568237882 472518597 864906816 116085450 11372857 157519368 614101124 724103166 116363248 478411480 425746554 985804757 976149999 349831624 247531137 851337344 728261383 516790083 714743694 698392456 753503183 889149343 520371582 582081121 737771480 66268501 324167714 659088148 576839502 439556430 688210257 458008325 492634590 542850557 472277541 327485947 715273288 846115615 380888873 997168076 124175977 601160218 811468681 143261630 780227345 441560948 462312911 987460809 406870421 361077552 859061995 636064068 444719445 263724605 196294944 539753256 85620748 514009595 924019233 995110846 836441974 704441290 183615615 113276183 610524143 559197808 492432669 538401236 95389567 725586275 73001856 126897302 494852830 185538898 56471765 804236220 638910279 717952642 506639564 567975876 649632062 642403860 900993600 628667355 622242141 104192490 457463238 595307587 264883625 303711230 229200465 985230215 884128339 453826344 128141596 811434007 641525299 504039720 316683723 833134608 249280777 628432119 909326590 533477701 175394991 481466601 989820576 360595484 846789739 618037802 627057943 209352558 302430399 600711059 169567428 196942413 669979027 359758192 944343805 749083862 572258307 729972784 746603028 460677419 507484530 776097122 633882040 470531182 914940535 223498574 389142991 116775166 582068014 52645557 260342497 954599813 572217175 691424540 101628898 736386864 808845987 509215383 220819169 63438076 544642610 473318321 406434998 473327279 110848792 470236729 182418597 491634365 550730058 794417445 103983880 685715539 890258404 840177062 840011760 962046900 825765572 971088277 465952205 192250048 292060578 398125157 165189310 183157535 325125650 556130632 860077684 15446838 407164306 940752996 913731227 20218892 247857085 998123541 993708618 225146562 952434409 312197799 912108635 393110216 492667489 542238425 392993050 466647730 218023646 847267056 112721873 182970318 491467504 806190122 550484246 368245554 135962984 427470963 162214 707969278 953561368 623033202 400895835 533742346 900105738 466517807 182748196 238517033 461236757 917087808 294901068 548830671 229972986 248654333 376755937 315521671 738043686 374125972 397909996 45173529 535924952 648052415 92775819 998660533 339622788 490114040 843955337 456251948 130357494 755359121 407565209 880949550 582249555 725134713 638947799 638564844 712782221 369534646 233024635 843308382 631621090 815995813 869383345 527356866 569923463 562711218 747726071 539944116 245331339 282723049 141396093 351029007 620931595 862982356 894625392 581145888 690773251 205118625 567273604 11745995 632275829 651379888 911937480 851856088 434838937 804437503 750079426 604554609 843123834 11038252 716931372 553618153 206679806 843765866 598221077 396590991 344452871 448613265 272841108 88760938 827177782 687960213 446979464 399224595 273762492 624187305 959427494 233681360 354633781 53211904 231654627 200126234 359834635 205349464 110486700 76400999 883817760 584168806 156962213 676924715 506887660 861596177 340494915 258868178 400837014 763435880 137405502 292880502 437791893 811318094 548256131 383762747 562356294 229600190 268752375 530893398 537623279 302368466 51121086 774051685 949397414 832873497 320931952 570586187 88898471 906787800 857421725 187715423 701056317 847507485 458131673 564053030 752763500 315550057 208064119 330249384 646928422 232278722 939658909 811422260 452955642 443123521 875355414 486506691 438948008 111766275 528023892 825449076 306294525 148422094 256745871 205282033 396318233 590012200 872145392 815940929 103669746 873545330 764663425 460269612 214273551 3804197 286472572 86277547 539253654 10052451 987467582 202400806 924411883 154956976 194247847 188365225 794535155 759259740 702309759 670824048 58529721 603116620 36914285 560261290 243083303 574158864 397221008 317106809 958554452 1646587 50895716 997043838 16716516 632333686 267735 751581969 835605557 301048892 60483111 587499019 532307091 339834873 903251588 635062330 326501473 565935058 423998320 653536036 376653141 749963036 818689936 945118298 344292745 624200178 266543558 707706881 380066285 999525845 733760980 71272069 402353504 822821989 159515740 164027018 893580417 389938737 862011337 803616711 330614116 189230632 785766334 204967093 162105288 860298198 354449763 858785992 111269972 287789343 561124475 506003936 968398247 728200270 556787789 719944249 791305413 735103293 329342531 483154038 748735950 166486579 276913549 959006358 184450354 237446043 743225582 283771272 14046811 123266165 835409376 577282534 719643013 306331612 3950209 338139220 361281040 509573117 847004819 421063676 983600872 784169692 238561828 764029124 450418104 140132398 909189902 49877806 234595038 515547560 13345791 148613683 202882203 468339675 441545764 886467309 552367750 599319408 238870631 567957841 683609923 85591817 228792778 774075428 980088544 349647364 107521926 199579981 59346924 822230816 786969491 768562416 224853869 898253544 621394147 497173758 194186675 384232330 7651865 20187685 237997229 914671463 110202291 693145451 539675276 556998661 573638759 500168523 194799634 883988903 492539512 680272465 214014076 718977800 595663864 28749238 43238469 9732028 914287063 426543875 840907445 9941285 542215236 189247964 612244118 362281352 74907471 321727605 274963082 884400720 464198145 561082576 550847958 162334493 859680012 332313153 888426011 803367536 734492737 77845938 706717545 58829002 479164751 838974613 921475333 705249840 867065612 350714079 678848174 390293622 56038682 309692920 219848305 260738540 204512394 111207551 660715817 74697105 909002076 654377102 281769534 719545853 652351708 491333467 164203214 355705694 889372621 593211336 341592219 553022552 46375750 737004751 587462991 40817904 868210312 972624091 594693053 394034203 597111866 667643950 241169177 291809651 262617661 176257436 114266570 385118963 983996975 561690577 148323627 705359387 219728106 264767609 259542247 752188680 914547803 125062066 219966312 617400730 921823903 851555282 103922932 324320670 218917570 407177763 623662242 209323182 425721124 294244352 86366673 697920567 677321916 105125022 293378324 937957773 561122933 129415322 476257031 926324097 250309620 590317503 613289350 501085672 221145733 624493201 657722405 358126986 614871641 595362709 394946966 764104529 534852360 772938216 393299819 80243476 921335421 482820873 695159020 270793669 98566096 216941627 349430290 560269719 572610180 516885825 70280654 131252921 973810067 615885079 130856476 287341207 795054870 287199113 737312907 695604217 94622902 513363742 626502333 745018353 540866950 205429574 477093433 381099079 923763586 305550759 678949803 579976472 868350510 757774123 10833872 484855839 366678570 795529448 560203334 746111211 631260029 116428086 725002398 477901952 973673977 336627679 328650164 601600076 680984054 475255111 456392463 917927365 699965064 298578545 721472842 759499120 350183715 209081497 93155776 935686948 333076531 640659859 45726705 586916368 75889397 447562313 327330578 811167489 905431216 679075777 468006157 814464038 866657730 93129179 420848628 228847258 400033083 151698663 204314076 186735391 640698785 733370892 715540973 432570962 266005665 453607193 977025968 270677169 909370955 249323693 931452847 600771957 132744982 311827455 346319649 425058176 486522437 428165252 851872309 415569844 573468479 16638647 183876867 173810975 903567689 716220720 385481332 569303089 567166738 743080797 899467520 542927326 727275874 89718010 553027237 458822293 455886773 265717253 409303045 120319068 806419518 750849528 190310309 274333788 463860201 308076933 722764941 153488394 921737565 709112578 674462229 89044886 335304801 340468337 800830188 352998058 47195549 729597395 894590500 939172372 317957044 457064876 28212156 479368104 598183951 497724353 648652444 672396348 791769044 301454667 829979184 30904109 405469742 905816601 111362276 618521311 787343058 714692982 329410590 438899540 599287772 136230540 396334563 584940311 824566990 303440084 804924999 475366439 921556257 714174304 58437560 465394436 67791038 139430308 820536794 291725501 15825476 37914387 961803987 136843072 927357151 337041406 85497973 593482444 191642280 289917511 88097508 761231315 260266489 437116014 9372936 754222321 842449979 918645329 81552035 37964236 721486034 344528222 4569744 496529113 986429080 351376659 756236612 737163962 589555269 195049917 510835027 2500537 441020526 315867059 297521807 732796132 647835487 982184984 582522161 613550137 936197834 30907762 614296088 982864969 618355669 221186541 735573705 450481427 87009231 373713580 766666567 656931183 82534058 293473356 611263760 478748277 951801588 303279183 759989269 705116431 97571341 342625770 730297908 620824039 708663131 60741144 184400568 668658023 437999901 418559967 171925439 940633405 961081895 888606420 922794861 834748259 198962627 222874292 756306357 430487938 8073595 841635228 12487464 909882178 904477678 664538537 300157916 421134393 384461409 30111188 73115824 415381234 28431189 712437583 726282827 17440489 948727671 992480175 311817140 569047691 961665572 994481739 798298178 488233217 956516003 417889837 940323271 259988386 528438622 489840229 33754203 613629394 699898884 393486385 273871137 479897267 43943249 977884388 108844366 65481062 20760818 168034696 474505013 184383039 196796754 606838295 649832217 889611076 901049662 843939096 392618643 307405865 790886073 38763408 89872334 429192164 614118935 632573482 75847118 718806836 912220897 207154410 322497049 357918103 897399252 225655018 885131691 433451182 916287897 600930772 337536623 778898615 884730665 895630177 178294446 948501860 247817087 21866636 796939908 792839807 685509797 679595442 328226797 521561209 628276531 876502545 922870305 646107647 302745575 334220726 422517204 925093923 492304450 130921478 89335305 744280946 411417856 185969579 513983384 350630304 140140265 828220541 781872041 64274767 38231530 595704505 7931387 738090625 768830416 815027359 853508898 262734278 432695812 92081949 216142011 272638508 117310488 951728065 620500908 598914304 854605688 62974688 63734021 86795574 960052075 17337126 355175371 762538910 596083700 173388847 312285539 232180406 722817886 424812572 245675528 210277990 858253955 965325361 850425136 219028203 115639153 728640856 8280635 293533769 365062535 733192626 642255758 471178396 240418842 720134323 995626434 194040451 216010831 460181837 755014469 988467169 286017645 422244266 709008435 89308013 673485785 364737912 841481719 677323978 604294638 26129901 67772167 896837904 73907180 691919131 834275860 773108464 471228184 879488926 74111876 26187948 508169088 288799198 46416506 732598152 856523585 470177512 844245231 549289688 836650549 988784197 511290334 995875906 497151524 315852832 198616014 139954525 406868988 251703149 319615161 46366985 314475862 105878236 475751800 870754263 410926032 748046425 938199037 536763039 385145446 442671452 418666114 703575541 371478502 81727299 365796975 945381534 991648647 462387871 197916348 12569222 52873774 76987749 633294289 442503749 387828845 111230727 919844564 13183312 343171078 771570819 658421711 486378921 248079996 47183998 667314999 469682550 428850924 934355588 781113011 500161575 767309442 241098719 291334982 106183292 607464214 235750692 508015733 717221185 935568385 791238515 285707271 204445641 773278839 698729969 552664442 476784505 882600107 889302145 237845888 565559323 717538421 455564753 843680040 819823062 526810218 480926793 732243867 395131428 153658154 868358355 487722796 234360401 703841371 730200799 135291516 598276013 714214191 429623278 655145694 636070030 721968521 887506923 719707499 449864205 685592091 567272189 840094306 157346940 528086988 905018642 428010703 13585473 57127674 786820461 575848182 758758542 17514569 547638869 694019618 142943565 883821634 971988358 942364046 999195951 657658114 279493986 70025817 851668506 328295895 122254336 151334220 369755405 296346412 274483766 201806179 663046724 125946343 497850324 231847773 81897597 568115898 421642667 250683932 999965169 580235045 47364265 492312951 637150391 320569732 998776711 136062979 941608287 735334210 386964472 140930280 840218691 956295259 568823015 917793475 269036344 427197443 687976682 408027501 703453844 41071148 941702839 182748754 154312275 347512256 259458659 365248085 647591012 21561179 320126700 862759601 532241539 951171135 694310721 972406727 495748522 619324754 124580663 804493616 249648616 614029192 484979932 982974690 460748976 815758095 344394572 462868249 255369750 849848567 872115811 767664076 809271486 10162084 821974509 39209094 423094969 427771380 180905369 983749715 666945716 782143333 708783863 299411362 417461601 920454578 545855380 192589905 428342332 383456815 99276079 746692436 166422 994808477 945228974 849501025 18171080 794782258 132676863 435376048 490965176 308984562 448510160 479036856 204312848 471155134 867251592 206776680 955682066 81496745 834736709 255441299 579838710 771789670 768669773 276833202 688234688 47811857 711309826 138475119 576577933 528909154 639262977 906572652 598891718 266179488 646099181 306451495 120616179 458166561 481680840 831744337 562166597 440754716 843892413 706129918 356110170 686724918 792633321 811075535 320050462 601411010 27666005 392559158 378305353 572366801 317580790 738045884 635620368 882508963 270300645 478081589 315525271 411468119 248829199 829707025 414550966 15271139 280506694 453182053 624286922 149965251 858856078 539017677 304012160 184869683 365121265 311382549 242572409 900956238 542821808 200478926 369856454 206437413 804491444 83420503 94406682 394337371 805957377 357609140 161353977 646417382 699127803 847341806 923428142 613436370 267325175 921229546 70972620 745212456 101351226 825737590 969365559 450346406 393334101 629437242 583269290 161320606 961187519 609821500 212234903 703355920 231644661 691578024 960857284 808006741 501321224 38420000 294334016 808314720 655809562 776369983 238439633 129654440 40745414 417941213 266743373 806995721 675561310 580206832 656899238 202045473 646290833 166870027 824877211 657448137 875069147 757541402 673038068 321364418 254746702 649356262 445857606 91830679 775629819 800355819 200279024 832353349 139816208 190531235 431209223 323609823 571728670 307084228 238272990 870865426 592007527 762002077 664953790 183133779 627386168 648934698 257964991 348057866 899702667 883824963 655610420 836282800 292460181 330440831 179427384 455158845 136437626 44529089 178005010 551634729 552869969 384408600 879074166 159197780 553525306 146427848 549724935 138349194 260356919 820261834 421314713 217944704 898634228 943284123 768099604 695721523 23935216 39130531 498046396 610548177 639694091 874515968 648558282 340497240 970542912 631754822 667310736 771774259 823697095 690212621 865214106 227775319 183020532 10845758 910482247 478725903 518878845 14428880 204029050 46499938 552828310 809738310 171866650 956712128 904829844 682140702 521494939 233802500 278501976 804902743 920818480 75328043 380490798 45870985 623616401 770353680 923095498 367503388 648212393 469647939 43416511 25338611 893130569 949249097 526169292 838366967 153657394 658422224 506205582 184972303 932649592 471602062 42682618 429413252 81110753 493188812 167202328 487446455 351857919 54243527 851722855 339859382 997506412 159791677 134054549 542966960 910842249 842181959 364897616 781479659 107485560 412098750 948713306 688089738 998370242 537623762 319353985 704001589 339309121 573432470 73519485 626902611 676658159 34855124 209098516 587150634 715122349 7346458 898257871 609573528 248127507 81315523 917541548 962220582 245938118 846079854 817883235 170755254 7562844 952487116 94883229 231466654 231286 166323203 469196717 746775515 207730564 938674011 344127965 377207003 976001976 345548948 886135018 734146248 880227447 269384902 948292841 480663999 590275568 936816691 743652211 22275375 365864913 768315151 780493577 265847164 197455978 554356935 535742748 644851229 604355364 262812176 81727181 100599717 853003368 142425930 864816150 590928328 425469193 758637830 99062476 117185944 519079742 371677326 21619576 384306414 793454214 925796793 696781843 444548125 969171754 274977468 120904026 166151499 516070681 997188019 291222724 805569808 738628896 958544378 124035098 370868248 17332838 376690222 701974358 455230959 723309572 5220623 927060632 650647999 318030299 306621549 616039829 632861891 482046764 777527670 119482114 732636460 167951346 871223153 584674197 231139927 421249951 212515256 895340935 832731332 823849127 467234440 982914109 838663988 349775560 376704434 655335688 249193588 174763861 73273328 4480228 825380760 883918404 334657889 787784204 944288629 932359568 270805354 182230912 211603633 68699499 606033129 752059313 687983813 843916087 603803618 907834159 153213144 235959137 155191109 992353589 788108267 394275419 693555894 980599836 562917619 416170181 663441296 918193703 757492264 868725492 519599294 115244455 400522807 832057548 27210454 309265886 241012604 985418946 863709383 361566090 859065291 238086281 618622097 858810292 691196303 952114988 966758088 765357822 697578829 384658688 806857211 574355440 279893372 950254368 790121555 683696763 848639345 233563966 295503285 215836498 766807026 411442804 837804626 778005261 926610253 78045058 652883684 544990075 388317021 846954796 976603887 891048428 727024475 657515449 163568367 542346264 218226222 442136837 572356838 900952157 706937354 729334327 588968344 826402313 184163408 392011109 142630961 631160928 730502229 877719079 14116557 206808587 831176782 695769546 599397072 981476801 454571456 122220543 703059558 504053573 256353175 543897536 167720320 333266046 563834951 534301818 497517417 368365128 78410345 398124405 490397175 60274943 610103544 389161870 48774180 890675197 990545928 392985093 696434794 493389655 932424060 657856318 473533111 272033363 542312417 473490986 724334185 917628188 374986855 437724012 697291881 510420475 982446063 97424494 30081498 64279448 594830828 669565226 10172271 622417274 240929200 877736864 250193910 751235783 834506954 924464629 63541185 914613144 698885725 495842231 838164352 800344645 386138452 606726001 130752674 536997749 707239424 466545376 197566982 903828710 81820040 835668438 145017157 659769557 768806334 718886624 348659937 22237518 783710080 939166982 666104956 281346659 174540947 138419550 61660238 342494157 162470225 69064925 515717023 412869462 552013971 476109756 233509367 52694247 465519023 231766216 248494018 388946038 724704909 55262903 362179554 882262524 30740797 150633757 117533624 421641257 403851917 713369569 735836311 844671707 935658646 817993877 299736001 360615893 230344320 335077732 337632247 265480412 13890453 111461268 631229398 685782505 388868362 475833925 339886212 466133904 879604333 550063693 93467213 403548710 470590254 825070791 882748998 185984557 107351278 572988997 979243751 314833432 168366139 85956068 591641545 439283936 143626244 779155750 905322610 597872754 996073847 67291079 968401183 576118369 839449649 313268774 922999010 576207453 338330933 95572192 168561608 354389808 850471295 610437167 75614523 213327741 509250788 512955816 384374297 663059836 417424043 710559927 752828267 503433803 864485608 843777460 973411054 657896564 415439247 813786677 459062378 123369896 350516016 652834812 440444721 405747015 472642635 882776454 483973205 91262729 733555615 873930033 505436288 570493650 857813865 377962686 803512349 120227817 34158555 179029859 331324065 664300116 909697660 810174775 970052830 272288826 738049117 681178166 994536136 772349279 148727043 291795041 642611686 460307602 532825546 538210697 199493038 502066043 830043182 585267485 451143533 460812673 427863959 406756704 387612453 917402389 221533200 345967223 187041090 586217420 870108353 761616210 131791424 842497530 348134935 167431337 109824170 392709765 42198456 124695983 246248338 694492374 529066535 868027458 639690364 965174381 202702329 704949951 543999987 528094857 406111410 877319319 301350502 952557986 67149054 191537026 741344361 525924720 37014559 530521377 40598080 920999544 92791983 569911596 30776051 42093326 339960028 701318010 753614332 176032027 605121850 889647327 985867350 840351024 152251935 188089646 865839054 740568019 514385329 336594828 26442410 630552882 63364574 633320297 829575390 861737176 377384003 781468865 44839155 389910145 305148146 507919558 706663802 255163365 616824727 468313809 539266370 743586389 754040997 747842131 869665339 369695705 791199724 467517351 11107141 105836376 412301627 40911654 51705694 243895928 454166001 584508469 435690775 247577205 413918068 695622306 878721315 18187525 802268626 569817206 304538186 782134138 506251480 305109295 586137956 632542712 952547555 831105516 566454165 760446536 293583771 28017447 399307599 183338234 36597765 165735804 892608392 127981179 23392095 846167797 267008029 510923031 860212227 526701522 263297660 774754088 884385682 384451003 188638455 794719953 679997518 971716398 509811492 362764842 404638965 20494630 692115346 616361270 320558753 156334567 672951990 41650734 801253403 124221814 896529361 574078059 104431 828924184 407145994 140150459 439566093 320510672 564166038 409229177 753608033 787555949 979095325 524158662 886110886 243614844 999406915 832528831 224412919 708238928 802856019 173062737 731094442 900331296 461030259 783792682 833759088 824964204 159115305 458133453 805452106 180866628 404034336 473938686 70884354 23836095 995810737 342075147 901075844 553619869 462358081 229186644 59717097 802444860 479023076 481098322 97254316 255406693 834425666 356362330 949041827 709890941 225284182 743641255 958321160 805523202 373390971 255988197 219036048 528705607 892184520 669805453 765712249 198935689 767176976 796165040 166093971 668078166 415706954 60115136 180423737 771901575 85189004 344124367 830670124 343727298 977902161 651656321 640897604 208488756 179036367 86233846 942009828 189958538 797656113 649124504 718542907 665748318 669898235 729002842 679576336 341663545 961400170 885560661 969594569 247492011 973308394 528194279 555820504 604048567 206287571 51103415 198496494 658921040 166469856 241244132 284845401 395597640 236213025 460197920 736482298 436518778 939824450 880171747 860374484 260768115 258600786 544791493 291751784 683196643 97715131 801313980 334952079 272408603 445089893 264879764 140664829 450683212 511119932 314067102 164038245 743346291 683572326 93483252 191405061 563282863 318497524 164852528 912080840 662882155 442997231 408705923 946149471 696809665 817496794 994401550 60100846 824468187 100034266 309677855 843956672 542645284 484509092 329153113 297751458 40536449 550302863 867122866 393362283 962186237 837639344 600437736 24639549 460447627 834764286 114091795 258266011 38670536 616911635 775095891 849494926 409224022 781768170 288520600 433675724 172764372 882516742 585388836 284500298 309579352 199785267 800426061 542795015 237695178 404422942 497568437 736699192 524115974 565199571 981818871 304034100 625425134 18512040 427348940 611754221 445142580 768550278 175158884 707382194 80990286 958730889 504646119 130954156 623362066 508174995 628758579 515899537 56861052 968358877 231417526 544477521 320858165 591649151 232338931 628520621 612161001 422280598 357412343 158720669 457660423 182977031 594486840 235936990 837640481 187829932 286296030 138987803 338576727 412664972 114436107 990434133 756450594 326672518 94668216 929331705 667740487 867045578 565140428 414786658 738424389 80661713 680320387 371203914 393724202 686506500 104315055 506332610 434285211 462380604 460215644 234351312 271183236 815503386 862869215 351980911 908121598 768084978 533237087 375309785 773792125 963180461 134569355 606479040 990907086 531306553 587941746 338913486 988764974 758543838 18965301 836619906 125561462 495808367 509763982 581587603 501419360 70716790 364301714 598437915 823830309 369894348 552611003 184172753 901338866 193275597 160796799 260535988 885749066 50617059 875008923 98956834 506932609 415205505 563024884 524986211 699115147 998168966 92617352 391500801 941056631 144108201 994397605 218386796 685362803 669514084 964401576 29965910 690314065 153060589 35538379 915706741 791725366 73554908 348788770 670462372 860282187 527092184 112466343 797009159 211164676 250481094 778452470 632010023 875653761 414129425 591844719 275138962 74790331 448638827 32423847 991247345 922426065 411319717 93276115 730027206 616917407 696984200 320052824 129996672 518861665 275302332 236115057 971489721 890231785 820663279 752648981 120586905 596884770 915738081 876776336 247581833 336772306 273267784 864827119 961687986 315771206 118562687 397793298 392779809 741618040 779302647 185552457 610067936 644374069 904913394 286337660 533990831 498909971 709649932 743869933 386730492 741222285 76365845 979662303 384395374 996179335 836370330 727665106 630685952 597599101 913570229 177999558 571707728 647722560 41285882 895998214 409918106 256283471 647927816 498637379 243540768 431769533 868103892 12372593 141752601 472459581 509523761 930949342 729015576 771753371 648562065 939418674 818751896 902219708 355299635 278598619 230960401 516466028 38371834 299257618 844869534 340038088 298958701 318017861 15899051 532847372 89278152 776304960 337732510 463797895 179278191 44058820 700957925 100516535 449153930 202600140 195320020 290284470 883338505 422129049 826151687 664181551 80951881 905291561 174429702 70236960 497240906 189749015 84153624 731535934 189430954 74802080 556221593 402962065 299449372 598912472 5084525 463484877 128995697 389562483 303598284 232278018 505989148 900751638 396303342 750271168 374921237 658531204 752632190 51273725 601214561 495544683 248709775 970510163 426527962 335986974 983808968 82003549 127567216 221374470 226589276 986040683 123881939 120320375 113213521 570596250 917308041 132952384 641560105 817326146 758278826 300088475 501612922 21278456 116348472 990406485 637638994 25342416 155175652 215854808 64006449 387262015 174736214 19958545 747739395 621008570 907191696 896650184 351722640 248421160 316151214 598474625 841645780 167369387 23231473 493923786 12438884 514726215 252248790 976205870 872542673 251170802 221131748 472474276 160018124 272107493 183076452 361145870 319348423 293275248 179890154 276744425 333579218 64538804 39670048 847732475 950797189 404579144 850507960 148100281 281601827 594135649 823888381 513346925 832349488 111252183 421532140 760692864 403704574 759874760 912993014 236892246 953509903 556368302 412296842 57713594 481135959 763012130 574797232 811796132 430891705 479332325 962234956 333116905 45305584 800352109 210924917 861866056 407698398 119243610 302804768 570679775 863592966 818341641 571018184 10872676 864098687 326648257 701791931 249942144 955324749 723060975 325398892 140639876 679566029 959294263 832029296 992900839 486995743 12146570 399743658 46204302 986495091 109721551 231848978 625259256 841317989 816940778 331635830 280233675 631827059 576544948 994248508 611423067 391323518 603350838 503568331 119193586 655698241 378550500 504723119 612012150 871783053 879998363 602751499 517422523 997768489 628188883 948609167 929288855 146598475 357123558 303325802 329349503 389895094 518099334 612326771 584578416 911062560 511737459 668351882 245065259 387851411 427208627 58836508 294625500 601829084 934167586 892260955 27208696 297604803 465219512 946919240 195804911 494073486 852925319 387358072 578046201 191156505 207455957 957862572 915648118 969560542 246396692 500572139 614867471 43045284 300054312 558796560 887181313 617344864 652590069 823511315 262727724 516353588 311588221 71990207 911178985 447903083 396073595 988307280 240777723 853356800 5551838 582431874 769769561 493763182 641478596 797163765 10357021 942542747 475977330 108692327 876259961 166540903 386792622 944786935 809656823 738869278 797514056 254657216 869709516 776838335 341732832 334495511 251288755 195573494 801947219 847940930 16594350 970439861 310563435 882339179 315057500 869314454 363669799 961393086 839656348 244544069 327364131 436499809 960221807 506657014 408396479 831839640 980963771 223197636 121178863 687275066 240720686 565946532 557329824 102714709 773042952 661375690 156596826 490660489 986546942 797403007 878685445 613768152 630615741 371998669 496313423 926522034 846529354 447391932 632018187 656971642 693697035 402547804 184881883 595111688 581654981 196315061 297655009 986025128 609208799 207350670 85503104 987419564 758374003 812657336 638064286 279707285 187777506 786295 154386543 762987515 866094034 274180407 198896369 571375921 236573536 794231930 595085214 926132759 478340370 982580908 11199865 155716566 288400741 305111596 11056672 25167094 623158407 812246977 756712451 575989628 71587445 281783183 418712626 501660550 512770719 455735089 170000091 665416908 222295340 930740929 931058955 352490652 919763995 745201678 422715567 811912856 611068330 854805646 326071229 526692550 972800220 279061123 961360224 165988847 234523901 334897562 622365528 223248738 872699812 771156610 557238305 580822127 141475395 773925639 762946578 406304551 17734581 515389883 857873204 590940880 568284665 723706512 154893070 320810299 874287152 301034551 997897728 97808930 795694508 362563975 222678661 334441811 978820446 179982591 281193378 637626797 94523659 165447219 112724622 839630438 454856629 256933763 845246463 658198963 496229706 481296691 643925693 169478575 840514000 261927031 620276999 536754384 162121358 355941951 796565953 485525523 896667713 108389522 366438872 792151911 153861189 846441151 22961402 661642373 875296117 208625070 82223700 295387871 790711768 862545024 896942900 568297816 589508075 187588180 340551505 753684774 850335075 526995019 941190289 410276474 125940589 617660029 13796562 484249454 18886870 752400855 460719917 800419065 607651019 739847842 460017803 916606494 477199672 927786410 529814446 518325586 728929143 820424927 77229398 875638435 592727405 287146811 84465273 410082744 66682948 714037324 92495911 67020967 587897050 902216456 129778037 460220726 822049328 605917531 975372083 860409238 533542172 963696126 470522657 44220746 992541321 743532791 176066432 307358071 603282777 531983975 388445585 738562894 98161060 716313073 977864245 618192658 687037540 125329219 759588625 463022024 374498131 480085234 418804723 711186054 679971001 159187760 142008693 53910513 929156243 109006440 665712434 521488253 304315226 557548927 466755480 993300010 554231794 650020388 659170726 765478880 8401317 580876121 687745096 4116118 781460796 164567438 92986438 311804533 673338458 365195375 935226079 313312719 321936894 861964745 838291415 175799531 7252073 86451541 426971834 113120886 214258483 630391840 626590071 812727843 965793787 257823872 156771899 793479687 793881113 224915506 59339523 659457717 80040632 400362120 112660467 901126184 233734635 310012114 98062958 287266640 253433946 311627765 811079830 663213112 206909488 525031814 483019045 796660545 923678801 797836015 362194615 247325711 489380421 442065495 194123132 223649397 502308932 486589571 42642021 661132335 948122964 633697915 152395323 639525101 386192062 309420708 845217100 557153702 143289080 295354783 392279993 637599368 657633248 445543254 4788535 933300115 759839326 189901807 480825997 882443464 653010429 938410372 587613274 965563771 914108173 79871382 277545188 672168408 379142924 343278441 817519963 492391340 336962537 566311549 974592505 537519027 869509785 339888138 94920177 825003860 681839271 269775231 581738125 112454469 24703627 183636751 23513373 796891290 635791597 409627482 283370304 454632979 414378877 53091303 941479283 160582965 277896071 931145095 749164538 183044715 108153295 539590079 661829381 719661306 768831554 818676136 108052378 113605790 372120804 433893488 648547650 739027927 655641877 118656337 295662379 302320826 579133190 188379381 380214807 646163548 116452960 431294989 462448835 934241721 590066438 955678577 168299786 66904206 736268803 375804418 369764388 186025662 597712299 561474655 323746844 807257301 787306547 580807106 942113658 38612335 794175264 654853027 643742048 786769366 383209771 840089749 984108839 155136285 253791540 415857202 808648467 193629793 666681693 878674233 633063100 811487482 486563173 388214750 826683553 256845488 918908401 926324315 782494885 650371554 377052220 217524206 986654717 178360187 252438565 954704115 128147710 423423501 353983991 368083815 782198308 747784479 462705190 938237145 187231346 615685092 666520382 655480181 305526500 891613301 423615808 370502961 8791352 95454893 743249316 199375147 267250757 816106099 858059939 174044916 744074855 373954513 657294052 368657322 532867308 714170269 882161897 449911498 363873924 71299722 166759827 755917341 210493508 157742081 769446923 475917865 394784416 359121090 104705675 243839779 279804925 135012378 662029219 86924181 458450792 822390338 652122782 354298383 320170770 152939785 385470912 981748649 190927642 504830992 568668160 232593715 757475179 137020115 727912461 785034854 408743944 298044630 736536260 983683017 885911464 450798609 700921480 970559520 890775386 13843147 226787624 528163266 690775693 286820335 30790823 877766895 260325987 39845581 471384191 5975045 71790663 992225007 902800807 142982311 87905153 79928229 103433102 588675198 493819858 280306848 723707608 827744730 140314714 831507300 163199731 235250044 312010296 647818127 43000705 799862889 869326719 84562838 406047712 787784162 86685768 764385798 318918952 228471978 665139632 275659211 355255690 126067017 171621981 619741689 229225172 165508208 654843793 615300908 603873688 218334846 797366957 363312192 280764624 143727476 878006794 742691570 418083048 435086548 241679700 869791859 70092282 421068250 877379792 994643229 128354702 295142151 451949989 173994102 202810970 410907854 729735780 589750345 278874886 931881263 416571833 846129171 129956558 846582194 782632773 286620628 684800993 214221778 651144629 909035839 752794958 120178316 418429170 967740899 11725494 280556753 360362318 707823028 661688267 829540571 125001182 531225828 996785345 916276173 631060641 613304010 632716781 20652665 337748510 606169739 870706714 447746699 385255228 961773817 750967814 748203890 784286235 774783843 802839431 184227930 44708996 408214590 873566503 778659217 428025353 78709322 927327868 745325846 973451835 212462383 153616972 696064768 700792328 132870441 707463138 445844842 412799524 320456869 331953903 167511671 10319862 37990454 803323026 900074024 596314773 441329258 471207977 563569076 558615075 343037003 798573512 529762755 344073991 886858229 457925090 378283831 89714747 303224895 748391861 356335163 960976478 970333248 881105712 422117248 9108244 706458165 37247766 988475931 181299695 161694475 934291670 556263414 44529052 980710268 397656129 73876294 548746161 723277237 183892308 951039682 433178730 279259904 384129609 880055668 61161326 777635819 206112242 907372368 314601157 251841959 854976072 648710062 682093400 737519717 323560439 440393593 749302835 749521864 954273343 274636202 435878696 244142881 186619119 92804203 860488264 570618572 52932771 39696979 876316651 196663591 37270576 427161665 571909941 467097882 458195085 342685027 134346599 163856671 107408327 982060480 270379599 468091691 218650829 159520847 868198165 391749900 695617317 278089301 975103942 934839517 824139301 374578152 674311829 705110674 311558899 771711871 655179362 822657028 780844119 438672103 366455887 584421321 223816520 751537788 117378731 639851545 555499027 337798847 30043128 505763547 994028993 680765297 236928171 298967181 51746520 768118113 139282389 943788710 325185942 563633518 597077463 170584495 310608149 391496539 518756719 151904267 814112840 827342746 374539798 520211540 618758089 983952954 47001690 805892969 758129160 682904390 960978008 174869218 106901574 411213652 32815600 410395808 93525316 111793699 699074793 697115144 169154681 32839241 314761846 913621798 290106764 670217137 982743171 159950421 54599444 86141149 46138258 768237868 123249569 41528357 683162194 900353477 107780975 493310071 306170915 203612122 739109608 1132161 486404798 444631379 894436672 338094908 104225952 758870139 441150200 187591074 744424856 482259854 451385564 838969464 337875660 529936563 894109324 934273962 544741761 210641627 587116136 144686664 838158668 247042657 402199972 920367435 331216911 27224609 987751440 802258283 845469374 341133673 189428189 357914309 76466793 127905023 262459522 901844605 873209522 28234327 221617212 422859703 556301285 861590929 496455112 35151582 807496037 504007323 684324039 501810850 54993039 189016998 509421215 400135661 973748227 896745700 668845677 882157511 787472323 131466019 311920174 668216780 728634989 175392937 232703263 34113466 849782031 308335239 791906639 258560330 265657149 385267038 734191263 865310477 991654101 959801497 160904633 184582175 478159716 171176377 278478377 847668355 571539975 439025140 430026015 128863497 917285390 924140108 14554616 926459437 365574417 888627097 378075219 253855295 939459664 740333602 403590230 27583308 834518088 87546784 71697426 779249120 939058571 802091513 501469029 545225748 439977028 780264569 878797562 149949457 254935521 20551594 917554519 718998860 614196052 842565953 229721458 718989533 979193812 837067648 199053224 478268552 532154249 746159366 218541464 894083622 291323323 616698040 213667139 569508003 654483876 132563252 385677580 406475200 451130494 605359753 593453095 881441753 314692320 240005910 580404503 365996098 122273257 303916247 960545540 470180714 340381788 553503450 592547498 755474393 719293422 313273719 200353506 634462773 704928039 114377522 776126520 574435796 371829225 124065425 491948180 103112682 894258101 566946682 534966965 731287243 862269279 725480071 794022631 107946045 38097753 342486224 418398419 497618451 619163670 418012561 393457184 924144464 961739559 719531554 432019939 703959646 18476623 358460703 194425358 853398270 430152736 389023121 847948912 323131705 353138602 383480898 305714713 748297187 368752122 313763030 310946281 527541058 531817038 43948808 470909199 121678614 638792103 34169981 746163687 242389124 611478203 944871129 821157326 308805773 897735269 404100409 877997967 2654279 384787433 476552439 633977073 200270827 840277612 229334425 64345282 729305937 996455444 119799131 776276162 71798625 192165103 893774217 856773019 607788672 717812711 215923796 588281645 461275878 807912348 992661016 365962193 364283040 581283666 833215517 540265146 139200836 744089795 212789282 248821285 345088720 922543447 949392167 425032320 667335474 39680545 537726853 327406283 497758777 95799485 590197458 46278864 739622754 181496700 991203136 806479672 290660262 586654068 36298220 16938733 155324472 711417756 350873797 410209800 250078451 225394130 126896467 940080330 459242105 798819889 463786712 966072837 698849329 551900917 378783814 304829985 557524302 884252643 670361481 428300162 540845181 303614011 727904672 649757475 396589808 728710876 295738011 943986175 171219358 128981487 708747123 1817346 939862415 211322771 411235674 55536762 604076640 150370155 200869619 290463140 353118827 454779961 856116060 526337745 407560629 583024075 634334876 934562934 437967974 348233984 850473417 886747064 865442161 707724322 846776868 629745571 821900105 75294785 682235496 889423399 343424116 4530250 645356771 321547877 789607712 558224022 151691471 996009777 789056384 990312751 781035852 595249955 423536706 734285402 177239571 425084813 113699505 569521306 556238869 528905056 480591505 62669667 309579470 134763317 88139215 549398207 464889658 811628305 448636715 134777421 606659661 119109398 572749564 700805264 410079082 8111334 36970122 852806127 565182002 858574477 604681389 932254640 802927106 231625000 250444564 109107747 593523069 619747259 927732998 470062338 472048143 171745589 654975749 488123180 980776822 636856595 602017866 671815017 138535234 791283137 107246492 384198738 788501114 557570632 45091489 24665286 253312188 507942127 889881720 785492313 362694644 475697764 959453580 65311109 583249883 28982046 643956440 493302806 488591639 133731179 684552606 496363371 692194266 932464778 618885939 897702879 485523944 106221311 339757237 709866841 144535784 158465744 119098003 258295356 464758537 965703241 133937274 700164277 213286141 516613714 796507530 500730926 995102758 833309989 69953333 153904084 689205663 769087677 286689925 697396811 898789487 749129575 433444075 355512609 234313607 255489662 162277546 698325796 931423517 132371118 598789654 912383892 166908325 321337967 353225035 469765229 829925431 325079993 646481996 113157463 267015069 290777163 296309282 629051371 155221583 492699890 814014538 772865391 675075928 902520739 898729680 500380408 544051550 71065398 218109016 906416991 581342127 432372711 327418794 436154642 33932284 188411188 728130422 646208073 950966519 177135483 837229921 543536045 448223849 488266410 761784365 999374779 473946715 955297486 647208917 748338499 626859276 540194301 85379504 115181444 447074045 427060980 80698673 367440178 144533886 296798771 738223966 962403568 982005599 521997149 678019649 302033183 591608078 715015382 504702599 544673687 3971313 903890915 885650262 212377019 3096410 827724349 232840260 354023390 345933599 942111777 553388915 928267804 895645301 340246004 694772755 857741371 154251620 672652704 763127379 863358686 744254032 548441894 516225468 553952517 841162121 664445771 139713375 553401755 309511419 941581492 493417365 216388819 735142244 372460696 858077531 614825400 4184800 8870882 947928317 851780960 41710959 892686486 128523067 492856998 966783317 735965933 325125504 988836146 870152123 510972190 324417349 891809654 416578452 917577212 540569719 82352111 228953304 290414020 96809164 219736241 232018219 686782011 543863325 194366533 193466456 799621150 222088737 99278705 649064586 338205923 471120748 152213382 87779710 370852401 702094570 667687591 941214874 70749513 30345986 241163443 467334007 735896443 716716001 851189900 650130423 313129380 985458479 543831089 285044450 846582968 831597833 36796952 261682695 620681380 148867677 519810184 602840145 927622235 37898923 285715021 607332357 465894820 617841908 690275694 326189598 583010796 193426792 280524630 677033544 781587359 356688026 517146957 786853088 933594155 274725165 587519157 505953775 5620994 958290122 664820823 880523625 468821109 265542389 144306178 885210531 347978796 556514959 107735982 935419447 865612208 464238958 878504574 486415633 963974049 809022259 560351917 213496900 87251350 692648793 892563839 122053703 483728418 318531417 707535727 261485792 762207016 656679796 660941275 699236636 958709084 793061840 774085203 542206583 281907129 295718336 233663244 41274654 726895095 367742997 222842681 685750964 128376815 296674164 943580454 221146455 118526685 913147537 843934383 396617280 719977130 5136778 554536297 458748280 691426001 372772978 162121327 481763023 197870709 722889472 667191015 255462142 876058366 219930656 275402805 901974451 770806867 785085554 697966762 543607555 228842354 783354290 962833831 449260661 939068648 441965550 632583208 90931982 401221836 381568531 101186669 486579626 29520137 423774694 107503548 224755728 491437111 962315587 682716674 364145616 406533399 92186321 2703443 161117655 493576027 928581145 162372042 437869447 800447838 244569671 178377888 730619086 499263314 224802618 382989507 615250932 169087700 362728132 374959094 818910406 385277597 707679748 161862792 515148995 724073171 592338232 701300215 575208109 728875772 45447403 439566541 905269950 784386840 872518231 957078331 493473426 457636444 701976735 365011867 297229096 578831594 310117129 939447814 987965483 160833577 448746091 969210294 946160491 134058384 296670516 508814784 332193212 361635924 134983699 903775097 203804022 630225517 892464495 270728932 203125987 153217632 675718041 696642940 667189917 953203214 865434905 741980385 153026047 361157897 539888396 681660673 579622938 133747299 357551515 913321985 969163444 314273387 954884751 699194271 76489015 882016719 371729743 627417491 576160339 48703483 191431309 376643167 312612392 977655899 196978142 293193661 894760796 749581224 655593242 918787123 611471896 131342883 790136047 876696477 907393355 250283108 728201608 881305431 439457852 320475544 156909240 580508444 505532309 153962075 599770695 838174521 560344900 490961983 456341690 375762217 110177488 381732842 575629783 265099104 708799487 226964222 525651309 311374203 18871855 382915625 380786411 287760001 133596322 140803416 289972376 181679453 522131304 250394196 100182571 442330954 51898411 123097782 141874791 686341365 903510603 970186835 337156169 847322634 163450359 27281663 868058863 320557420 428088702 659274821 613884369 130571135 325748274 742829375 524264081 555447203 673707596 19596180 946293186 532746673 668831615 908462063 151985499 921889062 871636165 974657330 169980430 74988023 300580143 406337084 533780599 379439022 757250733 609566524 629858428 660848922 139895497 13170544 915401912 923416801 199090291 122757614 647305440 910468224 649946550 419733365 988136977 437633598 764012437 675396516 926706685 482807194 298126309 330908457 231130591 7887024 556783019 201692645 447902032 737984573 146968530 49339162 427751880 231047710 948063526 827569430 655326291 689840076 937411502 724171711 878953619 856508295 299128407 927774687 459136973 997278874 460279851 496901528 967171365 721985205 528168289 454363941 802429914 871574946 231092753 912834275 420084771 481482095 572030029 524707311 418512331 148881747 109185786 794381342 871785140 215747276 718606434 516801058 177582482 483597710 626516747 502079528 790493950 86621493 588763872 933139869 562010079 165515159 727125496 150991959 918130210 935717373 998740406 531835194 17530351 720070993 175339035 471751138 276349621 562037291 124602272 441273639 982042985 454071159 910509798 947299479 438314918 251933693 946053864 132766166 776707154 986569113 806867681 186584951 954216130 815076294 446551852 374535765 275980681 879323700 464454874 987329816 180539470 238349460 13092434 262599777 116659751 215901368 221011567 475029295 510927135 103240318 718626455 588886566 942637732 590440757 356024797 157149019 969643553 945399377 194160716 905485855 158072963 606707522 702843332 261900140 331573757 196282638 440434841 868586401 181321627 762750823 514427847 925028478 269462598 983184584 732976456 96856432 478312029 522858418 4329998 284591792 117323673 821346795 955698622 96906473 897524528 940663498 155991359 834560366 752695656 690368073 755772101 999534984 901822891 648531929 704745766 593084142 287090185 828656477 806652346 481495307 430763580 283649346 494181272 677758176 904072336 927110797 638188835 162975889 379681539 805988708 114418959 647363437 838869968 94768791 303494125 678132214 670983714 618903594 415540701 984742058 278012696 602900554 699841228 162623299 643985426 4563693 907702336 812454012 300142578 685646018 75461430 334468834 902182965 69451502 658416385 414761522 126176564 193135671 414630389 173374274 938483976 993382852 577023263 42930999 581260025 981605987 276530119 376460443 498203688 856294095 158975883 646841029 217064797 640139027 227245159 895355281 689322394 684587789 681903060 713995215 480792570 271469719 10822201 153643217 300809698 141491586 634919955 123790875 406776460 828455090 28578132 725975848 236592229 306779596 216746070 544476883 385527148 387599984 337514470 44750860 424848170 373827525 484148628 499341369 209468827 518359110 16562862 594274845 810236393 347488878 448408777 954481082 588203943 636473625 716855287 937110848 411619596 580599282 248069763 859527673 676703052 457948729 752078766 908149604 632555383 107135330 559461671 441859867 992731408 979739942 7838383 224416068 276932094 443492790 481228182 514901007 117200811 772862155 559541146 197904620 379870893 477422605 575587402 884349664 567017723 857771715 163319613 475543311 518784131 835255799 504871169 49700553 20099993 831343182 99942126 301993048 222290502 870562537 786396306 630431607 230474972 570236793 844783708 89301225 7597876 18498191 51124605 291460395 572571724 274146391 994112450 528070553 830818411 919976231 376483476 985995548 639345779 847842909 154120584 355571339 105557158 541452627 693761914 64642235 669610448 545313223 824450035 933670168 822273905 649732493 479993804 519973101 990085933 329678467 743365407 719071777 350785044 862113013 600911977 502195485 139818930 732634877 470405237 807273627 680696365 599378188 72112597 214083844 908737659 740277991 217366947 471113342 612911162 743072289 851609075 510835903 879386291 4173334 884703112 197616379 846454868 869407407 339994391 954838009 949956281 319753750 928899064 56062616 519053214 170545278 33857641 895070148 816293952 717509700 540950299 84290141 262191506 142749937 241093140 23762051 462090712 620116213 237976551 527400214 133195179 553595543 223058633 991991774 242121793 313151393 398656987 968147235 686805447 725569620 292413059 332397098 448075856 892067003 510168522 18265738 467618044 865781227 139633412 771015845 1113402 334593952 370373797 175370356 225304705 153457198 533938170 839457373 951183650 80989374 536072698 228208118 513526080 616748201 311850365 66465685 312016480 867097448 565157694 31283092 917382822 476440724 816839487 856227308 479139540 286713553 369154812 941148329 209670601 537827090 695298126 150137468 312036380 990700899 843490587 627747414 708993715 785906355 164133409 3934595 529285719 591931771 799603508 965782141 168852536 527630709 263057066 903947436 782027552 789836926 123570807 596503386 447254936 181178247 705724256 17589409 720964873 619896417 831262876 778442659 478687632 165915360 292545815 521492200 938210989 525117776 741901903 115275576 887364946 277495297 389950415 504653291 122971858 718816392 758714597 632026801 630302976 919091022 437445908 720258359 451640472 904370720 165671017 385014435 37473351 73347046 176422163 194535938 667620655 286551066 54763440 758163161 783441818 465081282 690573511 199526514 185004071 395406333 452056133 906395501 790038223 89169104 970973884 877027452 664451026 273216381 753614603 858704078 7906387 651437769 282084311 601752278 10354854 174429704 770590639 615069309 600525570 688041651 256709044 658983038 246771184 219643724 917255125 560468841 982969960 9463973 410427681 558263862 786745341 964347717 905965462 416484696 838424884 358875722 172543909 862836003 46512113 451365105 967442622 897116124 472483178 517129269 448189292 461317883 293727189 710810627 399618893 718142435 37113905 786923315 886686136 759047222 647634866 491324454 355568861 51935309 944590358 766271511 686236457 747121673 247760760 871853890 401081294 995639959 736979492 143947701 206640336 151122241 293438183 826558371 375547875 379036887 860851614 408297301 179853020 237073106 908843673 130331602 574024723 233051556 16107171 4605687 187748857 903819687 21160186 773637142 802220182 240870222 634532955 271368384 711636324 701538804 828834400 510530595 869649681 534250381 650305801 921346818 645570308 828429395 536264774 105044125 842736677 459894722 763892011 702969131 459591424 141003240 623528501 744242440 388288365 761916633 821664652 635675055 458794822 165269716 130093237 918819647 371471188 367419508 477707613 39135892 503391004 755725076 476243985 980609819 340093209 698026252 653162353 893569429 527873858 823335514 781313638 882521026 972569166 549347632 558695977 311045789 663295016 986750695 772206594 704979939 78868735 342648342 593972610 3336083 427073072 840635996 159717067 991960670 29823382 461092464 370861547 740530135 363724030 243293362 849983929 678428070 449641947 268939649 287874574 91770061 831425056 518939238 857064391 576160814 517772107 420451618 748591166 520531305 782753720 557366368 397196377 508467469 120220280 229022529 958183916 848784795 318654773 918194881 196923609 867334923 508215553 950974336 249578505 399107320 500075736 66635561 535952136 708977549 20612985 807880682 732259847 434481770 92544701 780577863 475129478 755692712 468082561 832680813 598683453 803611669 820635853 376440372 844937635 685348154 911944826 218301595 118966080 177668707 831192390 890324551 393222933 995789146 149913369 625054365 389582854 179496278 533440647 30695666 665631309 90479777 929413721 250130906 275280692 48653235 711518878 964388651 602756598 820039900 786159975 881357684 190073199 687167332 561137127 297535321 462676910 160982982 655344732 976996632 927475631 311255588 178180348 343151873 101106677 558827635 144491108 390386265 362744474 904034611 246368496 665754669 464110716 415773909 852639890 428910741 301623882 13110277 556473768 978374986 933935248 391760901 822835140 875112823 667833918 301495704 488581417 768996462 277747731 131996696 35588143 487029955 306168250 640181331 777865884 815848730 607955853 709139837 583784833 955409777 889882777 469745621 172471115 188147764 796624830 105883006 793505100 934368746 724731574 805053914 96821763 186620319 637954883 976019638 690221081 741974990 600826988 937123415 900619425 273055348 578984016 225377590 477377250 412456555 967178453 113683284 535182093 875814855 888523827 265820561 69048504 904140296 418072199 592869961 963195536 652770691 794183804 456575714 483660012 304048 361038472 102335041 709529405 808025322 763560245 223152287 651122594 116159385 397060898 668041018 420551611 860119055 211932936 241133830 16152744 369848504 331489629 320236724 13686723 518170090 989805068 902803014 836204992 580942993 670539727 212610438 834532331 658337883 341884596 545776618 935439677 993956505 450398586 638504296 45961268 65667553 743182885 500222105 421992862 900537808 360336002 557633022 354524832 725167063 925334817 885062103 417029577 891813222 441584705 490872094 246352209 322842273 703383926 48309671 642592162 261376644 634619521 643184106 173679925 630182079 483929790 58658803 120392420 200916621 928033175 552761408 397779998 236496806 971291970 617035523 257744489 273329603 900069654 486378819 806128567 233340132 991770699 633384219 59708852 946126780 459474598 615749107 751051119 123763751 656605838 174146924 617591060 410716796 219099464 552762269 227242344 688229200 201771679 723539875 777136844 683447445 690732481 387056187 886185763 486114536 805051 219218213 294780018 564609001 647823344 105213867 833388803 492388602 87296915 882317239 514540608 97703544 984868828 104238024 338035311 609285570 439740872 201564609 878986962 464236736 883166646 326617453 721855520 862352565 847251682 781348942 536032136 498930893 981085132 357029665 266766613 356256883 408413207 929675898 274535576 91818483 840412355 92482205 48324849 148823745 791562495 190249579 387363956 646824544 769864199 349432713 558711579 270250187 271740816 348994150 940084852 900327451 179836830 265071517 520395362 637241546 234087496 60584176 107235060 795566065 130555327 766389434 109640386 480902548 539403659 689234035 116294190 839477003 476756849 232960992 152954514 673176123 792749964 158363784 936918151 467569515 255371304 483404474 74936579 15816819 705784847 371178982 330679498 777088763 948916515 656758651 986516009 120664000 400351377 532840645 680801705 318250536 104822042 274427412 488440489 768941669 898209761 159944349 862671381 990308293 726248702 368140297 473917540 109402317 220538282 130638820 325400436 967138885 888639449 484128313 287361008 564809170 362899869 664387472 186270345 918787247 733028083 471739352 824260569 779306240 518469567 389390987 511809844 227110006 514086462 241592171 478931219 231146510 807303310 3891049 105776139 187619567 681736566 357922983 183915233 332099154 621528949 241568689 64911277 284908316 201391622 820230416 558127499 266711101 138260846 548144468 119528172 197052278 231842460 197577899 603723865 280553515 531964651 864622395 953446887 166719870 490229209 850850211 869283226 892983914 60583157 191806572 682928777 316099298 785630846 969972775 895256180 484390455 145672832 284812235 195853054 945127424 291197597 440407151 966490922 874187834 200174985 761082619 604461548 86946389 644979841 183380779 426767480 385118283 891089412 71217990 827831769 298963511 794567199 307392036 397423211 473166021 555180645 248132401 826504611 68170932 460427908 982836587 246352979 803647573 82342584 584367904 192679468 962465588 117482461 939777062 737956895 960985360 983766276 177161850 673467551 266228669 843079028 561604252 463369312 653020461 962125425 834603908 448274777 977085487 609747897 420248161 461534931 397037909 996927761 190154337 234475202 154934424 877843685 908870289 894381914 65615749 655546624 222404386 624516612 233617221 633661669 893884059 452632740 156758551 479167743 824154606 793893447 801131291 287358173 656104968 630230190 679517202 781061128 730762541 129294267 780108534 937414791 760035073 891520184 567467742 430940481 251164139 536031231 21813222 762680993 481665976 969932047 950378935 283527195 475755421 514429871 617937939 241938905 80530462 55400478 173047653 195190240 401220814 925061390 44551672 567658021 286056026 201798008 169819636 746786635 979927110 854139304 694759190 758242898 290334236 856612430 618173306 145928082 305941511 285388825 3724108 62066457 689388792 415936873 937664555 223407169 409286993 268299045 304207176 88628335 194538771 495924320 206257703 516264232 99624997 722133065 426909264 973473275 493848711 457943473 955017459 829544394 79375687 518856478 410788831 155604623 158830772 978570205 726929414 133706494 136866978 760603598 947443522 925695263 40850481 289402565 303438465 516316464 868791596 800825384 514631556 953908519 456212468 170049250 743806328 264247570 931367661 831092381 431752686 337657719 908054808 103044264 625369823 916089115 865739269 425944991 692657806 735714393 806825595 472686063 204500149 515118751 829056781 626975602 786181280 66889702 878815658 95593353 853129827 297326878 55837014 774532194 157190591 189205111 604617383 277955552 656529078 259354139 13893863 339146687 978174882 97439286 211757977 298333387 250058799 955170185 63236330 571373459 626213288 844560521 593455223 774389580 563712489 726496077 617323532 171733547 122119860 876954294 463288740 497331000 830620822 661072788 320404082 817155213 319102853 658081308 647830746 497698767 275883231 881115324 224125591 219152947 710861674 900766392 535112657 690489715 510023259 502021909 911230835 958420785 943267677 373713586 646126909 252123245 622532264 913682153 54126250 285332970 528832396 421022339 874718311 703565126 427574195 802524493 268468928 192373795 416571594 529650909 754447473 654732188 889411296 222759094 37732731 91335293 866617700 603851074 395403253 25767762 530411474 841495708 3711872 7426479 818644190 887431383 12055499 182531482 948253330 520694499 284264436 540391056 155447584 929450101 909589738 796626075 121771263 872596955 999888854 372604904 539936176 765787757 971394541 12283675 157052763 62903314 297351275 715812884 755020574 857267600 26592287 922799962 732087561 466531875 17557357 445187757 699543799 32821234 951695854 488982857 41635485 76671341 902420998 262094158 998024463 687786966 999799089 318542543 194519398 382703029 705330033 619862000 104623931 825621898 850086381 242248290 401735802 737610337 450651850 823806890 42595963 250715736 60695604 882467174 870815328 529029729 12889232 645722267 409333968 72758599 998848546 455736380 768887533 976434229 194229890 748075886 107486992 120635136 498192237 595320829 730712701 374256889 8959968 650546001 786303321 954652771 265240969 768394680 789427522 967484033 462014018 920085786 885643883 457407016 976917900 693678347 814165803 661321526 433942916 128164257 524868749 479303440 789490943 461550403 164286618 87142647 286355451 98368339 183271007 154133932 506604991 964559111 499226395 247039620 365296739 876788719 774116319 757981046 114902036 324321750 199512699 573882958 871737662 196532201 109447986 623730602 526195222 71719433 85141010 26981135 886443962 67613597 541296755 299348285 446684477 379849640 219780407 712441551 334822973 979882178 766775799 175115045 70388014 525689325 366607245 724781805 472577321 628023188 445467493 727325284 630567568 225627354 722952710 223925266 117354531 582307657 409693530 191173939 664558903 90533260 541852173 767983604 222648235 404144375 301937118 447131472 877602497 222328433 535352591 393944905 587846166 898396336 11651398 345616464 168248606 503229473 597840170 12259817 973162527 697708538 35647340 43641958 340832220 731784122 826305133 953755843 394720781 475278465 390176675 189486091 344952894 55618084 40098917 78605748 321578680 495830410 325943598 992326128 185315048 895387313 550376961 553033562 113702011 328140711 983574458 196834335 190668780 139973949 403466437 769229796 482583741 802299054 514177067 925489847 505895498 628908599 181055023 381840603 621305500 901327507 84054266 803727338 761614571 722071075 498574554 498745781 484908719 826032967 391517980 920571797 171742218 530876465 360952770 671652158 371814520 142743294 75162604 286372630 136848712 214587234 158202848 936120142 654768140 632807463 968735012 304310454 764786129 300097507 163848563 795516683 974886984 437416847 297733486 52878888 126513938 48558660 706455810 774807934 581844861 907529729 753387068 599415773 652081852 611765429 516163872 303229741 863398365 485722375 596530031 748531051 139794237 175994237 69163150 411711568 728118056 621478366 265753151 945457194 802586251 601502220 22062909 27778168 24582513 225407131 27908737 644614597 785245527 909749056 790225095 375698608 852977715 621779028 492598757 497882207 743752424 384178906 13759393 272108458 944762853 77871543 711106457 170075140 76519170 514792520 77463337 618926019 85453022 376895094 53022415 181296058 558284873 741445082 270840509 752987773 390332943 904315101 436423644 552846184 882839487 922642494 509462228 32349028 178650890 148606796 477194698 250989975 765809102 521926447 84461270 304827042 9508465 380917363 911790868 208610841 273949313 772477369 179580968 833382492 105767178 650177749 937105888 339861035 133950214 764210086 779347597 545895845 8291228 671422320 963525583 333122087 553665753 133110185 380737394 166059640 206065006 934198635 22324502 725454416 396186238 105095685 841294884 238107781 387983098 782328916 775892145 490904638 547554057 501751506 993984310 782047140 663311047 545322721 75039887 948252586 691923193 739014471 931862924 176685799 620080619 401265206 456570405 606804585 332353566 562396760 841981892 823044516 541287418 987833631 811485611 128702390 160941054 841809826 721799007 963148894 263904349 62601000 215907624 865381685 300626008 650426005 968300891 246191948 936339893 535355884 218755639 629486753 648557781 475076412 346595094 543837716 366182453 841649036 735024347 508334090 43377451 854726825 801705419 706583313 698662188 955373694 655425430 537008201 468012843 410691182 682588023 427164009 714747916 741219345 290248945 404885808 186939015 566638416 159591942 577478771 748064330 110947603 96843381 302641165 638886279 514024354 448031605 623375288 256985413 816194540 180718761 548302981 778660656 627678274 170710488 795744548 890745144 492059021 710519997 835751343 535665403 412087296 261092971 892944797 433871499 421846583 453189628 808444984 889229621 258226967 66917871 296587317 929623218 553142741 404113046 203388735 822780185 802561334 309161920 979137854 755728713 947686814 478662937 395893774 45005072 67375007 985918886 943539428 578342615 590673243 773956895 976502529 641337240 777635864 94232359 579333796 869444439 324737782 913121898 713952236 168119415 616018513 447133360 741848075 686987027 244224550 549386950 183159992 561199647 190635018 566845853 866278762 940842866 38007020 272469797 443212791 137841345 476565177 763183322 73817614 467579873 498080957 781194370 190005376 654902035 86742631 756444027 149070916 384101488 28357205 268967276 780883295 723493019 830008638 398378831 978633209 67000989 321578901 636140159 423039406 624846009 997456047 398565717 938672918 33160084 799132134 90799031 587566544 366597240 280048696 375605624 70029631 535495696 700570867 590533656 399822514 426562307 92804707 953483362 302751927 878975343 96219767 521517054 420905279 173900631 425823468 486087749 12345495 18320932 980830890 892699594 432046150 347522070 46815969 194689805 398353635 445996450 872509884 67741976 286911339 825990517 901476299 830124993 99535343 463272864 900621834 277298430 663375567 167668574 638183349 668756598 780465388 428261188 630149613 167750932 113367791 514413561 567096033 987657384 612996275 408034963 972959216 438429881 577274581 736844427 355350602 64957167 306234836 885809394 320151754 963834776 573864482 469414896 711719571 970768764 747545692 23490430 442421291 902878389 405221176 841540460 260906149 775974858 393643736 1984221 930706651 694410170 8583769 961308389 864225584 515102830 119946611 586350953 652385030 357727458 585103060 730823694 131005256 459528851 523996720 519601457 663006012 660725816 609356412 821773399 292354676 571574960 280654163 616806460 509831093 497564354 52197269 571517650 719246426 991974665 147041040 704345783 991029369 903589410 113374835 645289935 624429770 293766022 917025008 179477601 245253483 288618213 62157489 164864090 100244866 987766840 59352138 296843903 352650128 126934404 275945084 340866074 952034847 681494184 809540727 464477614 468419842 733485839 434881206 342843265 966684829 694030524 105552619 6372909 779611221 198042377 436066778 465706703 311235490 337475155 796684447 502645228 22847891 817446791 300932865 98637385 630277187 756854390 350802663 858403573 192531631 476274328 877555618 268540185 607503254 665607973 532297853 570958042 675150265 629855497 700893419 689096907 444581656 171262575 188178977 33492976 603190927 875383351 244067568 472989883 48031272 376829791 404278551 917018331 265172719 692507652 795924386 744719428 275292179 422464446 504740470 603481648 267826623 877266065 72740144 648343791 797920044 407645031 702587098 472786679 860394117 216640650 361971502 937842835 583291192 347952113 231944839 192137278 55178424 52446082 768898897 275521599 617280051 520572600 360026374 111752655 713173601 835120298 416918675 301606146 172121590 469443465 773573858 486461359 684212304 339249113 251701708 298678393 537081519 985668622 637074472 402280075 404025160 478398356 460116316 330194263 788611255 399379642 260346951 182287826 789154794 641276696 876243863 232181570 721913247 343065748 465198911 211413741 329573568 206807545 986846326 959978748 558333472 813446782 95884421 604847412 644780516 514574932 745741658 884979403 842524924 784261511 43825299 672229613 510460118 743662190 73681377 278860215 730754620 625913276 295717933 554905438 417132908 483939201 113154995 352077654 549449442 634962787 304182089 299845913 865944924 321637854 179902322 4087791 878382277 599715603 578615394 990365082 501581767 243147706 861552634 697507036 816886253 516595897 73604074 902000493 375085485 104173538 490667615 830480424 491835742 115357223 684168031 316953170 70401568 700016191 620536697 622818022 551643222 808253142 623450096 668798465 332559374 428027897 473969309 618258125 179176200 909718762 431324294 882498020 779114671 933486048 315307875 978522022 508085766 470188992 463060294 128459627 423887061 994810722 99447644 858881879 64092508 924131638 889846774 490716122 166857614 815574865 615696481 976751766 655026351 688480147 371469343 630978638 572447442 784715162 930953228 274107182 60909358 169837859 173274948 276157202 566333236 21257137 704325185 556647521 839141538 261198050 567758271 26393458 35621322 566469546 794022554 958053197 72720567 622882534 298718920 259977022 783858392 40349145 4708121 584201103 468463531 546270425 56683138 50016387 682610440 155867066 530781492 314099173 6059380 334972457 550406972 790958122 360151189 403943971 852738618 467166094 538613882 594745263 552859492 766422233 395405056 136204287 455696677 886916063 925201372 518048333 26816059 85086997 783093073 598386005 695125594 712262444 409696370 500869457 818980553 838113532 977056496 519776950 933737859 75788560 59452953 91500296 599366656 368602399 770445356 116351710 267075671 23590397 587553031 617091311 8553182 947124365 91280346 791386621 221305374 219418253 296987228 826351590 439584282 635853042 772554123 905408212 169186505 490332568 692984489 65753197 315354769 585655179 479743773 506452222 964065680 358054262 497735714 338495093 366247342 430970691 207545466 729773267 608416031 964897039 113622375 435782740 324324179 129800413 352561822 284470645 568981909 293266034 709808857 903195044 639592410 304387670 381149924 732644577 508372375 731639268 363679413 181409586 343524971 257638521 917116010 159918193 765551016 182610558 113149783 406268835 881786388 188552240 693289366 433096095 210742214 851079813 519863451 890553620 650259411 789704505 997893417 654191168 490192487 347328847 390253041 869517095 615288560 466183560 78503657 459018752 136058016 942146522 585611270 151188607 686726878 764953103 140985564 479694264 664819896 468863977 157526675 300382762 585540534 87880821 184685044 720991977 541150646 700877714 837758246 480800918 256013731 544870383 954420789 218608969 251433751 976219151 702584571 193921589 644330418 796611921 8328382 448664024 71812271 733129519 107039451 772262287 865151521 579255793 507281485 291980270 19840149 95735569 300675879 532114020 515035052 782291728 550809269 900935420 369766155 621316449 689231482 193373075 952416160 599117623 979620931 876988876 395379316 18340037 287450167 617982538 498859230 909361035 226740810 74922626 123977130 549211564 113509200 655792939 223735242 373967109 261795263 83790585 354336498 610882432 977321746 830363064 618911190 624990692 815477621 349945398 178056893 202196600 679172961 66292977 415790248 969900010 460972977 241449854 108084703 902322447 390901574 144782264 808063648 747540276 480851210 52439457 171037591 33927771 957835599 225987199 985874150 784960939 332839050 291593922 852236332 786795432 982923342 375855829 485833917 459265942 548926647 34269473 580464308 434175488 986931130 129989410 314299241 57966270 613276087 168670271 637243036 638389101 662241394 382388262 463322782 476063664 925179295 454268856 339639855 776882639 316257471 284476207 783165950 348437432 678810304 653361086 791416198 90865854 746783198 973876807 229713901 478640227 797352617 576428230 783826106 731105821 526678731 327441280 204483211 891656868 26075233 441152626 669488329 893029326 527751550 801689103 610302691 627434448 595589779 958675955 888196920 421632345 118239274 624630652 739726339 770474006 506428886 983674131 145001750 629381050 672221132 482333345 471768865 870186347 51435660 797957510 736111936 31608202 290503094 965954431 610618406 817688676 219249444 881150891 939054731 490938817 269773005 259209984 624992270 523817702 63687938 942113855 506987898 741426956 835023374 380911290 573697488 36959120 276200251 728811640 494135632 886298594 20050285 236604902 475826888 660198220 897218071 677872585 525937121 631806699 668852675 220831359 490926463 657898803 960484353 314668427 896167640 591842300 484532567 294534084 251244870 878727491 904346050 269246607 37458498 299510283 101004363 637088777 722305646 486896124 396523886 53397740 980169492 651692656 288444679 633738630 140619147 325582964 679139040 866408082 412972303 719876634 44797192 719354621 426266854 454947505 331297420 228304496 777855287 960494264 112343109 145455531 641095937 12769555 149492705 923102046 472617857 205981783 985246773 233856447 959456335 236110140 476703635 383931752 773272169 854576574 731387587 337962778 354899688 717333074 437583200 977051770 491439709 584744364 230233051 388325521 627994163 467718259 146818872 326265545 232590300 451545935 722319118 634393800 531943018 691644537 136976638 867471050 361715823 405774724 936816011 678448865 476622436 29003589 776239777 529668367 516261644 465054193 67575142 755783393 461421749 32689659 367668380 84915299 105137743 288575731 39704896 920488465 284216842 300716488 551930357 994569580 528877493 381796245 206811434 952069574 965258413 389853209 333865994 837819853 766552069 616266821 512185236 166670673 278124881 102536876 109989652 206624604 828279565 137836301 866437557 234976606 515298009 515593588 441504215 581175255 557197080 71177417 313167011 340823292 195758152 904906534 500892377 875880586 720421735 742001709 336210020 127632787 870457498 415820920 366588571 939235724 764897174 989611366 318999033 846486383 460862092 78734914 563290982 583634789 678674210 605177118 224245432 650183694 459115202 685808461 336022609 703573688 824957234 431990751 920913457 708501513 637656627 198098402 690360554 828640725 844970410 581821206 304211727 465070569 170278781 730189349 156110797 200138429 84455790 414934772 987545432 792255646 579110411 750195772 232610620 663394528 137821917 704776333 430113326 728490948 877460375 330291227 330803182 489866314 539320548 690333369 722118584 46655237 396980027 251553030 996602422 685366498 610522178 600305685 399713106 214618089 902833618 452205547 309032789 243099278 341201602 99407174 282388497 430696938 863565086 357041153 19677811 878893020 546777704 35886766 801892932 648966534 189134608 417339521 20918932 189089069 8839255 437720310 886304413 285504037 851184989 796171946 28051430 92325853 906360047 975780527 637738754 117631628 426630172 947858847 76903746 847976219 901644245 565621144 249983319 816709031 812585806 745839306 787544012 201600514 843077447 570889499 200848644 98791818 855336237 501372564 435811986 470167258 960094420 479759376 285795016 789404010 548509817 675853226 30005799 437402064 353614039 778393786 130439705 237027335 294305524 484843182 855229701 388926928 17951779 382189278 726404804 450206327 590940730 114247091 510319060 756703224 960034533 722188214 907358695 143185160 49456054 911824766 964599262 434792631 762269188 212137858 33465422 590533169 96762591 78590123 248503112 467510911 543772092 885102730 873607956 58380433 705154743 108930003 681197551 398882627 169236794 589458830 410759191 555712859 377543780 714633652 869959193 836524269 348071668 6554152 653262581 703822750 824232666 263411125 158332749 768781928 468073695 260709039 387379573 202683240 924577371 213283522 232458972 642378309 260849668 920066755 332989078 544035557 478277582 1782748 935747073 238123710 723405408
