20000
920803711 774512488 479542996 298220252 978148910 8231081 437690572 822893510 784316565 638180371 991308004 837438623 381187841 612146485 552031286 329272917 256630685 215907982 196085226 293636695 336578460 411749183 61874859 493119585 535919977 331125946 411971046 339483688 714755925 590602938 844781723 809352921 688004331 538128429 196304443 337243826 679427980 776906079 900522200 689097951 835704189 362669078 31888972 364254281 840834254 473508755 944137168 774531066 80731232 444696698 10471146 319295850 984008887 785595504 454760520 508524378 261601571 294829527 917522399 340998820 836263607 825761932 33187138 762430445 427939321 496745515 767551847 386852663 685894455 969275979 836391848 159270856 435030190 831945485 484075273 173744005 368116011 340518548 771848239 692067418 192568326 82558405 770830050 784738667 278686787 504312163 680040897 757190225 45999724 216157736 802849250 583911064 495332020 466353786 68382195 140815284 418394687 749363086 151697402 338915995 666549275 173637667 970682354 717354983 41412789 357351699 2779370 916126485 661247466 579859757 468409902 633909837 616895256 545731916 592612049 712968817 894335248 114167448 989752272 5580688 921146302 578237956 50662940 308102243 2396349 784237891 328629239 234616898 635747903 880785304 217493387 91260021 550142938 208287473 673340856 944914366 497808915 387615015 458138189 744464508 845629885 770782438 196125730 797333727 205742971 509924818 635585496 392195415 934568003 319410877 936480819 178287978 244637550 249991703 189428152 555747818 822657168 194794491 125069940 512944071 323756199 97766527 175188709 343535283 480003194 870637520 370914072 623606374 494726502 188340546 288123906 977138764 966823245 761404270 212222835 428251675 268400216 494850635 379430645 4309143 888833999 741403548 226788604 530159144 580108142 75871686 222999666 813042243 494167479 886978079 745382510 991733706 522730245 771913655 770261925 913029671 913397008 161730217 134477757 400762172 292875218 733081073 894151552 38144209 144097414 78767556 197104690 253451257 328782821 804304639 308936498 124038589 508705709 732073887 801073354 25949435 733697027 64657909 288774037 875843019 454291948 194518801 387912876 30386721 905019914 70438358 660066154 84394796 124134910 688322849 324881291 894579416 730435930 985042229 866964372 409802382 830406281 875756226 838989764 987949712 213701173 204251774 908063184 600612389 539701036 989209191 784770840 13200163 317667936 863492169 244603177 826695644 820539428 623974438 169486077 491229381 572738234 521466878 420197596 159528929 579187166 222834666 468150555 922345987 348117896 167121278 991802676 478937137 699560476 308047496 983712905 687117323 494137790 803597181 39369730 269997421 621615804 623877271 108750400 443540316 359840720 115727761 688020051 823066763 777331699 842326736 779944527 361640937 839934040 368264940 335901776 203583341 763572504 631145711 216534693 42179992 401857494 409452028 36581033 306942912 639980748 231541711 507715393 976951281 782637856 540368082 220602774 240916752 27432753 191286918 198778951 353161249 203300908 617141546 854044939 888073345 628575939 430702532 215808165 309877472 504476946 682826448 483921771 684641904 122983084 590626790 161309044 999691255 774184531 314613044 510655018 397707614 280570902 674320609 227920689 930426687 826966327 816086377 341707518 108127542 247659308 663319145 700533645 380671461 977850494 488413421 652152170 714295844 324926188 577150742 600751660 141311918 202699971 259966535 355931434 880845698 663635748 477491130 981019545 250472284 607214556 21960545 957450226 918672276 251956765 697852221 753954932 798739372 699696829 456434674 203205369 7983629 563743947 879265535 866719416 107922918 132135170 10518311 329838092 941695038 191815831 811328762 609582939 902850216 716842289 872366394 550881020 129876241 369550670 586666915 963582123 972268894 562618994 759092486 957944015 535991397 941918202 352396650 302686203 416387447 357202263 162244682 64503610 94485905 980168297 645957023 95007660 778956299 310027860 680979016 479254303 931844858 461439085 146833897 367903061 9617471 826278657 547836274 349001377 894637125 985755935 399690856 841514195 341975276 909346744 646933794 110121447 436958105 864634890 701825731 530989499 562419714 846188927 42560714 396385515 692078965 653822129 516990803 403994003 50903599 669317393 29379141 390344446 37870209 372884153 573495106 760777163 782960545 491199206 318085854 776449364 837507834 173293410 452037577 173650853 66525537 733580967 414368834 391215260 344314742 442305830 753147898 338493927 700884289 16806286 356634171 398640543 302047720 346215294 377555781 247398677 684916690 253222116 888630636 935738712 56395634 873025091 353137286 851295999 579326382 579230498 834543767 30941574 533531162 697267755 880377610 764466357 915966025 664926680 133599874 792069263 541458676 165043045 216539459 115265658 34682907 533455515 462089810 169920415 395736864 550134823 1125598 640339759 711447760 589107542 666618057 625063482 617230872 426810994 4861204 881966492 270521767 202654588 816806839 779640222 895326274 359532566 673104493 196121484 167824574 331187565 330707320 756268942 644348345 263023616 278553678 381119587 630095909 220312786 203908344 74888560 487420918 578803166 362515894 286752397 546681989 676948425 708836216 333165273 735054893 852254927 894907189 423467588 494964413 644768640 676817197 232453223 641871138 327186608 330823670 596276633 316496786 858820273 953799091 453549031 891515402 483588505 503609957 42888654 342810951 981233157 968584358 726501690 327049250 897373279 574897257 102688055 838743268 601561869 294913882 997314672 232348922 984376034 598944289 777323433 768484538 29485801 415892542 976957030 12786324 347156209 86621231 537883578 287376321 363809516 856497495 922656572 591988005 398766954 551089964 686451654 768084166 952717703 883803183 357910648 191862382 527793542 801886363 880698558 825395544 420693660 369195301 513569551 540034503 818642994 15723502 979277164 269561046 834738178 798721905 865533684 717553153 465114022 979769051 243865652 189349936 18057742 625470187 703678446 13917426 550048281 703663047 344117307 170904287 885940552 222715880 78855003 980572854 378115970 388368096 283343027 555685123 997510876 817331826 816286227 333022943 471149289 840539283 937744096 899406124 688592161 154328340 237849412 656161474 580853262 761698163 590601704 808524349 184040518 4090234 899730035 315081955 509375358 738730859 982586825 498868871 154387345 664530020 447144776 837627601 158983142 622579198 731703435 119741723 44495593 347124815 660619720 907419670 337625524 350029928 92803456 203647791 926144400 689240586 652972632 633907240 480274363 493816736 34121211 951387997 428624000 700544899 360768760 153447410 823138415 650242142 412688811 4420861 337479281 602234193 955267821 548112444 491960954 291263997 599166590 589320866 431339041 382631348 688740266 472636650 67040503 769181226 20750798 310825174 371662187 905874224 822904489 983054644 169645436 767874787 118488535 963320788 160287328 353443579 650011409 749396095 686902892 976286056 463368760 721955359 869454671 804797446 904646392 713234702 559952277 161353161 478024208 243602803 496799852 946891888 819974496 619135680 515490975 336232733 298272469 456681439 563251693 486829463 21611456 465267352 412111525 909427962 519639705 843506621 549241858 428552081 811587042 253619499 405250513 926843148 136361357 489693437 522116382 287213380 516226203 747369074 973687711 349725479 835591475 161467937 538406931 957781553 507290122 38676381 730429062 135614831 848573041 719370881 70319347 228191936 268064070 446603909 244430113 224748471 273211899 101095342 122152968 926551642 597513489 640787213 58370322 819654396 538375391 514677968 551684021 862673590 271268036 708622620 436957490 393073299 760438162 72797259 138300142 699796421 863319185 192332523 33507980 901460856 451355608 11796853 548787177 853671993 214064586 59439777 165645333 62600239 341879237 10674526 139445404 796956965 669330088 54107383 180273866 382708596 997202934 812978254 566219043 366043405 45669746 213701200 512415969 432180633 778892351 40795525 508173984 618118638 966490736 589320831 999535573 56562218 941848776 686049091 70206186 309351984 537327451 19892740 637378444 835849202 306390754 303099151 672463044 301221109 724140886 589352983 187045431 45107449 449598876 850231013 299449272 374133462 537015691 192884727 390226480 933032298 413882430 748874909 552545762 407919951 301015473 416729470 530584081 612660544 324607379 838587200 308120364 638486727 943815263 32229092 983272039 290723823 8658205 55081305 686265888 521336681 18346661 329399785 132796234 948314225 561448306 688307968 582551756 949362959 190507305 217917190 780722133 240852912 835761565 792778571 944184544 847431035 274790154 45408105 842631661 696872489 681589264 236669307 2075343 625287596 946495003 283968228 496414899 307432041 268860806 64541790 344541609 708307165 356450818 502988791 853097217 172550473 441321627 489693642 544393845 66374456 36019677 301139459 583187845 737194944 460597626 842141192 809050981 284246047 796720064 734266951 971739533 465607444 369319251 682603456 875093113 879597944 463092184 917546323 742167240 81013275 609352650 183398779 387477643 226583732 143704089 639757770 887083999 361393553 639768003 435057871 167298912 909040683 378806579 344339655 407413840 342663527 295363925 153930999 612079471 460760899 362310623 148265072 523882865 735832647 246057742 492298225 245623235 875667041 460004897 796008979 315622170 173215972 664689372 92689187 546003707 246140136 807013239 293070273 179343086 439052144 582772403 444656403 711075075 502675737 97906990 78138387 755662759 793146960 337932981 183250720 449915380 416548019 954210310 491049654 484725155 879312811 599734423 495840729 529671364 820049468 937389127 749484991 222201131 369808304 264309146 913249096 218071074 20286364 770489751 183087475 667745518 508462668 70368222 242158076 253811200 421068608 41903321 749003725 273053258 603413006 6764720 731351573 625386565 995568119 839507983 465517586 899894755 641463471 937143170 621553479 705785780 517035316 765775220 771202516 864583488 635508 420489119 449831832 629123917 256262091 466920415 358175616 25503715 564578988 351236316 147079880 223244102 446392807 369432021 880487396 24198188 944035175 730820541 145788479 990362243 198273965 820567492 380361984 322396647 411464714 699857573 103992524 853964193 571989644 22074851 304284340 949099235 874834816 933547614 871811774 166806462 183511360 550910166 152315832 462038211 780369717 258293257 59295235 676438213 366047939 433543779 33818784 856735154 999918924 981828592 470828785 636206402 263822835 126502947 454492893 599192294 940840685 593620545 912439343 75626203 305832112 23745288 78385739 460516049 255556189 555723515 345325466 232142946 156560970 581007791 215196306 737804153 799224341 37001494 552294045 221797764 631641584 632372745 58822687 83588897 312013074 615753783 469711356 418802584 653498501 931993762 480126597 678579164 702369998 802195660 253867653 489080726 69756275 697163862 372025297 900374850 368130205 140927674 730531731 346391962 986813198 190867579 103023938 853188030 798124813 103630441 659311830 81421239 443667183 972535014 539028439 418950248 960156928 899107927 668005882 484554661 522160537 663461669 443888224 23169386 739880589 823522770 553933097 754784002 358044859 710457374 432825389 960436978 253779054 188262136 247297013 884703638 786240949 141617173 755118932 294357456 629972439 194128821 438347421 955335953 452272109 967678091 586686606 943554578 744405109 682773953 442627346 231564272 862543398 179694537 209638895 624184545 784241807 329863939 717775909 611262657 152197297 819646889 176215656 644592611 778857272 73945392 428307899 603383625 422726351 957413885 552428226 569589885 74529635 253355698 216093111 554924413 737578288 20079811 94472604 229959669 588434933 446525707 884879194 650609228 153280445 937618080 197136581 634188113 516816358 277390521 914603627 343585829 718816379 721724894 115670598 933237254 870331888 911670339 746494429 84946773 474346030 567753878 412438038 544311311 70018965 396290473 942074424 396034035 731897968 911856781 58394849 853974472 906275313 996394952 574397753 170067545 606047427 752234887 563356861 244067228 884706725 324426755 959394390 542322424 495300723 737517395 504728839 723762988 198499416 707890543 363650070 263081783 837192129 222429440 526323662 437313483 164815293 743025316 27812736 443146203 596980523 804295793 550654364 935842942 350737744 206876554 337177482 888568687 849161626 502150044 188209150 834538350 148505169 789386738 790689343 750578273 241858892 290003137 705932852 971212609 830560859 198407275 342799952 727937834 362125445 736194620 534688813 449010194 997692121 817489911 960079827 985804707 916001314 161723700 439704279 157977838 453110346 77783246 724985983 898897115 963286275 968372843 357984633 662515014 626071089 354713852 484936272 378377646 79341021 995152452 756497874 134978838 803905771 296309601 81043933 126003405 4164643 6807507 746063660 671065743 144830284 491166449 84135271 976429748 491395560 118977744 42603606 372881102 30933001 910893950 863391267 444403483 693469374 756495142 884309223 365982966 704223463 474306603 853558597 827556832 250167229 659261183 766495398 707478086 860298966 266399818 903069053 32407019 238330298 321871402 659956944 64402431 756120650 930463363 152254592 625071362 244667884 837027609 189078139 427407431 839221298 270827379 183168020 661688440 390753074 845711660 33032125 747522863 301162590 371206311 770701270 821772449 22666872 114430705 592804057 10764341 108251522 396684347 55478414 586631907 142368129 905374134 199826805 14816138 80072127 687846811 280390833 144862965 167536842 653794844 462789933 296885869 512865633 296511355 216509288 24475353 270392865 831011831 155393175 276378720 682836586 548450387 832473445 962757125 668417694 235030189 877169925 282105378 448717163 129755376 996851705 397940914 122343935 884709291 151486955 207935480 725775405 611045822 429915447 751452972 19498186 42775833 340533680 258788397 372191273 98235206 92814023 973910779 424452178 70565755 729377455 870137379 630054378 976081012 864048398 945093457 480904143 658119548 144632743 591112768 314537838 157498001 364915183 672588726 735600614 734578292 101255712 985258968 823466328 122595595 38673715 762333266 94017171 319245194 316667447 763059600 336208523 274311044 846600532 324469542 46023299 907266936 735500854 129282626 701807479 663815450 852042413 5319580 21260180 573958612 305937191 469171060 693232023 852256617 880190053 82150822 432605380 238224951 599603648 475263829 17827876 643520404 326705649 147000454 222721426 580384546 66228721 742207624 998817875 46798086 736797931 724034938 739423828 941041426 183416127 76213810 948850888 415201610 941952779 573046298 15334416 823174296 580259489 555659178 388535866 296597810 44219157 83930036 580534216 690773428 915028454 100650504 534663140 988051343 91751539 383651869 110696144 628465480 224735512 830182793 222822288 527683600 940480621 68910469 957741499 840825333 651354367 706313896 726444418 45111782 927925449 205786256 650650976 131042235 13995645 176852283 201715608 559473478 927768539 248482457 141305804 675694144 583844241 747774182 957716652 530597019 183649292 431115068 465306592 212999884 612620972 447584081 555624610 478119232 69055009 556082234 577361117 401608786 221015694 268326189 769298574 878665258 892417973 551943666 874880698 271551030 381352940 583839489 676742181 953290766 728312176 502824762 595503567 30356284 600906470 935053680 137297579 689319811 657828922 733502110 517920892 106791644 505894575 520014648 965055413 600532506 435281376 612402733 420305743 947332823 419172765 94895788 336483614 614394949 923496246 175342206 461338636 491518572 932016112 50481668 833384090 483538160 857894317 350619978 730568545 248134275 143544093 548601437 402867044 742443153 646985022 875178200 746573589 526653408 86778948 549017362 624908768 251712219 514101223 887525554 615086446 859226097 796471666 931504335 677414180 495081383 697581447 463743799 654966091 89161511 121355485 233480022 276957093 795479446 752528770 282293055 109224627 27351771 301749800 705017328 806495476 254366121 181450031 148370228 22244967 886061620 132972753 964111800 231625832 327500302 729565314 296919216 732903522 729674175 639187746 115611237 844276032 160313639 525935759 238873357 272928079 999562013 816475474 380774708 215037143 811454245 585973191 724901977 183822925 213671523 773127678 91103899 467972374 827854743 673528619 471515512 790192806 986934677 902938647 655477989 696056225 355413990 824255251 183950100 245067463 108774126 845495452 164438857 672678403 936622416 891710006 375666654 92487429 889169615 600482820 409892816 970491517 672748710 62703613 398850366 270672611 672935345 676553746 978030819 218727193 824866134 823633358 921303565 512293110 562123858 416394853 939489102 30463304 436057705 757180641 31498356 423635583 25830625 526073134 106671480 491812061 599556113 829696852 413925092 190180651 5066011 974571130 748090151 864519181 494172310 606707135 297525425 524744621 178183863 341763325 641724034 929577752 617117953 273223120 780072075 362787941 818172840 468745688 571188073 739968870 127783737 132064212 380409328 597791154 846578443 714410519 799451900 163633912 316875264 327354007 945847129 530844046 550086824 749842190 952871209 719057856 31425614 598764548 612708294 640303153 236530692 573250347 309663382 293204107 44976999 577988177 848218654 954664057 84978268 276477113 368036079 855485423 386184199 156616598 923308807 129949656 663213703 109031889 176357124 746705753 22844623 820994634 159783880 615042246 823528060 972395077 632496608 456728302 623042621 50625995 618564480 997284106 690303752 791130155 69856008 958165974 940242437 757325681 690055619 784573959 159938359 42756072 777440113 344160270 575884595 126435216 119456303 114154181 12490808 407512450 287105965 709262869 133969423 570689248 839339493 644081893 313835175 192192335 947748404 138482970 938316542 791941871 593605787 676582934 925599326 246323707 859681586 483220828 556393061 605479936 606095553 537630192 364295469 634797759 635122965 57042296 99894081 33531879 500756787 649069286 532954414 74501314 43008061 456397172 211742389 927063687 278988315 136558412 384661881 115323079 561404458 779781004 950913170 31972902 297732744 330880906 775376559 571428917 726839776 608998240 818583088 192769303 89916353 507769042 581697651 618164312 366427866 385204414 861969269 468476946 771170167 264579434 232007936 896006443 547346556 26823732 923380397 483579389 665469988 983566574 883416558 781763105 779541375 324991364 153865239 452846714 924371603 554001157 464497319 382433284 803827535 226793445 940326632 12930276 813008114 144919717 612027588 221446023 550291138 452169988 821236517 585622173 374422774 855643777 920225647 199744450 234898969 457806960 153703166 110421045 358259956 932793911 330780771 871584136 231905987 632947355 83999858 486769386 522141983 98144533 252723790 537883983 982577045 523365611 876642213 35242147 86725752 727235356 413780915 48290637 532943954 958361443 531439064 643286163 102178581 110979869 890392459 739122388 22891572 589103949 232937268 395627472 234552396 137042632 345784430 110961882 182373875 753139939 439458357 876575732 95335829 539248025 807979973 637543558 852353336 755880169 16352594 229905469 486028438 111254039 981038724 469030707 505404604 703758570 382120906 251027892 929934632 34057790 933709614 602669034 647503077 576868238 921740221 177391286 31950479 275778995 868762969 40138486 590949083 626946701 707361137 465969371 760825846 585049657 270341590 497955757 551930729 711220171 266565651 439335944 590615167 624984072 522753475 20497101 785031886 34728318 693323048 645377415 183312968 141453840 745206801 220204967 896825248 662897513 469595672 614634999 942799374 320817763 631850988 626979 156222032 915428791 906109337 975931196 713785590 767907488 426154153 64299371 747003689 886530137 410673495 838721768 739199383 17857718 805382463 28063755 817694825 362429361 942344405 989690676 148343056 198184 212038914 448354206 34803513 816078516 992057011 407850155 707541404 572393249 575741948 931448512 607169425 982312173 458968900 414582339 621584612 858008253 491336793 23838058 725728498 542620691 459299091 517124156 327645779 511331680 196803982 468764680 486429929 134038930 215008427 310895714 773314051 375025575 49218340 993140076 377187669 962352347 133295290 81733847 610845020 215537751 332742706 612083500 481097669 340324034 776808731 823759651 459171391 813790366 175504348 576261954 59623488 356166583 489910563 376702298 559615013 268936130 255539782 636879409 995642947 307974036 82255497 66107778 186624807 441683146 727798982 155300441 361328918 610185039 992154259 887847161 381135722 254647908 434992575 973668644 572680240 464263090 820963466 274369738 442119441 784529234 923089569 67796132 72900248 398537132 853229821 533973487 553458080 291659628 558113717 574838667 486548003 936696961 419054631 677636447 855467242 744779094 857515403 941962941 132688086 19052623 596829674 416012349 843017629 114954628 228371341 189806779 747169397 357749884 262491816 96286577 788761941 536401590 219749797 269007371 571559379 508797460 854998591 145072407 952967622 121579767 812407286 436801676 591268908 400799344 266282578 769777402 710278158 510228633 595255984 148378276 879658668 170767660 377998865 69393866 182692486 764046296 72043633 19936377 687436363 703116846 798647354 947585163 225298689 331042900 254427281 599022503 670986801 762335066 418804619 562928278 297758318 724485945 579805417 776649826 356710231 414010547 225417860 406981405 339203015 830622714 521920921 360696650 230762420 827568074 786638656 730016247 95376806 17911384 840069387 540796391 485251740 647985094 798134129 783276741 160913753 372320423 614975877 377026520 199304131 706282966 800211827 848187022 161580392 578966865 546477576 936428792 904665594 872330555 826088904 168791199 721009913 842514415 732217509 617631335 204731225 137431052 890779990 381455061 806428896 491588214 761480944 163703612 462322111 563738215 862348966 863019590 358921239 823158693 965758693 811323241 777083614 692549820 225909258 645801177 745664613 30634221 730689294 217551977 134450477 109928583 74525437 137788382 511686104 966627796 941870700 766527006 473518020 648500300 56190930 926728204 372501102 946210831 255686138 793549379 385756177 795916801 154881237 486300694 906904582 361811721 26255656 993851169 124756234 970232020 301060065 339428567 311317978 359718745 671758600 591945336 691081751 995396969 307890489 58634962 638929348 871731365 801343977 693748883 436511802 568068940 222132549 628256560 750901753 713413098 860651943 921483766 757611892 174751272 53254209 529255213 461502486 275397899 102902063 799823698 679676064 680042533 591687110 645855398 480892585 891339811 965155441 532264979 237000833 928997328 761877885 58847428 550838009 108288596 668963333 822250998 703219333 54234145 139272229 104317639 976723305 265722734 230698420 850768101 627515753 314737327 57330152 261255812 777771842 983319025 148060849 633907160 570016779 822452957 376889104 375733959 536359165 347516816 224301110 195663009 368887102 661626264 132043973 982935763 708759182 388789215 274064602 690646470 680146007 559715641 443849258 896928553 891831085 291097527 158401517 8542132 877668896 433842317 213304574 330868576 443266716 713233620 522256771 749674714 973316971 711019132 963500703 853116835 70836256 758115183 623554583 62319751 969809953 544704743 23033440 165763832 155459492 523637521 987771591 367548191 175157253 250922553 156290683 45513180 75219873 179046651 930465021 218814216 358877206 209970539 671161252 799207766 212411818 135582515 493310664 604524725 439889751 790059126 268688850 439643318 35432978 566421444 67941284 686140645 438332487 570609615 31728358 403849721 140290272 974892645 889557384 179031871 31753620 565721656 383115875 228340292 819070863 545670006 758783071 481114156 759358798 76930403 814588003 888757771 288881871 748165855 112091644 823312444 822125450 295250561 285864314 130405959 674262984 384505078 742239581 96039375 17698583 626990254 263040705 124346843 128621919 319159610 29464506 4081322 934102900 351630181 238215819 905056297 678737868 933414562 778364378 948760210 493940811 592284696 858913914 209604860 213155128 890764813 137898705 610746171 942754336 443154781 350259085 195998969 171242200 625664169 651581258 982026586 648253846 715425148 404051409 991460331 267114609 382269040 190083212 59876335 813884065 926519146 168820792 812925381 441759481 805381882 193622077 124599031 189235300 781121017 481922229 842869843 274783395 853224819 157892261 2954644 142854433 414720505 197938598 872083767 538677986 234591704 483043689 149741028 857898690 950528748 431398824 947206537 279113647 656575012 493196055 177964197 24932189 456712020 560066531 86240487 925321882 813090195 986820588 784102408 700594367 673804174 195137915 137603434 158125962 616781838 450553786 587756730 32555055 894151169 448989362 577102972 227912353 465507617 452133078 622255781 854727202 27324184 155656532 203229963 135218366 175521210 947564468 210218578 337637018 628442242 893334415 792429495 825527180 802413028 737684244 97743178 730512824 348560162 567432156 542814430 177034084 736869473 840785732 746248676 898346588 290716813 846664998 229293892 844590107 715512437 533589169 354795382 490288428 467775535 84755285 605964355 559780342 181605300 276243165 942519807 866340701 483392591 949367676 782476025 994796082 368980856 738735679 92726354 772050066 892503449 12125256 884239798 157984835 559725181 929619291 829774936 327189679 402630619 425206384 956206630 556260632 296575449 264548467 562247284 905013025 324399536 246610432 484080555 42596091 93671522 931959511 964461091 844323034 627181288 49166743 468075990 451366688 789123297 562142630 811496813 310466824 709346848 411095728 451724221 763815103 472667897 767200864 594978000 709072681 230074614 390411549 178368550 787372387 36833983 359695891 928758075 835296352 518797538 153854945 429995625 387598122 384202414 36085319 413885780 926738988 703967191 883311457 341426412 548584355 830930666 228644287 940352183 777357594 688628006 643527016 433441867 659468159 517587553 476737378 760322232 554720175 507834322 834427868 248788247 73296392 37231616 811108021 894718782 595983832 598469138 760166634 771272545 443017178 100641998 450057721 16454575 540783849 270027383 820680916 979082847 189992146 691276186 741857681 120284671 967237694 31287801 891668096 105863872 201023399 711673846 440732272 40455217 914464818 493270258 97439942 688270000 326660035 645751061 87260564 98568733 953712234 322701881 517594955 852662877 402381374 40072498 426781811 236911466 575659721 157464482 819332994 73380505 663531858 204576735 391388508 853918025 650048897 298860185 699708129 322121247 642973714 669884999 862594863 555685335 906331662 575074773 441411198 278918256 745936469 151886812 891785298 185765531 161350098 508245765 459825577 745986575 735982995 404111006 203925309 565976296 382558628 994284480 19658675 569094012 185383965 570604150 595199485 533737659 994974213 832881721 505810377 634820043 927188316 250758054 570874115 478528354 791203273 782604205 300540096 613154721 113687393 712723262 63198592 90230919 135469318 811295152 29064596 2600298 606270264 556649646 25397225 898452014 10656980 882066044 92817729 604758125 797785244 504392175 841556864 625828426 287864966 729914244 406002623 16517158 500242091 386035675 643595273 859095611 810018948 136977924 837535117 25989701 587069828 725758525 693034166 642550011 435630753 360751941 872299623 669096277 593512691 948111712 260899553 478796199 325852263 912861042 772511014 430375562 375733309 338626420 626226741 710143944 319170159 703447790 389794419 998888425 868580720 527094520 711969318 583763784 199178455 95750534 102624657 298873328 46288669 226275932 741985687 127065862 430781947 321579309 716325273 970663376 849456469 548946569 379349193 518608010 590370624 862163924 339303424 804086914 956251972 862788061 751623439 581726541 285925994 161462186 569130054 94349341 368045999 297041802 220315168 306390136 778775547 549650069 118131162 71937354 921872159 567328823 157862933 608504589 765593498 442282306 549991342 159594844 597442315 217793058 587959410 494814216 691674481 710509439 184901752 981645213 922521434 254361797 907702234 143358920 833791844 452668687 237825558 921303587 197597479 30742327 841993371 927373258 540004505 70780734 451948958 876376182 789052693 914565317 86136220 563029148 684261053 427697993 308613656 931381548 867927166 653244029 725035819 366038450 474662882 685480940 342029523 497973829 231581016 33919852 64410291 565530883 736893767 217273034 514244819 215371909 682911018 63270167 43869349 723129005 609348048 942600350 728941754 854544428 918504645 862923226 571839274 764373617 93832355 298738893 203888639 574345849 119070018 931013154 899489300 209325935 903403924 222117229 918400519 969322230 971328949 266432544 586441521 755797045 263135815 678131231 260411636 780862227 83357482 38953820 571313063 424027130 679473568 825148659 844623553 269414667 539596869 576236925 434579944 8171782 366098902 988559272 881620923 837112236 817358501 83598893 535370275 949897632 319964952 873262651 698689352 279906674 66215858 478930235 952157064 467261810 364570187 960688161 617882020 963341848 592603925 529090547 62539917 696322800 497927050 722536262 3860737 466076820 400952538 873808278 536153722 528302200 789366702 43378417 43838493 579951809 693162193 660479013 284469111 631089900 234859504 238514469 632898586 626996036 164640002 73366208 775814622 92506704 708680920 776338795 411470540 702885678 803242439 402845445 500996291 918519759 512860902 419630019 913188364 232440499 75274225 284247251 36813599 235283482 350204679 899468862 909434425 284547592 726837165 980968802 151924834 691643512 569432163 697903165 200924407 346982145 144136424 581785976 672520450 288044327 766984225 906221714 540183024 462034047 379870771 480902589 415232684 886869953 623377517 776850976 559527650 3056999 225030673 770976737 679346542 663528586 323404974 475340881 702559319 529017789 302624802 633589924 603604053 134357020 514805680 749595969 717341151 251308775 223269326 92930619 835380747 104176044 345077067 30531073 720718408 334878716 83688371 723390591 898537791 493320121 92170212 568314642 55070529 801356840 806172342 274319229 295362217 911869580 152601227 62395408 838967275 954775857 203726541 388099410 942486239 870812144 833405332 660555363 548428754 819793007 433832830 681745909 137153216 678580991 536080633 107841656 199919648 222624893 705171445 714250076 721967828 41591758 650506164 439035189 735062580 789839097 902435055 102550321 631985333 85460539 37719821 397354959 356642714 94106076 953545399 115655448 982227908 301393751 792137638 359147251 36593935 720128449 512362918 11829979 780807171 733321466 312346950 639386996 345182558 927368067 321085897 825597884 909074778 917760614 123283053 409637703 422656305 327934063 248368338 741941958 938371476 136427876 55757061 298765393 419906746 344376337 998269284 524326763 121321880 188026546 36513434 32473814 822541293 491396432 709033125 829493320 219625751 336563899 133227316 829499598 654293808 642428392 659482310 224962820 786542110 226436078 293406831 195194337 683295936 575320759 227466630 926985904 304206426 956592201 349234543 377661830 147312460 899621962 124941162 305466902 855915307 256806880 215232108 758531103 36561192 967947575 11790770 266594019 477695460 179808522 327819175 94350593 353548864 850090855 402162007 953224461 991969930 31978459 902833468 484542385 80934726 162911861 449215169 275518326 814939901 712109574 471026377 507831254 228884315 84798289 701246992 7122442 748552357 145045961 894438082 973632423 314119510 372350010 730641390 327806035 394490350 731656191 62146092 802656756 446338867 730040580 495396054 802631196 912473547 922230723 774476261 652336035 974880691 428978991 912469340 104677513 299590303 630450244 642551480 741274686 158171134 569875193 850846112 885273047 584522957 467689387 230239112 760801296 635295424 553393595 479467633 454459287 584416909 5841883 473776023 579874017 990320812 113027196 927529436 748978734 605368868 887768591 514776997 75366011 304927576 504815311 999378123 812209661 796553810 889218004 949544730 986850365 511866010 709047772 159064949 365080874 628695513 957998978 247116790 844086962 198701679 914511060 841911079 778390913 223074758 315282520 865850636 322471498 200335289 31557572 697389392 104703923 525811354 734363651 750854051 180790517 916014339 914348794 756822379 813538683 686310550 437690962 129940466 271420613 107415423 544727152 897002760 461915852 65297585 65397936 858964407 827981981 750597303 554951993 157339042 21142885 20216371 22411049 717662810 50810072 454093283 842642966 76214300 212104076 582447125 622314875 82124060 149670001 555146023 876685643 585640462 196068716 999498692 997009502 951419833 414763680 445651923 229789903 512935236 79391022 603287104 681950125 235134929 15327758 717737142 102453883 243397979 288051898 845295802 223109997 459057003 523065840 469320324 204158126 609412375 721441502 139511482 172218545 608373493 745433665 40141510 543181738 984629213 200701709 636315946 114794646 353663885 259084431 655148538 405617813 590224368 828642 284180755 695116105 189800338 440247451 292401947 198174592 813246336 274152706 708284283 924882378 2195284 774215030 172115294 713594718 929562243 895057741 454829367 897249189 557544156 979805724 389002444 657628921 715300768 55080373 349418142 843843596 515551123 535297264 872514151 315142224 407142430 457750357 538302269 79083168 758844378 607048509 816650630 286563837 9507246 329865608 760355224 25680329 452485243 899398791 694382819 26144699 950237851 864108530 129066430 860459595 17151890 522433736 499650298 53056110 806152142 55357904 959175848 44444686 129459872 360898520 515669923 920623206 100763616 131652577 907622000 146780171 361921201 748709571 180193292 561051334 178834202 625733293 467900436 815776295 126654125 453916170 236698523 823134063 605663834 13149323 942462574 17803793 91452855 481560510 336024132 25950354 868145457 507815911 351844061 485589782 78269862 861393053 531093172 232952279 634018250 145030171 890284707 399666616 85644733 409105941 928307467 390579171 976882942 494316042 149158895 502976410 681631109 264892081 605936792 908476075 34273964 766060760 38518967 21385518 694892238 767704292 657942649 197568099 147415413 115871743 618249855 966437458 241539076 546135658 745421557 62511567 712460538 186476719 148277562 992843103 517469986 85951848 83763724 246947314 141232167 456229721 557076417 386640413 297328699 870814936 729909250 461628496 290596693 373039681 655259563 326319881 422470738 361495953 816626659 731372005 735336682 271832724 367198529 345778811 154234771 997989993 972114497 321829651 46649770 489624085 822781418 662129925 502394316 748254715 158481775 616894281 140355839 905487003 246469168 74939882 440413389 419332866 107037819 733658310 50950578 348370622 322664944 177065349 265909648 214651378 9653758 221546104 341517907 737600458 333091854 861861135 41261279 186891293 490806879 966022715 301068321 866065029 686209323 880818731 170549899 182487110 929486464 381061397 545490946 606652374 275078718 274976404 407137227 256945485 223174870 955654142 458054519 914842070 523681263 246882534 321752059 434578859 30513084 216320077 63651140 610167419 194031742 999116326 437642808 123151012 272966308 200802815 163096458 809999106 276864249 2086040 132966319 951228452 112480316 544177105 629629625 123482889 568914507 728426971 40154589 189224474 318521996 631518390 269781496 207354519 18802449 815895222 811482096 247807766 235521132 507250985 726186381 331983551 356698341 981364848 51703241 414290405 784192462 785608770 166463573 647889313 567998593 756964127 532735862 362690426 251919793 288661807 552860200 756061215 450981209 258822705 381174591 168007674 688910788 138229406 881214332 304384232 825299945 971363684 94966769 702886524 6574031 683242148 946763539 239537721 854039374 782935569 636537589 149195812 850749336 329305057 973372849 321292922 536364825 83257398 99677017 916516579 457184089 679903021 640999 174529255 607696623 669437667 257481019 740060189 497626140 660441791 587394710 918773096 605496513 950461970 568435585 772715434 525519710 300675089 741391702 451018706 86945051 627048233 589774732 817987187 339052211 42247196 172251981 793163154 699850927 144302932 639911103 751330269 335818579 358136218 564299547 490100137 425065493 466277316 590451832 171492026 563861096 730412326 152753623 338531706 973073357 282161949 997352797 934361231 238528774 895647299 499624524 463566629 490788099 411146925 301580536 544584968 900015886 461566180 698825578 708661582 934096251 212534467 131146985 171979445 237281636 204873404 702550258 272523324 36102692 367454427 572783275 148233153 388031444 334075994 50629810 789243062 571628437 378419013 325093012 929662583 995641137 568227764 444145326 705262682 104179033 992432534 162642677 592701683 670871400 51006775 774820798 609241310 395467850 978370757 901911205 297978432 105898767 164134568 482708395 950193717 519843141 516874285 397240023 125481867 398665262 365409076 267259751 700880894 732843064 722561033 34700836 301041249 729387057 54591792 930473963 915837297 427558246 118117184 568087116 443778060 582346572 251621726 475734267 450670329 514156855 295567701 853689865 649424847 221794828 871888939 622846540 179298397 127537595 411585519 361438391 438600770 306146589 259411167 140975943 964329696 652570874 518085376 323186317 589495724 718998840 190769988 517724630 598669986 261256681 163769586 453362854 219061530 340308414 29033907 916799385 53742638 395470153 563534332 242288530 50530622 644522226 581231960 233630056 802514986 545005530 18327949 631965816 224716554 523878115 848585913 360865030 809575086 964985926 844705038 158896990 850751218 347447122 993749594 118084667 828166723 872067738 539705356 817776381 632388815 726129494 836871766 474785189 892948182 53155927 442356238 214037895 630403812 277045755 304181566 729545742 813437650 663137174 700471643 847166254 432992516 433844062 708546361 539944701 837928898 184353658 844432205 103031319 982751411 430322652 836016991 909725860 845432999 114247251 169185434 297184611 899778449 926070543 123253726 936358737 733560058 952065441 933234559 548306248 669735049 445024086 769934880 766400987 718918763 421514682 86624608 12104634 183143116 885572381 655300004 211577003 419092872 18904351 952210659 129008321 185060686 814270955 858179353 470733292 514073076 278546310 493700116 113368021 951344023 392892454 933770404 319460952 485284393 757863082 769875762 75239040 500484160 950442235 521528240 518416688 959637408 3954727 470235312 264195436 55273113 203762034 205825954 814106857 258483754 103303766 155069586 815542331 976702496 38388918 433076383 20908573 760920145 987171866 416992872 318053276 795550738 10110109 62633145 939289463 772658498 620777926 884115137 302578947 579392366 165510799 760515678 131461266 639572636 617451196 420252091 903623998 725481648 997634994 803795540 763656007 394561387 660532941 222132845 630958487 466431951 340943563 28993315 931646111 499037489 443254251 703638964 931124328 711579984 3456141 766909129 179556670 740193291 573381193 735588232 229196048 170166639 674220189 198899127 215805316 373923265 209337624 92149423 312337163 320804197 956353974 283130513 66806111 121900852 623130008 600723376 515295976 500746635 767596039 816101042 308153094 472044113 818522230 539898311 649566141 70771385 322254091 519485492 612275064 969381189 585101439 936155763 956618005 28289641 931609840 980298449 934799787 361323508 356966172 674066947 700629287 499372667 31844003 934941801 769858051 982025650 164391813 658665776 802042044 581851517 801924872 131458011 379473419 499988162 315623427 798201389 598900758 262495618 544806361 372136259 566587803 415863470 990706665 922930751 138644018 843891171 93040444 97086505 765332132 421361831 998297439 168282866 56185221 700413320 391677002 986156255 858518914 496538470 90679387 624132468 282188731 191694965 783911801 227695690 756261781 528627664 231584922 136331353 464200215 37955256 870499407 376291934 3123233 183200808 258257988 777948200 919641473 99799956 51283440 766637956 449025021 747560086 396242023 545018356 860628102 210706838 527026320 960136567 25207796 841065636 57984273 573850323 836021890 487194216 125548440 176256745 987542866 597459910 902910457 273087342 802773328 30394682 629827200 232354034 79665511 192204181 323788653 625613492 442689253 447587394 669247051 289580075 936374731 629090894 361352651 800519558 604955236 65303884 182169331 781845947 600308089 918048400 842446304 414384486 876572556 500654897 828768988 442863446 551269905 813338382 136479200 824403836 947091096 906378125 899103840 462325334 656066758 954677803 977659392 913706799 843963812 19051567 61176599 808696013 396828774 965586474 826225632 166362691 769322221 355283076 146695007 17604385 665543496 102633074 505494148 146479357 739222360 274858643 469706460 931767262 328188599 168289191 129277851 382557857 403283599 524457179 200505614 553026384 361357076 730036481 668974857 240795846 113367738 457744196 265767605 518130591 620924012 940685775 19722572 672899942 682022193 596358888 254966061 978083837 258586294 962718478 899119136 285178637 996502709 536853965 137397440 656491533 598740197 657608697 761756486 120599287 83689379 246526172 183177511 945911602 737871709 710509584 477430727 359301255 174919496 608120127 514086074 534226383 296327710 3809869 320482108 47079354 505691939 840122554 512946831 423731643 886991352 561232177 494861963 500275997 781226511 274240623 296932718 623321325 164432572 146174109 586283191 279905193 381886462 849386711 272748205 164393697 356320578 340857904 975383462 520362760 817761187 293381602 265002884 859870710 729483508 767628854 283600749 798739152 297133415 960187757 279871748 701764904 189713412 374555412 14137917 114568658 473780502 844041824 952654798 414510721 979178394 365409922 264709397 122696592 423855207 129208902 162931353 534741756 319908950 305313651 957054536 43571579 866231589 320974140 449966429 706661690 432577355 180843228 851171599 406006361 494763916 901087843 225146913 612451441 613379825 343446893 825650723 991640140 992618568 149218485 810018754 394744569 195493330 963295376 507111530 886147264 1363959 124766972 350263312 908793723 347437531 971833728 861860893 124506685 154239787 691345878 292120395 336495683 415095351 906091106 611431147 508811363 768439888 693337544 686585546 783176823 197196732 592997583 529482459 694590197 173917231 692572323 202581553 244170666 13055205 818628715 845982430 421799431 605736412 981118971 428893840 771709317 207216766 308695119 600013219 977086484 114730588 995580803 364716894 560478076 189833034 727082556 626393769 330479162 201176334 691199809 547092091 469573238 695276488 668967402 932261036 363987738 543625053 727222289 945978851 505444569 11569268 222113984 97867366 22470083 716396798 536475031 382197068 3776036 485364445 84426095 941407416 989880771 313406135 457612698 478284623 909734775 766848475 398378337 336195014 903553877 811372481 517837833 613806849 151496534 984179486 189253344 48966960 842643514 146766714 725508117 869405614 352474439 917230113 708484784 975583129 201160023 94280280 826970704 414637481 74434481 697418869 809484879 904283952 830707262 85196913 280951744 723826285 715015941 446655104 31664330 613487876 215352659 517556635 477422260 738228326 886553431 112198265 462627104 94077563 470802257 663232631 968365826 690421911 468569240 391245126 992682182 647891528 872448253 159940206 213482137 647561626 784763510 198598930 417005369 360542381 394090637 130991541 90905168 392922066 355842982 245394180 909708820 481826618 588548828 637733906 850724411 725855710 898252249 500988357 691151999 529247848 183040660 665960907 807075872 860157718 571942626 188013867 600112723 189490281 639051739 62869564 638351346 102761515 147404794 728028780 501000540 527596097 861881404 207620038 382870522 274991044 826843245 359191678 272570837 240224671 728055963 631785538 461219611 88227337 871590955 589249616 229379091 35557099 558559465 474898462 635117556 214061323 572117411 736995694 902992199 618705831 313809864 446826232 874304869 990812197 980111621 208871297 763122522 401960308 981632801 16319021 884774901 66580095 254624074 837979000 175988075 480243735 856907516 575692813 921703146 289596273 939647473 918170217 103845302 586844749 231146865 444139674 189441318 185972088 93597146 861808976 682745091 702835174 648991089 505248890 293044097 117432466 361299934 701682732 891030260 94579924 943622514 62480671 37294837 42032353 773438847 873451580 970777748 589370657 432681036 885019880 801793071 49751898 686973351 319151427 951217869 154828374 583313831 28858260 849134061 334853051 42290974 341763952 615465054 616928983 40587616 317832093 291810156 506861023 836794904 205543540 588425985 330210503 666169995 222863351 875772532 779291931 61294111 767009796 328300219 593897113 969390258 796573790 120909922 948128436 418776608 241499657 635062848 784219299 860159290 178949610 141545892 108988831 760901745 243313357 336303878 119714073 673707271 84093692 125986727 907070302 911564093 509085072 730791246 997821147 126741362 164914315 713030172 528445328 172972452 921987005 164084541 614934526 678008873 135498581 817232027 249133763 493445684 474728980 979110804 692146096 570309058 904446061 503001477 806376374 632046442 496501665 490956398 659831946 62467303 924168126 731203932 44000887 868513598 446535332 291385085 941879826 837870577 760042806 436102377 508969333 499632117 966216754 120543455 217891887 366294864 264320868 725195614 554101221 484904326 805185167 54682926 220359833 681477802 264972750 43111535 386368208 139638899 247764082 350675264 114768450 445501897 496428178 481585272 15901535 88908661 958798429 644953650 893907228 900563303 328779598 464956818 729676074 701591125 440486152 926848948 412055708 473825749 549514622 279333587 465446705 849961812 567501653 819341875 144122692 60173976 103121324 586780997 565086655 771662475 720450716 456516397 742090800 274449200 113644611 586791837 699728015 863044926 137891032 269984083 630547962 576657971 41869823 892272151 199556191 88266412 882229016 992497429 56631762 2011336 98232416 393402477 50599135 328630818 47161054 1912461 253643217 274726608 450907865 615870802 967096577 633878833 396369694 121425328 971047228 287985023 273148438 939148348 433276226 182329921 438892501 501213703 947935337 795242595 200763799 940667913 570664775 7891398 783162653 805914382 17961540 850297792 812212865 915150051 826839669 878451311 757257506 44571840 587207634 89912112 232282988 401075840 371461867 702192505 574902771 77538613 739314426 988151927 603859296 184573830 181620958 183714581 856268839 601202387 369489009 757314323 46378807 61587269 646331675 952578149 459217430 246069496 811966232 685040739 134963579 979078514 848080928 593204900 96350556 179547855 126220037 350016134 832541382 250751310 707545019 352253690 131457568 371448098 936710752 171097141 867110129 197992077 704512429 285995160 46351528 711075893 795294257 956862306 207161293 123739684 925585317 997878979 686296128 161531085 235997681 721258107 244211435 375458998 600134313 547686858 704383383 416847357 261530673 737345538 363497764 940320740 985718585 513197331 398319567 24706801 578756342 353911158 456670683 747920802 752579005 645183401 399902480 764448495 822263427 482565091 824349690 585462152 588931833 200898861 18853496 349037186 591441491 659732716 308328822 307061302 491723991 543009197 59984839 851009111 823324895 975746970 773579251 489569724 220894005 358930658 487434316 260193134 607097029 565062826 855520606 396183205 727036012 756326420 996718936 781220592 267265337 663870031 160086408 672738516 591387979 355064427 838245270 907140826 199848670 298520001 988377915 81259295 901284013 283237156 150364345 507556644 563185103 304809976 464448348 143924758 276084638 230088954 141387980 336572763 671667585 352958837 8325853 934542953 176153754 673185121 473930043 886793583 368094263 616179741 175765837 989907220 758766722 783993287 785356233 863742751 159589925 410459372 758767940 691186072 854383427 988330806 539961678 42272299 979599025 372967694 898923278 439082873 362982852 410607178 132169947 711797381 472060058 75065483 844311134 934811215 804838165 977441612 577707003 598412327 190897281 488137972 238824079 959396992 946997030 908042564 566256035 666471486 77587919 318534418 475086288 1044638 71834275 667596854 200085540 514416855 79967085 834954096 540108167 723284699 133091783 367870272 212185982 172345643 111300749 84150552 112245810 938795373 251342625 120986259 829778171 266981125 46272431 226556861 174202103 922460127 742767242 43138730 375470472 851268942 406491872 590795082 911789837 977678085 929133716 183341015 799376564 368595953 887146236 322711620 744729245 198214905 194013033 596973620 591175262 486293411 518855055 251778167 434823620 707445290 589289040 266563525 404432572 278151062 178387148 706642642 3072835 461544023 476742254 134190131 743577253 999306860 976948806 58652084 785582655 512968959 121943592 817012735 424623194 983449050 716757050 829783070 144644077 614714231 562450358 548830990 813389417 39090873 833082778 709473535 468570518 763778787 112973685 207036523 431470457 471662858 723688137 793074167 448915486 491327837 370227557 989385526 454390438 719802853 464134885 283400602 34084003 130989960 691803473 504886193 890879286 815340557 809907137 778866372 395690392 262683434 993876410 182697318 352034021 416092519 741953209 786150904 397793122 180010429 57363110 125239250 861133804 498901480 611508416 414855927 625557682 878733864 737108331 429299219 772418923 508330518 505954233 38149456 17485270 600269172 819282300 539229272 524984087 12569947 81812000 409809321 982370500 876869248 77519773 345552804 685858494 403961877 711026288 374765326 102106306 405477521 102854063 419014119 691088612 766495599 771115868 818853281 366954624 814763615 422196104 889103783 750885920 769150188 763552762 97483565 585400985 362163347 263077949 63806940 626087700 203998647 235772148 786089979 607879496 302658780 129986406 340051844 595503919 140505530 258272258 343893187 97879423 98505112 287619832 134334427 970095654 730095155 369204343 772148182 750523977 246068513 251397090 792147097 357977340 206697399 311720098 915484394 726165936 464167254 260080345 200228147 869627604 204397433 465875765 712744247 330454461 868884937 238648141 861006803 597069028 897889359 543318023 546550019 194736527 988760664 486566561 446324181 323327829 184985851 138450743 92181298 691805304 828847238 814632146 542762787 235303307 922531137 142666408 690812254 565867129 901482050 973797305 179772450 758591129 944548703 670124951 842012922 539359461 375381044 407136182 904304966 328617997 933319525 631387991 311320965 832205849 622864527 441201553 965064700 677568224 963088001 293660643 632544730 358812667 657761789 695484872 936972258 100237534 677385951 281740083 260936519 726676826 305211003 743808553 777335823 72456870 682443758 913349147 438934689 669445661 955964907 380899349 888496856 332074999 226169764 514837179 189831019 429923825 168689666 401736137 939646287 416222124 657702098 369645729 43280496 638917121 896096126 622051999 762018494 726829536 933326585 268171403 507360459 152008679 747330725 885162229 809198893 70530457 490469945 279497957 369938286 298622478 28186773 718437590 809833589 393179010 123956327 136653847 864921548 737712990 680054259 222612999 928127522 882521509 772973152 869907794 160300084 696063861 321942167 884380715 238074080 494256261 495795485 905944585 134610312 487534332 834995412 931103634 585406412 532535302 916333446 841881840 704562540 146416464 71886762 128204028 498721625 845568620 468957461 620509822 775387892 219637045 429608011 691293017 921812113 659154776 343209691 994103222 507486204 999186370 177858982 331551645 759464584 847867752 260775446 312632224 495973689 78827911 588459875 15612541 558994062 835796736 917552305 287823198 154312513 916605408 895188351 969841688 91427227 221963778 396011046 943026135 746177102 383336126 305718295 114600913 611647567 849509039 589327030 692185451 157819052 124864401 553514918 837848332 417406109 992110892 817038502 270309681 989703113 730550088 972766869 975786724 763508241 472078716 473389140 367558144 54701022 157202502 322345605 819614176 190209602 119659165 467168689 349670473 299424697 338989679 974786162 133113990 556144598 558533879 761571486 478799101 867987002 112961056 776877808 609591080 907008859 45908254 439830785 779898633 798172760 195041929 254530797 161337459 19263968 918424533 893502172 237668903 638683779 742786343 339774045 565219129 418390872 462822444 871194243 273373446 773604839 53741341 363615608 959401912 802075155 614136790 274179952 245339822 969038865 769056421 766155677 670305657 666461704 696568711 104413477 416166284 847814219 209037548 895185721 850834733 498779857 868266857 235495848 827320139 35722581 135721064 19338222 548878142 178485540 664887352 864349060 600067043 956540138 450741740 362177440 779159727 151689925 797017150 119653998 259064597 718098254 212205914 861570779 813192927 182120762 261691353 190718835 653941877 609940236 639192888 327741281 368685510 932385056 805049989 15298544 680548492 103112917 635208961 363925186 256034481 29473018 766116779 810589898 934344103 184338421 700029985 59167555 961802139 547329045 533676808 441749905 553878647 901174889 336581257 96163238 762031962 867930990 820179622 244015052 567929817 67805846 195876633 113804070 845725445 900569478 380364826 408922431 595597811 267637246 640681084 678205854 82037331 453587713 477580686 780962740 517922841 5553827 985991716 987064553 124019531 772072933 688804853 660176241 470146767 475236048 613581831 129760644 186431351 354275528 966502902 677763477 82463155 231712564 393018637 328995798 233391350 478830927 517507703 37745364 224623939 137133666 42321434 458161922 292752925 746223963 368406640 942042201 44482541 124448384 283614155 371627800 672364403 456936438 77378789 861103493 687968673 226276569 978839066 17181256 790620940 386971893 820142089 90066121 468375361 417955111 669363874 952771632 889549564 625199465 925628049 881947531 635347651 561929590 682131396 542807100 52008571 763626054 656079564 698560164 58049660 373211430 5659431 537321983 300622782 581641920 859858062 189230314 85386576 561661245 299029977 361786209 32520723 42233742 518432244 738024162 306319975 993343563 719142775 793867491 185907024 25258253 729438925 677497822 945044098 691996061 127198816 433552034 671250814 716800213 518838915 307775143 424915088 223945044 806307751 709421204 540337399 184527306 642442910 373746747 940543688 246999366 838624183 553290728 69888913 901973543 498034428 68990547 445191736 52695214 914511510 730701998 740896659 37564883 959331532 1739615 282875063 304081422 506258336 859689228 422721511 350434132 759530270 487294100 718501354 721999374 170883922 760757137 455725787 449067632 302917875 321422288 225343478 17970393 330788590 474027443 289671817 320984041 68271608 791212734 12318674 982574491 588535066 988946735 73646974 549980300 386708972 476954380 898089455 707677256 19131861 85749182 628475990 201544554 147376120 690229659 989154094 631977849 668539045 862129620 91306516 62612646 43054006 308625177 943421778 474458646 786998079 637124078 141919194 522950075 469327963 254337720 774719634 292637680 889421421 157000409 51087562 648940486 219754512 76038329 231756773 662407243 374413494 646501671 645808409 793678324 270378301 783366865 760601289 725648973 709122921 611941155 185077197 79128885 618697446 247379141 860711192 59424061 105053408 217361202 330849887 731636228 694728238 676821367 293871750 887457335 148399593 392723064 575600360 138798410 812340740 489566678 172555219 830137246 526089567 315889260 444896147 537395111 323996705 58708157 768277319 878940740 44303895 811312298 883604594 27085486 37246636 70398820 749910995 183591066 226306499 92422957 939085890 599585565 172265956 321521290 391047468 398828801 287726107 586128708 565987164 27245614 968767030 240270341 31302580 258878088 325900976 575767313 884923883 778753917 271536194 88836315 70902723 157900649 116159569 87558386 584836318 265079660 888095151 305860870 635704913 370626490 992127973 179236310 493834948 673047700 604495504 738936730 794071038 845575419 815653352 461687933 370929479 329095918 733080729 492724436 354823705 718928095 692994551 571498216 86699921 935082984 628315273 712747283 248503472 110134463 468761139 591435122 647748022 383798125 763039417 979626627 948471589 464738103 812897417 95124827 221985418 864973269 509203273 46616615 681251199 725099441 235844076 694783814 769806253 677835361 1986322 114355850 170498167 578945803 544113488 102932228 422070376 572624699 887874175 201763993 67671129 467338337 752376904 119999789 589734672 784897749 55256531 112585611 894138363 370769756 489310985 870076511 362718750 211926004 764883477 327484249 505368066 992936244 144847729 999597843 160378706 731691191 839726132 486735555 346180671 948135468 135447321 115839004 560252267 546591039 369857362 605217486 44558088 312378400 515445480 209351104 913687716 478035632 664540865 479384035 521009991 369170606 183865735 340469762 280488225 717134254 605357733 920026645 536750858 54727103 151726884 752178752 450768467 239489750 585681765 37621840 839436864 978422281 946783722 661931377 35791774 506208757 154991241 341196289 494948160 271148529 684794702 732718640 612426079 102446257 251782726 299943979 396620588 782046964 960398733 360415830 416087218 466673356 786874222 790980995 580217881 507916262 505481008 843100567 963950369 985419713 76275608 90217383 341593064 455369712 879495851 868262894 839278384 838801279 348321306 716715490 223261802 310531218 323039919 666552474 984287039 285139714 227258378 172880806 176848950 38499364 860705619 164300719 580665446 207651705 793132268 204486390 755234785 660807221 200620131 477429705 215767036 24907987 624520966 322038211 165523672 964113935 859093355 618510606 182996513 603515006 531807638 362127844 870086165 86105272 14705982 290954099 936338965 309775136 643114141 308651507 544802361 388563637 318224239 412671216 501543588 409682094 785088941 180280536 728916195 852825850 417745905 84291247 442645656 947589994 279749774 546295459 995696446 575136927 609447825 715505978 822139097 473093193 451133980 476715163 130195106 899766451 444994491 872600750 885130761 45259422 902380782 714674625 206595275 544843964 910176366 597681012 717934461 819144177 921757545 834127553 954113962 221524401 225966569 801729290 143700374 557937995 324776914 675748333 371939258 819977167 38073775 412416001 137956402 388026732 523307525 78309332 640387501 65183775 42056207 871278803 630349841 758365458 177237578 981096296 875337872 642077266 613055160 542630511 469831927 393883396 323283592 209866146 522997425 323276969 125816545 601196492 592077134 124791271 833112346 241213876 678429952 858377657 838213078 241105370 968087198 980119713 229332158 749543692 200464711 489180295 751113774 351951372 950522178 100121857 547403959 433299354 178532372 685370605 894197608 68629414 9901539 420745554 482829139 219418897 551011163 430823691 894256814 870276735 969437092 549621213 870684542 204244930 918362307 270911982 36891042 972859033 771223815 105747088 311362747 494150336 410298810 612012002 64954702 921225720 526004750 169947321 896203789 290938625 166343293 585013437 864674128 265400603 521612715 514350425 865132830 455450046 227005678 320297951 819590089 212230874 8406433 381308603 703239194 784225609 440894908 264702231 172900748 447695066 351652616 641139674 653998163 262160436 523461851 479179362 845195040 758060005 966870333 110024485 499036685 783144855 398299079 754304899 389454625 549151489 94195994 411026675 828182217 361810025 700602098 752281215 425178797 614833071 287026032 316343098 975583943 898110552 122449642 281727020 22060848 705341474 422816215 601109504 959620335 270626110 563988653 300981638 672376756 899821941 468042273 805360745 689416881 51666780 188101219 882065577 640162789 389445847 272579808 743027854 982349436 507344208 242102180 649337910 913157061 480278258 738934352 823754350 262832288 572720340 366727862 184039818 768467164 924700638 45340313 615237037 784467619 347607725 671112552 217318865 654582783 988461127 577196403 5605718 46136795 515544621 682326590 177978679 370165635 537048487 657684034 740405008 433098480 590377893 831940419 683266051 697354860 162513867 471017777 296532542 563780894 669264036 6663026 799087188 919909733 51360090 524226413 337145855 831427384 166158263 746892239 653574520 982381584 541008046 634175207 812781659 34723744 577789966 630376917 299281311 217026366 542134792 369541684 963852553 133673792 186880507 871805590 664833449 789933993 13331303 827782446 14082165 140784767 687011857 142078689 683317525 884184207 140159964 595294678 608592261 44276183 134330536 495744015 852351793 342911148 215888789 364256154 449935790 356268556 889064736 395716639 833760507 732129459 706809930 886688343 539012845 711346019 455198344 596570201 291042286 791701985 787684717 194558831 279549248 561777021 821549694 535273231 294849826 989584314 398797436 887654777 347316580 708783334 67129 423999826 16772032 61003435 398476554 417854058 368345081 315589623 696953618 934052164 376288265 571037241 774183596 433641325 214508462 159210136 993855155 504960470 505698548 433809055 851137129 356967546 907583010 722580512 746301780 874915427 887360470 449981818 565174265 773301770 982202428 763874021 797793883 404924876 261041310 785370702 52854171 475343814 395033555 705937845 732216820 959797024 21738740 587768947 19516680 162255796 211154645 237603893 677484769 763293193 451805842 468815844 805220304 980093640 364248743 619366338 746994234 931857047 599179192 527846298 666474276 647824978 250642134 654919890 227471361 410270204 236153648 898713541 109091005 150626938 993708133 669501638 223698410 446918668 195235730 623404290 574930054 570752309 320768297 116664763 354936947 357132623 312551375 778434181 254938087 481312114 537360533 48957006 393678469 94035910 142564180 145320522 935444550 785906415 572728701 475289454 50638177 901848075 422456586 122256825 681256323 237507879 902126547 348546061 384600908 471536572 250461115 633427738 585340450 574517436 151578437 284735388 506556964 318259347 915380011 368986485 396740592 238922469 422336242 696335255 594541116 161705429 327350660 614354133 583416826 523976489 71933717 993356337 7102534 963860259 719012656 566528930 287637004 129736028 261583053 50190318 520630535 497630772 787897925 550637730 487343064 911921109 685967062 18593953 581173807 716104218 516989408 354203224 845665049 555176749 858009981 941277546 848061806 777122827 160207586 458876216 345582534 26074025 105816552 426487316 190615548 394263206 71759632 413934856 228575230 877130217 492188758 5497215 164227005 180963406 41455426 352847495 856367462 703567996 433076339 332212396 129745916 418815721 129863803 654804547 581739253 133972276 445830695 589965086 928824451 509098201 244043712 83346387 509873183 896289500 126363900 943315074 264708243 235969844 927524357 4355146 16570777 45011125 762798041 713502821 828869342 662016494 530294735 297458973 982712367 936712976 864856001 229695187 941098735 540883932 499552954 783319808 249592739 122678170 173812366 152636050 555449041 710717102 542434829 928061260 709999484 540759999 723462053 674527703 65265404 176128553 714174583 296017516 486385157 139891631 441734709 586714155 261108373 292091714 432663178 626267036 239218084 18827203 584899388 420768593 932035217 399192281 245082249 823305071 123625425 213661946 487595432 49527171 696354850 782790137 808899561 261940076 901531567 922963173 362582566 255521582 484130548 208964472 569239169 417698869 695921503 170156004 801129111 750141933 464087981 244727070 105202727 500174942 560065038 909835802 297584268 164299624 725621547 380853821 150482346 981591279 652494107 494436288 886873532 857835557 376023148 934100301 489896913 33617142 262217935 781868279 710178503 556512369 335480782 724748623 149700421 599785607 261036742 817310705 263884021 404011441 138317923 392339376 334897885 807728965 243077487 833847719 943753857 228888404 736184845 875360828 419618764 334789739 814711695 673255955 77568624 929224671 48295032 292514530 147508684 812774371 203330369 829270761 368797222 456425060 184022232 416322587 669633092 451146403 821235375 448988220 178514148 324725090 602870573 44265117 447822191 883831148 672927416 838297923 863773790 557204116 557092263 215641863 934033796 854692541 821165393 816201932 338186542 448197267 351328354 736096641 258718777 616955541 508703214 616888128 438774412 518013373 259780103 211983700 206847500 353213489 618209823 54895663 538257142 664308692 106268817 969704386 86897702 558536776 37245676 971916518 192279534 4366374 804627785 596011395 330842768 99639805 737432967 842981032 865710445 322045896 899036386 21593163 945895126 612613153 860920183 710328057 363185808 312394839 152539461 894103773 795984714 100227872 810290342 1868472 915435989 318309101 774299686 736613054 941058483 122464947 584296215 142675180 168906143 594434660 752988905 696755237 842394740 23845935 287649625 309614671 195808663 649093459 323157108 944638509 157636683 938803142 99544849 782546802 256606491 806848672 90085517 295965171 170942533 358648345 934462304 819694167 8707742 48526936 373206294 15014503 871219669 385733947 687058136 692891719 522525203 496246710 635292354 371385135 725627735 108391865 882035613 676323382 360220817 624878475 56012038 359563714 264685507 75646644 282635315 445984808 340544003 54010853 232699049 276248806 905520553 121838810 55204407 225056358 320751709 397629668 870059835 465630881 899550305 826599226 275204801 698412384 313469659 517988361 828146095 280350774 323869624 408698063 623096918 360450354 460087118 789270268 601477626 619516574 408087926 698176840 784768588 239808315 775539795 107515386 40065044 45384488 196971400 293625178 866433912 445890959 784490511 461159009 804480502 332308974 180817051 776368067 848195823 290065741 805436276 117694259 549439636 385289265 820001627 574575136 199496287 209041317 280255779 137043264 956658501 312302828 214118861 689764264 352142937 882996419 633120507 961642484 407086863 643629258 586558610 952595874 585005852 715689666 674528089 409431981 800715887 193153213 883242453 58819725 759185979 493656041 781240074 495891601 248339642 37383254 632165384 104519397 396629715 637805435 421647123 46536449 110510095 817933738 150013006 237908094 117967590 397998580 4610490 644441514 141979304 367949536 361492442 680456121 278067732 856363058 573359847 402520961 728068165 912474929 570403527 442031631 876768858 118656075 148969771 369701644 389989179 880520900 738439031 477985487 314978277 145110634 874643236 782542996 645448539 8904337 563681385 628717499 486593183 321374830 606583772 979899910 928359486 957940530 704469557 637399131 356717012 240760551 295178955 954842986 991502541 860466059 152503720 694843291 691868672 329070951 475853865 9084451 709876152 859932440 285254824 919112153 542177282 332806689 262140884 931267698 504301789 631431299 290713256 555420390 174035507 465925001 659826603 795733184 634190410 158947107 823906545 699916845 942090131 501892771 791748646 21929016 480441149 548021557 863454490 906309841 745625135 780750864 463927808 400630153 55178951 939795016 221158597 839841151 499673756 958308396 684273740 56375661 42873363 375632815 734110450 129350330 298393920 607593799 501794101 774517976 392799813 787696373 782998938 795986750 21053173 580290512 837055598 637850431 603256856 801598208 409598150 488979809 714654516 500179335 324010512 204236460 797240388 788206424 794390809 779661695 820483806 665472355 375583503 313905522 911782887 351341621 965325917 753070102 234207796 962168499 773291466 363092615 329561151 807600382 194998571 531857151 687142680 135756345 360959175 539119558 789173711 120555274 216302072 392005073 63129024 738551252 763585883 93985406 899824420 271211550 352969483 785485611 674697811 238182469 43592233 477662470 38848388 579251964 297249360 912810663 115478825 541381626 905608037 615699983 997221102 898948631 877738760 272243138 699847299 258110478 517352593 175655510 239281681 956224629 613861633 31201379 347880817 824802605 430410500 48659313 939772914 54432154 737920179 334232694 50302945 391271364 962932194 80908800 342467632 465105104 777566733 563564749 277761777 145865103 689617032 555424470 119230099 595187310 138800670 423267168 894557865 218464176 48472393 239802446 504970351 882275850 165805812 565205116 647278371 893012569 980566805 577844685 695269254 883741618 414540574 492164475 490936118 690984108 514595885 991249944 662928969 237359564 522584423 689661809 67792418 919649211 358841318 714009478 329741078 480667645 242690310 981922887 199946516 102082051 296478477 316246021 902346613 120928303 10632168 547386907 759350274 264013732 55425711 364717050 71109741 983166356 816051787 806658943 850894892 733625000 215262744 620601839 225621645 524219523 407688704 137569548 32532533 392882938 84146694 871778066 311898955 340420117 222179608 218558482 63577185 924431512 318547907 257270108 211243786 500709709 76121046 651388148 761536338 433371452 514998893 717733429 149845648 321838354 552732506 74408935 292727996 284694978 345239894 428671042 652650730 745445347 200014477 319388821 812144408 390895184 237358202 205141566 739773173 232883061 779627004 851832180 4085101 92537915 701282177 231824669 75771966 736259924 738186628 790009376 835824772 956704314 41320974 260012775 780471423 301912401 720585717 709758232 498371900 260476963 212888810 693019814 995666738 54193077 85641063 354449163 629584205 129724016 698475114 950001410 783314703 314459201 437262830 784396953 54766396 177137799 32112765 604847673 360298315 285859095 376020202 512856985 462117658 443817882 237393817 774162160 682617004 103741781 413989906 450241766 313394814 649125201 663550080 926024351 754621725 60373754 561499301 102509608 215515638 851704309 931658069 239153117 619587959 771094290 73561780 248912369 276334058 500172810 51718169 750128887 177426023 703818623 103915632 785639455 605803124 79271432 700081924 674285914 876978845 657265686 555490220 607720857 291711189 827355617 858514903 533006388 116423435 42805765 200280718 458325704 380509921 862656639 141523890 179902173 249882990 380388377 929475407 926964845 618995097 869686778 298091233 391575175 984924036 371081791 895504025 342498693 232447258 997214323 181941262 875159771 893857230 989022723 347381875 858455090 619701799 398344293 271838582 199956356 977967730 320313684 143913024 712718009 509444766 374204210 54235517 503002114 520649976 513072861 637185973 383238505 571124284 644186312 362883625 33321084 980947739 161662921 215510842 126391874 379509831 58229811 3830503 925883514 572173242 722504469 353841183 641680511 823594607 667242828 840905991 574629558 428702781 244064762 54758323 282316126 733694753 536538307 114337265 266571378 938999569 72261401 852276398 881006728 536630158 897434015 470142219 586853139 555628715 948630627 487072151 268692291 864059295 311996280 486798114 816123257 150468957 189613251 650547328 926061412 936171077 994453839 338908490 117204475 441878406 803578241 178722429 610952944 433992790 777873942 163441694 724229908 137915369 359227236 411716810 7977345 616982287 255739721 146885744 647258266 320915472 411914201 744141517 516918364 676020377 33535197 542756750 122485104 756078040 265629921 506602418 316780147 453086242 81384647 690866232 81995734 930007172 595691448 362377684 43062897 678689450 576264489 157991987 236554540 92067952 729519715 905506277 360986425 477643111 994852067 370141146 886442547 717767829 703681579 396180177 418240640 793834610 796269874 545983234 228081800 737730664 270445463 136261531 842463480 331908722 530687215 295866451 521426730 284554452 465838184 197513719 499279953 705232808 35838233 273914582 547683368 104213529 285308250 984102381 905364242 840590013 831184740 566094395 541682281 569474363 578322680 175484305 887605611 472119792 352969677 793814388 605566854 367919270 255351641 751031018 966988255 683667631 534478725 187250473 35659275 295764061 387675103 485620262 842758913 645005942 775286347 243067285 664055817 253664452 684374922 156851152 959449927 492396853 879908844 792084299 734177809 662310206 804826743 58335817 608003222 280015286 657200941 531575312 674229692 498882724 323520181 34825725 474870234 802695673 21149346 322399310 671578435 406382286 314406588 822806981 451926923 718521974 958539684 161154272 756766936 841474417 4349992 671560590 354595807 178005335 764013895 383830369 133048398 955182022 163995027 729636022 70990838 321891755 446567069 129152937 832061619 317653744 440525609 873001748 412628091 916839420 36853972 263196864 625367714 53967323 201000411 181726479 82317140 833174864 361587864 156259191 219807320 667428783 72638472 16751307 974114844 76939097 671063053 145439005 977564617 843758466 427992925 402242056 538548853 118311281 552960250 354376824 617542732 960183623 221952660 821704054 432528353 284319610 386110378 469999728 25757251 703361020 639027483 161348973 759606963 163806644 315975424 210501563 361188390 477610210 349404480 630170104 958170915 603973245 531686912 635773136 898158346 158656116 246301186 520999113 155992450 897416447 84734469 519581137 558283034 108220207 589472803 120110363 255132142 738541298 89862659 127935051 69230675 487746360 87344435 595402269 267855447 207387974 287533608 949112639 594227339 799166233 301116069 996820696 704991844 247203766 915670632 284704623 942815438 279361889 671153052 720742250 611559678 171904828 353036901 792150246 148979747 416504615 564825566 90395463 829798126 391508729 289028919 317583943 236630675 979627532 235012559 570769593 629427131 506414534 858498377 22904592 54250570 58492163 69293936 920431808 532943272 441979593 993957450 6671167 522069888 954384542 884022608 375121080 224871284 526980685 317896462 987201921 370147140 223901313 225276859 240606794 166637550 790309409 480615055 160962564 44158884 825673999 772857750 405888395 612573465 610045164 909904335 832214790 763158203 772344556 378477254 469364776 667033981 600972125 692605808 254721733 643325006 713437810 366874463 475648268 178020086 443760697 576973044 49895998 348115086 517089140 761240997 106908037 509355438 822937950 389139432 586005967 547471453 270364976 433579926 997276163 925440666 518821212 456952276 280754386 882714601 989406795 860774375 669860000 977871716 197063175 376203535 615140623 169831818 941504857 461917918 509392637 830474665 754112581 845948623 12444307 774533078 372908988 336653536 114513191 933976239 701378268 819731955 347714151 283185494 187138272 859836545 247584408 335170908 689674070 948439425 92101489 198149281 402528274 529828092 381086014 686582895 533287983 730509598 262830085 140403010 114011621 490189781 593666986 169658575 785824794 201726039 893371855 161759166 709393932 498846480 894977695 278810228 313934816 876588157 700229346 206264306 507956301 903098873 51893613 743223751 130511213 987242986 16656688 60730465 737579134 603206047 266680849 55343729 10259347 834386347 876983521 698058224 296444848 289060667 555396705 539093182 705475371 640741217 902943414 249714022 464645752 932695895 31967097 800808146 893660718 507593742 397821890 534001922 604946885 957045537 21873717 784242955 451748452 81401301 742965546 952947227 883121212 422897367 299381082 748371829 315998581 63565669 703457628 114985648 961595060 247828478 418727707 376473118 255980328 562461826 904871725 401896355 327206099 919627056 658265466 336405864 205817236 244842177 524864554 421771819 826958766 867675211 145022948 149570320 55538104 152646629 270376013 606023849 3532588 10323021 455824423 9822363 558310683 248537700 523763244 387183079 733687985 54337180 909367675 839612545 139431024 738545993 265804149 39717268 980460765 608634453 343483740 527809795 646460489 866719519 378915149 470521451 104691508 37903524 678209384 580313126 149616057 451573322 692909394 40519879 351580388 768469151 40762988 166350848 520416265 108494578 575284616 160942367 85457639 382147563 100359380 366850697 54031636 898921386 464476124 411692176 749606203 22640711 540430928 720035790 564568830 402556499 824941854 569049725 283925113 947496419 615054508 775153192 352666615 122039185 155122412 791756516 965531430 548412302 455528269 79499286 586795388 957592485 431456510 490279140 333748777 348712257 767302032 23760017 300616957 778969522 532446469 621920595 246709586 264444356 433382357 780904561 890340779 523778624 286819823 407917065 28303694 847659937 250483594 162757052 310712450 903018255 11003320 80891847 688781762 778716288 932184046 218785303 895795251 115857956 746437145 515285734 810765915 43788143 819031189 96462681 656796428 202977157 539098085 877369763 144764496 687784893 525906722 325332625 446262706 816682938 411388405 723890976 893307211 410150240 591926560 73878295 751365328 423428052 657169344 717660638 31453500 910392475 520098269 801385640 290549383 534352264 33494809 476246814 799182802 601898609 510611787 38479434 220451234 220138625 243935226 253533753 108363969 165070985 488453008 617866823 91303083 564470990 902953205 966204069 319625969 860902143 167913376 460458652 1940345 983344692 468902459 961962847 963981697 18274696 634270333 60101550 865396119 865071463 126504628 590900607 715496799 809947907 319092354 991574896 84616556 753002782 768758454 145311202 424695833 365563084 621355614 736556193 718810400 196611597 632517300 605455966 403467548 420233586 741127509 205949410 647014754 165894526 377165631 409977677 338124359 557228286 279829620 339620936 137528969 805887252 784496075 343228469 115024628 422572204 160334693 595289236 114573720 630415788 870589793 123963328 441904432 445645052 487935448 903391566 141080362 610350132 356291902 778745788 602548949 753832232 463863740 482306785 997780060 91604978 455889880 620364713 268754821 940970667 319477108 985779454 311793598 28347384 241760747 601184438 712866217 977985179 444175912 429291808 909983883 496695074 495788399 895844658 104370976 13389441 904466478 808789453 768508812 505326487 438898359 865737438 565071409 979933508 842641745 758886166 646526073 784597630 516597790 706035995 18630435 870238912 137374149 567144330 14943408 995827445 22055721 769408344 70891639 421584874 937652840 447287823 713962218 416100139 904030967 448660739 565717916 376860667 35339095 86670616 346379643 903837918 680865506 876170470 820647241 989090955 977123017 848753945 971121296 538347759 540797395 860007753 786679750 919999021 989498436 941074963 214129009 675171237 187745892 896764993 193702237 100415883 960203037 555099458 985021675 820686116 791997706 87528760 116421125 581828756 245883969 333172187 672491239 704774888 726651312 967939926 535167290 484164138 508467848 265864456 870473870 568397193 445656135 773797867 266821864 914926945 268546313 295053672 212540657 390044073 323559144 179607878 349442714 541745541 615843949 328635768 104709496 168791623 600039968 458646293 838123739 233286087 173003344 568214659 250346855 213652247 171145142 895377049 458607743 538865448 837171932 897621025 750890081 495154606 104136910 64131334 178377058 511212532 411685778 662302867 270294678 297425321 91752650 482063198 498929519 773295145 490455121 566715145 876255279 520217492 878077493 565367345 480760347 358289648 843260144 312366042 294384750 719054969 23779205 194524314 333725307 611245448 836168987 46652532 663084038 857729810 425754857 266987808 340764188 577279021 279766028 419339768 813796374 382470835 24336126 608410289 982344981 276405646 199554365 209144593 834560722 991305610 503082356 482989445 640878654 664309118 824385891 735778027 115967450 580203460 221721 835954148 878746012 47718796 49624382 156679353 352317750 42998194 262031442 313491690 967770008 295649092 226403094 168561480 414592392 122260724 532773106 918000734 40939420 230543076 910235300 614184650 953834203 293154761 580030107 856373290 891280558 807939985 541288809 256719092 560488553 342106499 215350111 253541522 840736154 40458416 508348305 410689056 731694461 852544686 157146078 407897092 355607047 422350562 360646168 281410258 607164374 764605796 559079802 226190901 466781615 343122391 969056174 878014146 903528165 137146230 336972325 815038215 297267572 566749950 709397815 397898755 653429735 682458308 350248286 502854811 433355012 387070100 271978592 505068003 263259107 114696385 553387989 782672842 717404238 321747522 950548344 69154588 124630673 783682781 255056083 373236856 308794120 283559067 275968880 827302759 818476924 683741734 295673568 184106436 325353110 456611304 438125553 121478687 578965730 177444070 514182995 883592346 130124620 614907081 122251630 767459770 699653631 519994457 492255204 336107533 972393396 5320181 62146077 706503901 825673036 986534814 91601731 665173406 311978506 200788566 244417935 766911237 827084355 552534913 835630955 63352663 330664342 927784920 524636431 420456920 129397517 133300735 639908400 910357005 123839040 192539862 82198600 848671301 353450265 299368752 273714156 263453921 951060644 84157392 763065499 784673069 331394339 811249617 601006104 602158245 652644426 913872611 741414843 439428703 786348717 89319813 115358934 337994281 285385644 380009292 917461895 204968646 655236321 514210067 834655991 612890255 461017086 159600317 874434145 9470406 392208545 238650196 669873308 784288561 176595993 24792550 34226684 745294584 834790290 716492888 335767568 396998404 540406119 522878741 300214595 650147847 769445637 915396373 505408095 32218305 977867565 922216919 190891601 396324818 33704747 940080872 631161671 432475651 739355797 409703245 180086162 988386982 874995706 885689174 74001081 836137365 678723638 647121064 970450937 570311281 627036484 77823852 234157191 834079009 186822025 683922077 36665585 935375924 12475853 461907219 140881629 285960217 557880271 671903844 310987480 578111879 435213015 659351224 748028961 653118195 3063841 526962398 494460346 181767833 655785921 586540024 345479723 859700943 926088125 314972658 953026078 5732512 79268507 329029864 141289692 542184658 498401727 524058033 677487740 569920672 90441001 228894810 849037543 584582496 721382273 545006461 874309466 181224433 905040910 959400676 377164272 140856500 435739249 55248119 673480492 525517845 891448538 605876273 289999371 458844795 36081987 443449338 857784474 383844292 202941906 331777315 902321551 853148965 142903533 617183056 172568732 74652816 661734182 540765032 4119428 755767003 254452996 334954988 66940310 757932204 251584411 876864413 340877092 876052677 399744617 266471207 517660765 899697237 247383218 975134606 178078909 265488999 114616640 856402468 688926481 125573414 887364074 99262370 88091755 429103062 419831236 908546146 890583968 743306708 603274803 197869108 92651613 950873917 423735873 778422365 275499197 696948286 550367178 960721808 2566919 52436363 227414584 195743480 242822839 654452721 691090169 327573335 708414119 369778619 644434809 213240660 425243403 913981517 531585768 69931550 501552644 213697351 60425964 581144082 763712268 802140539 340301907 330660881 735127855 609879918 40979070 636435793 22522170 331093117 439100648 714159502 767889523 693973724 460837504 489607811 468838221 813074076 808317849 13889482 513742179 906639379 926845513 869678081 746125034 527533288 387526378 633661131 828429865 335977615 385471661 687397236 646925259 606511111 628451468 481247374 648567513 321689944 657187198 338811496 363950235 674370249 887982270 669734533 682018897 327737625 357841059 790562681 36659275 594307642 874826873 884779972 597520162 90764831 702251353 337183743 89190457 574510569 142008052 330707355 643762085 384830834 451400660 437468080 32474768 436465806 26460416 371696516 26327967 65859319 853999437 698467178 215133305 96332149 518161575 106246 513883737 765646136 576885005 631293475 461164696 768077000 279360075 721443686 649731719 581247913 767584968 512229522 620456072 386667478 928068467 321813330 468995831 93729290 477618613 958763324 641943356 867713828 64819199 313880329 497392647 483782735 230272732 796423649 331843279 161152502 425157250 291320091 672361720 236731124 554089496 27874872 267211079 151905664 153391014 89037461 267911385 399498341 178175540 544852856 110333818 996175893 911214599 976597048 281192523 840820105 134615242 331846546 863181570 831443487 803212674 447488360 536377735 303662623 824451145 791459109 515931960 973860292 879826880 321981582 961170539 187941452 521725844 225746472 45238951 861894802 570764202 490865785 221969701 975062258 946888988 359912751 469497950 72718910 608133876 333339998 521981656 101623586 17077182 836683179 464967172 193599406 420171096 811578723 379680545 913758194 967925209 258059400 993579326 898758175 622491915 364487199 738920105 850819352 739669000 627038047 636456334 935998921 978595064 186397426 307779344 999317967 490873340 407014165 716381257 507050502 548122869 434177711 162913440 836562739 109084600 990373281 832805014 276112017 896145563 364047895 947163532 320662900 320924568 281181514 715490715 374554364 148362307 412920033 758285794 323819965 559588477 670525973 943570365 604024815 754746274 917230505 637527301 428039130 66637069 240309949 913675699 719393459 721927629 550878606 651380256 72470061 232896491 433982858 844166002 767703876 771651964 434048739 33197781 132821284 502865456 776726048 510073243 196929142 559061221 526312586 573823000 718055097 703236093 309040896 723318937 516902512 650273638 481539391 246740671 232196183 405916573 54237591 134763914 920610969 997142578 271311677 903167268 783840615 607060597 100795586 257662309 160004884 425078760 658203074 440033438 907344572 356323937 23945012 785210563 137005594 405514628 223254032 601355567 236231485 504739711 421684269 637325957 897320194 584250463 358866948 242760102 600558096 860306380 837911861 832282442 785160689 172261676 243800237 129888787 592995458 627781379 565371928 202436304 455248176 855332969 911386987 744451572 200291282 940293989 479009188 905644231 740572919 832453885 738141753 95551111 233406355 58245089 19434151 716200054 204582755 596909701 628019076 198652291 173540496 43864195 127303676 910081940 805857638 705860193 206379785 759433604 558685994 352844384 613282140 646758937 478105306 236835552 234396131 804834076 935927556 380283917 634863713 963340357 183134581 933635108 241183825 15316495 696239996 225271278 484382259 949557878 221173193 595727456 585667715 912691380 460845166 515395891 158941150 123580582 913671745 916705246 413024315 641977681 427120171 824313554 906514015 632634904 958373983 670927484 325303389 324424592 854547716 13030352 366932749 693242 626439166 103245374 940840529 525091600 62262317 118889428 843957687 341528035 22527641 914268967 574708539 80040734 134857934 494146167 282590634 600449998 634131370 901708505 234225224 600975617 906755734 672062537 113239995 855698529 994099575 29887794 457314020 979212785 917881601 440944143 512322505 377706906 307771743 733801202 254309058 419690278 624256722 65688445 266757471 288642755 125433696 652508375 884144116 907508708 129239941 850423479 398337045 339785758 55729462 823537958 298657764 17249890 58417500 910316435 983334448 254575935 816763244 920787928 423912390 82643350 432756359 191699611 784974123 566330395 456266914 549219839 415294258 323354696 258042050 250625198 724716787 297036746 630757950 8319135 990933286 428551372 972716173 160401879 443347561 284112283 919062252 244833997 194005340 478567125 3299790 938628613 983791860 614617432 898173363 600995143 195117729 476060003 666108714 575582020 624661173 90217493 483009788 925373272 106895673 422262924 344694885 861383332 890437910 908777895 750772331 356648973 84839564 139547036 931095535 56924801 822034549 138505482 240498010 832469313 792685415 502943563 635864492 634662669 804970522 532016584 386549194 519279402 283241115 368719367 609762256 173331398 449828869 888167071 762407658 602858261 20923243 364262429 286061636 870108666 241045331 390032313 447393495 199749080 45939996 119166207 759649734 910028785 181869548 548145881 813942025 493441237 396422796 264352824 906850441 996750188 37618424 162948865 745778721 932064529 432556232 485809677 660145458 41280343 411594390 610749422 877750650 736722560 508139867 395695758 647895539 894556281 998336998 738305610 840073034 536279085 747062078 575092252 694768728 749360383 837924754 422105388 708677247 306328339 680539458 594136222 502117286 147661847 677188394 184634994 84322492 928517741 418562217 26331100 616180342 715102724 557803074 937940794 713768089 813065198 430025185 421571035 899651441 325020484 567664912 803266703 851755903 808064183 339562381 951871682 317712333 910648486 464832968 527396672 178595587 258941304 963582564 676577133 309886982 328529140 650182868 470138796 62586181 672157420 935395579 788482032 763901699 651415027 988250630 29780608 966060749 301180926 172786257 269113759 40920250 569273403 898421715 858648018 357043864 758396312 302525472 684729357 686128885 640334055 497156815 459781227 74491819 454548265 499141836 912210020 375978150 913477830 353849113 527379969 737235479 101606156 428298566 322741529 558451393 19977979 824609922 959973687 69934140 535259096 698719598 152088044 706991573 13801226 324244573 76867726 201206197 196324577 409480280 387364740 301536961 351690884 297515039 473000505 894324255 623809583 552816211 235432972 496821028 428628402 58146204 444927791 794611778 631728174 200525945 314112825 547150353 215993857 423391474 884012460 681890227 842347193 913760280 982901709 817321731 566786672 78915498 83396256 158264074 865286251 775833638 852374151 41931493 591569298 609839815 754574604 336355528 890500843 874807862 263571711 318428461 338412830 592482114 423788577 845149550 603111633 848964492 601124884 768295301 928438821 903554851 810267810 115231994 199110940 998968256 826218052 171094731 462243732 835430740 140457571 900530851 63083213 561157025 147629178 204690176 717127922 537267418 367482665 495254689 117031765 381768096 659392721 968780957 669398047 403108596 978014659 184689161 327276847 828245678 657478078 528397732 748260835 690798177 392267493 73882138 416194022 70785526 640571899 505059273 895985701 42979751 924923637 418756758 207857792 239099235 910268905 929438252 950964359 519993931 549921785 960316985 626809640 726794727 252180123 314851193 531108891 716250847 724566785 771657078 690108295 841907821 317019059 796063483 28787140 539733998 858553538 228397361 924386911 969902328 844589166 360838159 379695685 314991053 939501880 535708046 371412694 224715195 565212436 853526765 385458608 308698299 8671147 203207447 197144705 541698180 363100746 371393202 393541224 596789374 602745191 358501921 800343789 486324560 975221393 759178106 679073571 354478688 256133374 585580793 686584710 342407639 873935393 679029556 100205116 838603416 125609175 198107933 196361725 798518171 178404435 354911847 820424158 607198419 393389088 106172872 774587056 770866491 648807593 819604959 917039125 628709668 219700993 48613326 746846220 123950405 59289877 768302303 438795308 720995004 541758937 517118295 174825596 878770340 855678882 384738875 358322378 745225631 860508438 436209790 567950683 10068252 375729159 218028690 475654369 535464884 185188563 48614201 723064853 750831290 243932327 173107378 874014382 374596317 9300716 672491431 310692852 470070056 330272574 134327857 588643908 129774997 51252054 237935281 369101826 192873237 235005536 883395865 310327667 53625630 40022356 323008367 739241989 852148754 197168617 867695094 407112751 731372847 643500631 290630323 73612704 726483530 162203346 763206623 843458713 753015908 372715293 545424860 646116761 254761633 668462928 305526243 70253457 342254760 4465428 239150545 128244806 207974778 178812977 255322706 29106443 278281152 521380601 654873596 415275855 2682187 297868430 660059839 683584834 487121142 720984066 796321831 847735219 605179113 56758539 212564259 902722834 94092804 350561813 628713673 51504888 489204042 797458154 425174779 958593422 962720945 502442237 61324555 175889157 426783539 693184705 373674541 10128391 221935031 133589257 932938081 346361431 309540766 3885810 990937315 932671344 751743035 182684062 34696667 948906764 638050710 664184161 274928780 818299198 703328233 414480869 217829086 531409718 673844225 467546843 149735142 744403198 764125346 486168991 162576139 462680407 690010145 707792532 649748010 32755004 433729555 918633580 879777535 892694148 490790978 223011529 512749060 857472032 636139597 206934026 356137300 113826030 604671929 592601252 618652020 285499021 287517035 688736523 430741882 666343581 757222799 361524531 284804242 989407443 288106126 180558236 722307613 831873925 573395498 758750826 354629970 341529444 629166326 452956488 358485741 982315738 814674654 265313537 187708679 897244838 204488363 362930407 968973476 214410531 44924390 938011494 660666828 237191646 596145416 473249009 700946579 62881751 717966317 492983039 183326130 11697071 199326111 874210120 220599409 111595059 458664828 451569726 642419830 958472763 787672356 986919006 41089017 292480403 855767563 829493956 807071488 611092066 997135267 771466906 640595635 95453252 750244423 883238277 90556294 516286786 493725624 384495580 838409952 221944975 500278811 198339634 260587507 175142566 717559948 498062786 726548878 119896460 515568367 407065290 615310233 168921541 381190060 241479702 708933534 959471780 626522027 342832669 137940949 758696159 292482401 817525818 544589395 38657918 78629466 515427172 940725775 304715377 422510913 216613255 126471584 86082286 222872661 25418109 707131595 992203270 478179257 45921067 796046405 386709952 31638326 390793573 641554276 715718975 344883310 134275420 703788940 802176726 105385325 838180977 163125491 695930057 181007881 738741792 50141685 305357215 421855256 135706932 168015503 321013281 98257007 932863835 532625789 109969926 609089005 959835877 492993668 272503392 710760146 208992842 811630937 140360477 413725713 981242541 470220199 807865925 838463198 427345751 45415418 439146252 754789682 40938157 157399106 21769854 729751337 116777229 829990766 880688738 337130939 40645778 987033397 318534708 616265637 492646215 514944483 195029652 942834894 500119205 330017894 534662017 947084026 251414109 15105559 458743180 557900104 727655496 953499670 668446779 369000415 241671323 870576438 893590851 434707848 315578804 346391963 46801503 895095085 568202500 947458260 882467084 870225743 112739767 491904474 895162190 758265460 938159754 361130317 488470446 902618786 916502793 603030657 892522454 84892913 171068952 105503852 504178117 269087801 333053272 834152508 712261052 974717593 959757727 324371441 774142879 857847854 845325685 555820683 678712277 196625315 832611880 35574836 749574554 214085006 882357056 856390140 26725781 901818445 515102731 159814243 960294531 384430748 70626278 31618935 966860332 952661302 304964491 381428558 849011670 73969744 715309419 566887007 23112628 647226536 720255024 893320702 553411151 531183022 377473788 326502349 668138957 361119463 164145837 555466589 345671514 732505511 878597203 413024347 552553480 440718155 256306719 594459288 869945943 571502808 986728917 18327650 284278087 43044102 124061916 121154533 582709844 141236777 303976264 920656913 89993074 667817336 101590949 828418535 108319009 170083523 64630869 970224328 826987101 873757328 932868947 94289921 74805802 993174023 612577745 910449761 496510743 16976971 908081170 929644645 866198820 225300026 36418065 257519436 61315122 848375165 967358613 536723836 503936624 785303140 616125112 474272670 119606876 115415610 138925018 108951197 580357507 961374197 807399776 783292619 106735211 535003995 182391845 937081349 349910666 409799945 918518946 16087621 982087648 676779656 915091457 882727929 630732284 183048211 17099263 816373800 577605669 900316061 345629754 807727484 29645664 702183153 12411437 900141034 474678732 189118364 31009823 224302738 59291351 691347098 504201432 22746390 951261285 15312639 751174858 408471829 154448563 335619540 351343016 41554431 295791469 638634779 413683113 91452776 990836611 748255414 354403639 633052892 171537973 492053706 316654203 118315863 130459322 724002990 671267877 573133897 673448819 648058910 153572601 253137 687825489 375453531 480126728 156776077 316791584 106666353 956694124 978467148 447795821 471034333 835862065 810786138 112346743 866714122 468318277 59496375 658731519 655033760 290205233 653650277 118786475 21337690 54142260 586841143 898625672 442736952 428258843 277438766 425614148 572588535 491849033 422184722 170150001 621987486 605147534 546488258 258449776 404575401 147635301 128175223 588948163 503033663 117914075 265844433 524176503 330495930 598647860 395429277 409321559 701119066 718750472 151190351 439317236 758142750 958513751 29494169 668828662 39563304 340894362 231965124 334618646 616538157 602789147 582760506 655583353 656680663 760570988 491803295 219872979 15942710 400555713 583718144 328521896 574535585 536704548 935973468 773787906 493531468 664156242 405458870 392210716 197596733 378284669 748157027 622461923 482484882 50192441 781609488 222618307 206346231 399771617 328646212 825533739 697541865 604997587 757831407 638979513 10919231 609908903 538215847 39767613 455222052 164362121 184674529 697508112 198087567 581938858 43427725 346191932 244957368 719188365 521734364 585892727 179594388 766947981 514785426 374169069 944333501 57645678 505098555 980481525 605920513 739526469 778628445 968723291 417582452 957703094 582140878 215371582 702448735 137087711 241995225 307551105 908116106 159563574 44476816 461675751 551113435 622877368 338072990 47913798 402044650 985932405 437283564 13537591 832395212 453046809 958330024 467199647 32197820 98778195 662305375 698337127 493508614 708198239 777376858 658561791 121218628 650311229 287181519 29186350 170275661 870671543 916998481 760123045 348717137 551571207 491981971 235648446 171651660 403620139 538316428 213523292 72921796 483082534 282650016 240292395 886542756 191093886 495609304 519400225 254417515 40618577 788688907 284931258 507348845 426168810 71619606 346162899 387650998 653882035 431611825 157534101 710143994 767174538 996821124 375602307 412282252 909385698 698458163 432798954 511362359 597869641 506239475 834328124 954427996 10378228 244124067 265439404 938398253 807192221 464083546 345756010 352085909 17599828 614871036 412766843 1446274 81416328 183102293 583368806 952343363 71422001 2052478 108645020 729226665 822761995 613888262 455573982 394786131 192591808 160382007 892104779 239524745 464288479 917059953 781242215 97111900 276894010 163612255 910782259 717588365 391067538 385980607 82874555 403665 299282944 48045316 203280565 158501706 445287882 889509865 190343649 505985927 534530997 138465605 509163739 961121008 449493118 14302807 714730523 793595384 848421055 126486913 535966772 212522584 809089720 58903597 850320070 736098825 431328231 434702473 235894422 298571943 983757826 509485292 73317854 283609400 173162757 779793888 925083382 996595656 754273335 137173390 711022735 133948712 374643962 467327868 379473069 161732875 808038381 485440858 292849485 577459363 230106047 243054947 270094251 6465123 1957176 151835467 118071352 280214898 2843990 933483839 200295276 173229806 311216978 1508753 213800498 661086561 193427365 791282947 544999345 346718620 957774378 780010070 13882998 502223084 351075957 109492125 54746271 108441042 284861821 334529923 437166205 288565667 515853130 884546269 193641592 496658305 459324087 89899927 503105217 407091296 820207200 946937904 287069914 327319661 663895011 375566154 338084636 354834654 538608727 337344994 803921904 977615785 172930835 557240485 771957624 262293420 92256019 549536129 228602307 833861122 852994943 779757924 550459196 699305017 722828936 970550603 578146068 504865089 50078216 360201844 222406316 951671655 107048232 935784506 654623162 312981348 822402558 165718984 720020515 580816293 249872794 270028301 611927393 582269569 291060346 532972133 881463218 662496072 291931063 719777305 896945790 497322930 197986972 138191457 997201134 139534060 314777251 278901902 767719274 17255667 448781374 28416890 880854642 596127810 221454811 749873478 538016259 855911272 625165166 610310334 963035035 589919659 574183635 951656839 441911615 28341773 102534602 1861175 178596456 129334144 825014404 444690565 342004785 280057264 808080384 214969334 690710290 468453630 100288152 919338376 436576593 968588878 938083528 43796298 836852785 756755456 562799708 387265268 250570909 408848907 88611176 586276800 674586755 488231194 719941441 613920544 316446159 389926490 206412369 504159839 836799146 111865735 89880831 754426455 875662953 185201668 798944117 810875231 443672310 497843621 671835365 828739376 960002965 148301830 41059502 901045143 179892516 73942146 838260940 66656092 982348623 163406461 999185093 777142851 652410242 737863018 296194563 765841479 234444836 642937044 825606259 287617123 797368033 536473089 417307233 752005826 311110655 747043994 949340970 134317761 103254467 570792424 561889620 62475406 982273029 170590903 258536780 585914017 155247127 380337630 644235642 5045332 260357589 77119693 117568441 660539876 44395427 220628435 188633321 878063539 842317450 214832687 120488796 422674362 267082082 601906843 300724044 463943697 107062629 64426942 355712208 207851591 61348443 492383185 314872467 387854109 777036804 919969855 408329538 580181207 622997744 63606658 627755360 606260900 362875639 699611228 588234487 520419015 584762507 311477209 689200988 501483884 919050549 961020729 72414265 43449170 814237003 764713572 545529158 784183014 639519829 558345744 392307655 807134729 320387979 654069476 137364749 531417287 146574906 159463871 627186053 343459202 982045726 401111549 470604047 342552054 522974189 778699647 863558282 467437268 606289790 109473469 696681179 820678823 128250223 676561358 145683611 551809375 236076643 794607368 743225819 576770757 472598436 150777417 601472921 895604898 2143366 429123094 582692388 400193377 792484410 862981722 499181950 268450609 774718271 250624271 256823343 770712240 497156605 563795768 760330201 73145344 544780487 483857258 237835218 788476440 197821864 381820879 231923641 312519692 25644835 770143669 98650423 407696975 776417435 738617469 466789924 542803576 79078945 523737409 662619612 642930616 432877696 949715223 711633311 236351791 97976597 318525138 859883424 222353785 705321492 800663606 582503191 768360741 766845720 220436823 712728050 308015241 338360206 318444847 37833328 515549306 12578714 847542376 182620545 163551940 9847286 580919401 617065929 763922874 328460913 706260857 648927617 173535818 870588877 642370126 398522810 185169171 77807599 238311813 623392634 552181413 222702462 246462069 247401896 331693471 299256680 909986731 832768861 306914281 755325027 75350012 292480522 450996581 460412998 57470278 201705672 599384758 383701375 311328681 938448647 93944337 400997535 892181300 68263077 648616736 64558580 951928611 44241287 75345659 538532928 877403389 328421885 344701151 238192901 682587553 954755159 275232142 110893065 598416936 246551083 52524871 545458762 822661865 910039549 370407334 365341590 980096436 182347380 913651122 59773697 954419329 414792458 730931550 637765953 558512020 938200074 942063633 257663051 741071946 914563888 268817463 244743190 522364352 127226037 979628060 25900590 781164278 36620526 368447882 795230489 766996037 884679729 895974047 666423785 582241579 169064818 401893291 364791173 850198698 690038812 626502776 651257666 154650716 182602688 624838559 523611662 413226789 79690141 479530526 156135839 246014549 817633305 64593951 18225829 755863981 90920498 255799763 189637287 410892944 983903109 318500214 412364018 896645244 174096733 780674930 734077830 84973627 778875134 918543771 740884683 189550570 243586337 819439353 591560734 605082402 764263007 689504275 732439010 985925961 581497225 237403145 947338345 54578170 699138011 662583236 935267158 822968104 880791004 807651749 262412780 434724317 689975269 484838843 229688852 999427014 213836297 906147172 211196198 894442091 177030964 982298814 272643543 186072167 901154970 57450427 104664430 485927833 384583825 409172884 22791797 715767248 70925411 611447206 988665479 601243429 283753498 165452314 242763709 607060168 116227222 783984685 109741092 715707966 328647147 628854947 248902966 258068498 464669411 437985997 878538529 65123066 710672062 954022489 786346323 433885780 571364360 845503352 160307712 649910027 819883429 846582117 699339247 420970640 957559446 376229893 508250651 994384314 846772609 125906803 555264276 888450025 300205015 368813065 540755297 430724220 777448363 861680888 540203281 476795082 885399952 173905992 47510015 645474054 1843115 949456337 264175863 665901671 468063541 642249383 368530143 805017318 737641085 698845336 482357500 789554100 457926205 393186235 323249093 87515765 141223249 217594269 407206284 293377042 597977109 771639202 337969897 259621155 755071317 876646955 237254468 712625707 181771543 808734031 861719470 603466143 265186339 970957859 908291599 532191547 916724549 672223040 796171071 745317444 850738056 624488040 789599338 243293307 18273773 380850468 522227622 579271386 91066946 852454390 903666795 143518199 435101811 64094485 498903828 19810586 226664186 817886807 72465423 898157570 370312174 832165685 203431338 860248169 191031839 720641327 310749499 45769498 715842106 305174501 482381998 997518205 204884151 266087710 965940982 627911135 782465938 52414812 249823655 792810959 241840449 26317864 52850130 887128571 186334448 733429588 466460835 490332351 273262358 575407162 875895026 337216116 66752182 828975659 72769889 638770692 268102411 156825737 742388829 655339994 554127181 473599839 8843876 530311151 962668499 84564388 75730770 863300853 617504454 590326989 68310733 95383165 953626307 229630778 333876443 107250453 83697853 572819877 208841862 321595649 935130864 376431754 608611645 991344538 721040348 439436157 587438844 843577982 864194631 96134478 48854215 791835365 563516718 932631087 893058901 928622359 343657890 144234742 212045189 974564696 461858283 735184453 568787225 194939805 312866925 723277986 185177653 859792360 438112728 869123701 855000493 165885097 649159209 222472453 225488978 295668526 152354395 857378921 539736581 651049068 230912379 975671822 432582748 806013173 831221907 500996330 680286655 112326954 912840058 118240162 442112451 730486135 846675945 155626834 780559183 775157905 568136560 895824487 19837294 363785202 228578194 40520038 59495594 658370510 588331944 378435909 323850485 461802822 367408391 998107396 984489537 751760252 404361880 565053963 444465283 666999354 114927753 695783161 308344401 665004897 782440798 589316674 978595267 11474377 962477802 412040842 563711478 743276653 886757533 832621926 619648422 518885696 851604966 417266739 621498614 479256589 682376332 11478643 117742954 874429338 486253496 296968668 769523652 980815509 81129239 88564909 147699085 552122965 239961821 909066296 894912347 474641469 505439439 286648335 865852848 346679263 402331891 243588415 502760305 732157463 611991950 682479144 423832926 797112118 147972852 20174253 168875317 209842741 959609247 218563123 619492242 226114121 867536696 649819571 228876090 856630664 520298145 811024553 430987466 187516843 94233471 782501952 320172895 573190101 869421348 616044612 573761374 813677947 217385369 808045521 125123696 148973903 296538922 566144183 844662587 521342071 7743599 988638574 5464027 275719945 589347725 753844993 693531916 700078533 55042026 204902681 837228473 579578019 65561032 379425548 72856146 756325727 58549310 143819335 937849206 217849431 790959304 636337489 582623142 718455392 472646012 858537127 968650152 637588802 132373144 327134511 302457980 90159344 206708218 182472100 859877998 22146038 996416814 655194567 183691510 175885256 603544302 409939627 985340517 939911863 742463226 835513493 799772617 640882087 358120199 782505177 683273060 829331301 502043157 666326201 875949447 762013862 968746783 709084775 303349660 136587756 410876376 689815864 142553976 80358487 110987605 392695822 643923400 348717249 317369085 301096783 776545616 676362659 84988853 14456848 265995411 432390857 746766050 966029225 769279473 424926134 798547941 280712486 527544445 657987614 776173683 296486764 213561010 251171768 274625187 982612588 801314964 166043761 839775897 115160643 769719854 557598037 419937844 369472109 679576273 441126271 537247087 646545385 381033766 632954971 745192871 281266302 375304533 368268114 546968345 869405395 559296762 968075978 672672598 351372328 689121013 827262730 698128114 77213441 199418585 998167445 86988960 562049331 334670369 823962443 114494621 822811093 916628802 641403366 730064780 435160234 494152413 910158240 285365054 512542543 415182015 912680790 326315917 596279037 165434939 112072157 360098729 674067164 659293096 222175777 421917108 722618364 780917574 839080470 148550775 113080658 420035583 738278323 920480982 67476661 143928192 915635409 385676791 444534050 711234881 283916401 994854457 396828847 428319098 26726413 613014996 799746013 354950026 509550166 623558613 246823451 149491360 443940751 539302487 680465073 683732073 405251211 789301574 837330919 966106419 399778876 148807911 545832191 286023912 751599720 688903978 258158596 251824322 49738063 226013719 415275850 990604909 376248586 954265454 998520659 482401661 519557678 400629634 990395518 591590686 677516036 866238827 724625351 859074937 384106370 944607288 74313265 397576740 599655567 828438217 961317575 289349885 845343142 331667378 542744335 537000212 844830325 817227634 430594458 436794905 630575196 371490971 195250218 428590319 127491238 244483363 857694327 255477866 827135025 164328833 981058363 731953270 639964462 413980525 179114222 627317859 728036860 15150321 668799565 110888184 139539968 513303399 523377354 104402853 617337679 631551762 157191305 754105889 804301767 772794378 369585852 42798411 478299396 479883520 98302676 786337754 996217499 510451897 82305700 692351416 115298713 362958700 198923842 151909904 476328130 79689015 385723436 146022171 689375917 728932738 927536477 531189219 6939561 330456171 961179379 513673108 263383565 768010273 891495 685790598 237293136 741542909 511988269 812496068 54892297 595010767 834534170 379286625 905504263 791401474 718908579 754929492 585932099 272431000 118019894 505758150 341291887 220962333 318904202 342316403 748128714 296084620 473174911 278371971 812903165 792743847 597224131 29946610 977694333 136787318 116004982 65002955 379341112 473677510 224455141 647732799 451796366 492128087 191813702 844912361 389066290 141191861 410761168 69180689 861655429 271422750 947970977 789761219 644179333 433343866 97785191 254253953 463271038 113366937 468788323 88603125 122872241 151732500 962523925 779887462 820521416 518912525 245036586 180372957 77673021 725167237 970508726 502592030 998132271 213737890 857227568 573046328 794502801 652831776 475100134 81244723 246545651 291090788 902808834 634326615 788786160 532720402 14270541 900589944 839904410 942971656 36714970 589170612 202454663 518225787 18097124 848968667 770989901 663759454 310587683 260879956 83494442 610403251 606722291 56262297 139297342 641064145 960544330 993980713 56797923 397451561 34081152 723053273 69031154 515023161 737728159 825851425 59842262 912216855 320854056 446560869 469953013 699990832 960068078 397266931 508116171 571530557 630392008 834817109 626674456 867566401 503853676 852204249 7955718 863840072 749479525 77314982 547994028 131133906 783441220 633011291 442579617 668860981 527169836 363394700 912257430 971511268 514111496 712922404 698224638 468381757 187979630 355559448 14490751 434368960 976636552 219859255 688552691 842556205 923952692 636214121 577821065 423251847 97082482 754592402 387019082 719254653 456467171 177231189 777524137 458082089 920119371 141261972 24075938 378807005 233700439 957510957 606287935 485859622 257800920 495959423 896374612 153565366 646136526 121810700 788228879 434328837 215993596 824550908 470184162 610475202 771827577 728833293 511761799 461511626 186868691 721950737 209960017 848296505 254375619 229952786 907235116 374337768 23667266 871547015 316494464 445913844 712927970 64508925 210292288 243030537 80417168 622862179 643475489 621553010 860322163 888439727 39460059 553639909 628091012 948898730 501258567 581475123 43002728 811016331 12018264 599613240 773109890 636457393 493080506 516675867 811289967 459606181 449952770 426639950 344405582 73199649 89982505 141016034 771813843 947964679 153276242 124673264 437608591 622602963 969074236 659113920 475334362 304352357 624967588 470288527 504553068 290566190 199307069 901963802 151741341 362317895 542986268 207117591 846052685 197009891 432134395 284826340 39893215 243804448 243244384 510612486 579275204 830318520 923464043 817595508 857560019 661826122 336594645 664565836 766376271 225319229 728739902 910404393 588976730 460402164 266507223 536592922 419640395 145933184 122749625 887051395 682627729 414590186 758949061 925173922 547503041 883523276 264386589 876178377 638537837 637441505 629284066 45858058 758415563 888794064 393942646 391617732 935726849 223284687 172982827 155735628 111034082 626821707 836773396 8721681 5307531 642875849 311054525 625069513 579557894 635425790 333357762 588956557 39569467 490250781 265020665 664514097 780967168 592119193 644451460 616862979 547721385 724715957 296369507 740576159 205132351 843471050 574459748 879676530 282055029 492804362 267278845 56816451 359351321 47772760 628233055 580914520 538864324 939517983 951448945 458806471 788659421 414911075 953650134 445238869 77617670 19563870 863875641 511109340 197325466 632274430 10383353 429766593 459394987 276485748 824170844 687829044 233449773 913742375 67926034 201501517 395947172 167141093 717272084 301874999 431564200 390490889 539482392 234621100 75387869 123765852 209616179 453612448 726370463 960622385 694448215 572835810 808187491 414387312 947325078 91191239 76783282 760137044 907891875 497984028 463232721 867493666 139807544 949200722 625900806 776892213 157554437 344125456 767987749 688878490 270504052 214343440 745014108 123349883 967508001 717620458 388059334 903798147 116190235 308663184 418154350 827193177 876554600 881600989 598625317 230141868 429829384 333289211 979738463 624725967 308310383 664042178 1127123 725194546 159914559 310743424 23756819 544622273 10252784 266970584 634165795 592311840 138459962 125488066 438706184 742747387 220997193 851992015 729287727 21618787 985494130 700519524 295359095 443065154 85890849 344585313 513566285 273768072 724845274 342792477 73823170 274554171 727755635 423599346 58376580 936132140 701688472 108243332 558164648 844228452 781396029 23197465 867391202 171065702 763143318 497716659 882802016 409032966 503457077 651040665 720926946 373568003 695374487 553448003 102076018 175280526 570851 61042856 9881477 641634145 438230332 910211764 521014751 863966739 429579356 371725844 640992350 935221692 489026700 362240192 521810129 685410360 326474934 289414680 136372742 456560941 161559854 350821837 916784993 329673788 427954138 928006770 181589918 419230730 270167231 665054040 544901433 668538692 528935300 154211782 911074385 327138995 148124939 685634875 425184065 775188268 564169672 598578872 345066978 105265143 170717423 213513536 182077526 498189630 57659951 683653876 998399496 552730934 70504187 163333023 690915909 511607380 225404246 570854058 936947981 602962367 535310037 311512368 615516483 453381596 925445146 278166062 294926650 445333424 184657338 384785114 107137969 540744915 694509032 498768892 502741312 547439403 310637939 204871165 528673107 822321772 177180879 55918277 339169125 982643035 696226174 902741697 531145589 656215976 836998227 365376572 809228206 698153020 983233179 139417058 625933369 505020295 825550352 339189026 91904068 899366192 426698819 904978182 756074548 630648094 37859477 160996727 817140899 702716488 457283987 784090284 844176690 991383159 635137432 618663560 693054671 931249814 573379248 826046557 865982476 946388453 361746136 455711661 954775363 432676274 769025183 333677340 108105648 235784193 227997274 609266243 743661857 567564558 553010925 288514107 398185892 863738588 962207845 732604006 792765527 687437132 301683231 607723250 204432532 181411388 608364297 714617332 12443296 239179794 300472033 784394117 340499247 714949006 169832035 602590051 254920184 25003624 844405605 52617621 272129759 362585987 564063787 239139316 334461582 2515604 640889997 928823185 727932069 360814806 300490302 18018125 925766077 27819042 719439336 698791162 875203788 908699043 131885866 395112209 654019748 135205178 644259977 181316800 393904443 343073322 742349485 4747817 378417244 211935381 820882537 98438805 159129510 224042298 911296109 182962751 210960560 572345296 708188021 999520998 935026327 404718391 877876614 883449147 581120969 36175916 146774657 795986345 515279913 995674984 193649456 235526035 331045181 576349499 979364411 323783828 566974503 271190142 225339091 872278825 206299501 133855816 123616756 238823360 826819394 998950532 187556131 362006846 86974393 470086685 677704654 129025403 432733660 126177496 825339956 54514648 812695365 922143609 466766920 585653742 87093589 284874740 469262228 716505460 474530196 530854745 173717416 366720073 569572608 999151740 494079797 507825146 488273239 854683796 438473184 297851595 571613509 601242509 342682535 52496342 112938113 887578922 398110627 976712105 933373185 540356312 623738290 488452367 816491064 49282764 506890387 753177787 333308100 387936414 240858289 862853631 592173407 813870328 122315509 747273619 313467296 689075571 204296388 197438036 248847509 961234000 352907833 978990265 182164964 304102100 373426252 124407612 529522378 511036825 347071806 438797531 622988158 109113042 36335346 511892531 996674190 317941692 843148136 323785897 710547713 828679712 407382526 731331465 704831900 293420097 22874834 176160902 183922098 631932649 710335468 740365778 53005990 738688070 93083908 825195193 127147587 569870151 709239211 89621576 105516392 75235005 92973135 191446335 575545320 868641854 900062148 407735898 142562758 670099935 686115237 478644202 347179434 91423335 81895628 672621472 124357368 912048687 97873737 212447637 804891383 753707979 865106797 40489835 876025037 938609819 203019201 553575250 723526097 489263213 875671964 727518658 300456087 657579262 311783690 345619313 851582728 31207492 842997822 943880647 130636414 816377726 37475402 57564382 509595431 735366519 233031978 941829708 638349033 719874952 633856144 904330058 769285853 830703058 480335678 132088825 978704212 48085711 542813458 508636441 323780074 4585553 324037475 305622303 48006542 101316522 381322190 689936672 694274991 755381706 258540747 428309927 866141386 996703515 141349043 494373179 536511973 458191581 30811302 890381744 959358327 399530497 863935008 334788871 273591878 25203398 987743069 266967278 39208580 982806104 954137178 454985065 621381920 56877045 69098883 755145191 759347351 819739111 46635265 94074637 305289655 211578047 705594320 12446922 275280947 212464325 55007949 162496383 867163887 59180273 120159198 417236085 772313156 690652127 146064090 283740923 754299100 987028446 44362152 773933077 347791083 690798239 910271415 878838031 866654758 374013029 823897941 920633325 376123230 962493587 711784075 257084334 965497030 605405433 744915876 577361371 231923908 814979901 948920211 764969816 222411034 592973174 624394754 944203006 715175364 460973297 317106925 419030469 538549155 680990788 917462735 850162952 238237240 669976434 109741199 515446020 849879042 58008743 358059498 780050489 572066256 53288476 305037442 205233276 257654197 973297088 301099867 676446485 398615788 520495494 357649076 462258200 219499259 614276845 464468060 522638415 152164439 940537033 310547937 595468077 254725495 567845539 484403696 354053267 547672777 784724254 218788715 253321094 220136231 405921794 80091041 843503323 385637701 297908570 217928388 319597940 562751362 963257933 601778791 111254016 323764185 462779486 101825212 858401192 998175486 138557182 201616890 718155860 209295251 855702836 94653877 616782977 427735852 750512134 121276254 701523658 759857671 300791583 667473305 848139426 763648833 944924149 574558559 302789166 865211539 967848606 142592301 29156545 651677804 230711635 723509403 40638582 342765372 915562071 628934554 935173239 655267008 319086066 850493933 359980780 31688889 70950284 572943897 580975604 197652895 720922697 972443040 749671394 867623441 623622259 207460798 924708884 936123832 575106577 404844520 202065633 672953440 242420953 514272397 381374844 510081082 324926322 612675722 569532409 336668092 157200195 433207664 502744302 394381615 231199074 13483673 256455191 975552794 686075927 502382856 603045629 379716691 897556535 736050355 486936086 720249307 824512537 131049677 152066349 109924849 619041076 246031471 878505967 862012741 48959855 337719132 554253962 839897029 271831022 815689065 137498033 282744197 981906175 956305357 678190736 294764155 59558891 399228663 607870259 5194167 736919432 847898311 808557010 850680182 701284503 687901704 932453374 350810795 946135429 435841665 128265266 106288453 196494516 897991089 609521404 286813909 493960173 948048167 984547106 279779456 358368538 114849023 591140862 351173446 260651423 356251621 449588532 477103462 972113138 48538015 929442943 89652052 279895960 737038993 370759627 730280529 410660756 460164495 5004776 91156255 251142922 679330912 700242624 661394503 377256368 406920094 49435900 344427775 144551542 120216800 924654586 451260592 488938228 501830601 336103929 461990578 803588906 93615825 182237431 518516394 901878194 999413698 925031191 466145413 370530953 273234348 908369650 125153110 391174891 318396642 74265420 36039338 439603615 771063560 465966494 622813754 291461393 701030772 234801216 495896257 986674962 921743694 311715529 669160199 739028486 422812817 586743141 860403819 716279173 733028267 572509468 51151323 111665379 439288544 183074606 190060095 834755805 202974256 747128925 621167428 152068834 528676753 255511595 277190844 979742592 347477566 717476258 927316743 529819896 273557714 366242575 244197617 280591974 31508971 174842603 235452603 163535782 987749752 850062861 32391038 921415860 310793728 925619810 281462497 184357801 250975035 329878972 607456548 330291750 75048944 278108049 32160729 3502315 912858885 205582065 508883698 769064994 344984965 857180588 31269830 614167756 567681620 553988669 721690874 546766396 148367292 879771983 636950426 56061950 922329575 263513389 98203441 430277878 927742599 31221902 853462768 638478942 639595133 895699104 963359595 535322747 218119449 321155545 218472749 512874452 812981510 155173456 359944926 261889017 428533354 559611825 717943720 644909998 691608214 772623020 636551302 128855102 390148859 550747548 752526892 920135864 225197115 287429477 268460413 628078290 499300506 882409005 938077716 140506357 710846303 982895673 639835663 395537729 523067695 886861128 37830449 309440495 920014865 129226891 410306631 266429226 325830368 362602818 746884397 246646481 533799830 38036044 141828750 576844525 868536270 197841520 642758446 923363336 802702980 865588240 5361846 547426607 372219804 54080642 469969533 550861862 228977329 688496276 523601529 242639723 814667300 57856632 550498897 282781974 693843135 411418011 185248969 484768941 649993510 783113538 904035644 725438509 71254265 644665303 286108054 623198537 518775469 518148513 151455533 6764067 651349391 267216859 601306306 535076560 995881334 953103569 613666349 404926168 658465940 805142003 979227849 753715025 278482641 994837025 545621590 280514053 471793522 981495490 724067883 122333417 859859386 620260774 454468325 325488110 611692890 887600438 73129187 800591164 250145093 129781219 208793553 293528092 370590904 684129288 376964479 303670362 154137841 607753869 987249173 376079427 710541027 167701043 469127247 744542989 537686271 856310404 621602759 400749417 117553853 265741586 850050146 325685459 956037079 190376005 158227613 805017745 760640824 697155142 842506256 672250433 46617913 336723453 630258788 539464474 297367164 791419349 389591517 258426413 419359770 315834284 893388304 140080885 577647365 430919395 567625874 633082692 965291778 948957313 185058435 248941384 290437667 628687022 718995026 316552452 140264817 860760076 507394207 231062784 778984441 170634450 815932017 330248213 62607262 607873916 474298771 234058227 582459107 855309218 753055721 68059357 66826899 90112505 252967327 295691707 833009370 889881713 894771532 853270916 646970265 926082619 723318243 479691584 81843419 103839381 990677184 633517870 545662316 510015921 895040217 952450467 80932630 430176708 881461565 322382599 71312853 12975586 145668042 273816996 548253111 835701037 636283367 912305077 797686074 48304097 703121305 723051895 931273652 743085835 661702254 568546774 916237261 414656051 120143121 863791157 891563499 538940757 386884463 211917804 496560352 802777057 790722537 465353526 330297604 280528051 952477032 402111121 137468040 797933268 501519960 151648661 752249326 708806330 797075700 957384105 282218717 303001095 692291413 115024548 764927565 88897382 242494206 654814076 677561279 775353576 365624744 65362447 281652267 167833064 824885746 924621443 182749715 454902506 354797086 45202801 312826918 180532538 997915275 759434150 258261515 405322829 349900702 816848358 90036244 250518959 520447399 121643083 621875077 392690723 756636781 493263026 325666615 807672314 363099189 304007369 306291744 560405674 875192623 287316273 947175154 587396589 291086451 148017146 881406747 856467112 703384356 38426035 645421330 430898020 408659792 223631445 171642865 30652338 410286291 963419349 713984072 545008963 952207044 773701050 290457866 39907743 739872631 492378948 833099471 288772371 249866974 791710055 930061149 991787826 811157179 104972369 558793281 648624170 980695873 293055077 324515470 503209673 603494462 94521959 864025739 143124098 482150967 491513458 465997300 283964268 496758418 894686843 900901668 562475948 905241260 232939101 760574990 784370664 837711839 642229140 110251987 801875243 155773098 561283650 736908905 836978847 920122755 531769526 7221739 549574071 18282392 632880625 900738898 859059804 509591050 182068586 775723293 246849733 411114007 606135327 95041530 417823516 339763414 810144609 132357589 227034268 628824866 783016948 781489257 859692369 567062297 985016911 396345445 676482906 640616506 523898238 512855647 740211057 188909409 134502847 129772729 335927133 794310030 669767072 153091714 402229402 543692167 53969501 975837811 698913360 253210566 961427930 92397367 539845052 700780198 172356523 809565183 187731456 652233058 218430500 382951859 148399919 835360195 216488365 551873958 205914485 61032479 227513968 391197282 471135160 502629562 663936024 475084180 404839980 178441726 188464015 393897221 913490007 346382194 428995943 749748751 929814481 312293831 931554601 282199034 380222616 780623338 238912316 578196033 594779137 240258833 665411792 174712287 239054775 224372541 516884047 785956733 670905750 455779912 708900975 876423082 920129669 175920442 46374953 67900689 408880354 383981791 839035264 598100076 818061589 29801366 572344811 936751678 675996302 710321153 231367086 567984114 385986111 170456403 976664991 377495184 704955635 135010311 627929433 280634211 520380744 907101192 501113179 498450826 876008790 201941446 913415461 826889150 17171558 90417508 58401131 315662234 959648060 664582839 576214794 56454075 123171921 239627146 367262533 406447711 513365595 234845170 881438646 534711300 442661205 655590067 392121101 491449809 81187354 951968693 953372639 525121748 715843991 871489339 780884553 847605565 724514212 682777675 811507979 256242861 964329088 984487544 439264965 829066339 95738497 450720442 873097552 155825594 570420450 268434375 992671951 914469486 13074243 806489151 8323269 210340738 565460444 194163435 970350404 967847455 813038922 59395936 57076589 245166314 312153807 871374846 632979150 93594788 502266387 120046577 903580021 809217927 476756908 149722473 858259624 883468066 260213126 286798465 592928649 260283616 149620040 820819114 264104117 122799070 252255802 622944070 426200219 126249059 893188567 324889915 465821975 857121684 953547316 807964360 462282974 675207073 487913910 203984873 64924815 749658184 43803538 977498078 190180409 297327088 321262218 349396346 388853148 278738785 650417565 368006737 462475284 21532706 793806222 895192516 175920814 47666338 95658174 148724086 618878211 39636469 128510087 525999355 430171721 548152621 218619211 476877290 906041563 584787206 483729600 512390485 941081568 254588484 238447503 80849192 358283970 602362187 675712215 405355605 968707982 863925049 752906838 207890794 487473697 562107961 793776073 910657080 150648660 43829609 522895102 520591784 68667977 357743608 416101168 26655348 598850919 635456460 711173032 272661998 369884974 924443136 426162677 659021227 589588855 743325071 486010759 532439879 739837987 246522962 403999711 276811718 775366548 356986393 617100424 83769822 208185167 313619473 596571117 236638144 500879105 860488206 625202147 148928474 551655221 324292217 333540753 825599399 391170160 313585865 373576089 289876526 250792014 148361819 326038286 276489157 900201003 488186108 233758485 56779827 819413681 426378338 905496261 937448117 719544926 647734502 615100142 64424885 822446379 374497236 527356750 674908129 49372707 270780362 464023796 664874555 274742883 996015596 520264706 231258512 104172215 350056714 377991545 846374326 421033616 902715099 839084879 754097679 357164817 566303485 299363812 879932173 625123712 21223438 330281944 265228379 891065383 993840865 832824319 440188866 75333855 389936151 330493553 706730993 801258227 783143122 851895272 985769887 930032239 403457524 200329632 784984270 675863013 538479943 955681908 5354773 536502109 470584537 973398927 839819167 151632845 456403231 502992645 595223018 807800750 306080282 230122844 529605801 606233306 619810880 317700863 692053451 609529284 200243077 739257214 611184540 373496032 303282325 204927708 571591095 414267022 971377735 281063363 936749986 673206636 68444278 896293394 879745627 39896447 375405988 497692234 682242547 591256230 233770683 232477936 838791847 750222938 757023480 319536534 734569381 923046136 964589721 235578745 37382797 508973167 107924569 305658928 937448071 527146187 591052572 731828509 543019115 696080363 737700118 230802694 387655420 124863755 841529530 649101190 455683959 674707803 629209146 979456291 690658097 658280163 683583202 308122284 662254609 916183063 652325037 119602263 50438000 117150670 905416240 803850534 602425420 993164419 157280628 979168548 203922502 198638603 843562032 332873233 776903864 690927803 133694626 629610962 694688756 299808358 825664559 58591316 200969519 313398266 395792760 969783616 864897752 484207513 585667414 753504674 803985905 377110825 147062619 292880667 18466390 918401971 436152423 272873330 705527383 27001428 776480539 960155809 576758859 961388927 33793851 982647046 642648413 805818679 539965270 650152053 102372759 392193561 512529590 703620064 425785143 464167760 142776399 805243370 362289184 996946344 704330986 526049793 657446175 292696825 361450075 981187268 44376429 459457517 688007366 545131716 582788197 825062754 971134275 536404000 531121323 755027740 882351632 136991776 132329513 5298814 367689341 941308930 616284327 471142139 264708312 26486879 535445964 712062075 466791283 71418948 345105275 145817579 82736402 440736430 532478322 521344381 337877527 774191183 883719172 823536957 778640960 28858821 211155450 450810661 904766611 918183935 399029251 61298795 493158338 540747448 959307109 577668662 925197369 312694868 530545929 39923949 397982467 28554167 517876990 610631787 369278058 803565754 90041024 234273958 306815544 403445401 895578323 928760846 131136554 988205801 912391231 983777302 109613454 998367190 544846615 525572622 68639193 863107640 758734394 563478151 802968351 815127165 478298590 42864657 259968686 640946800 395949716 434590943 1777031 538635742 119612784 210654082 345709287 974039303 391634935 319067080 922162399 573055611 336941323 558714427 199213362 377679558 449784159 574921719 231631847 840392154 628741782 293404203 954877127 280801050 433423143 91019625 19490788 837061264 848836625 478854932 91117664 843046918 580831971 239330198 736622308 23845176 420600541 9533088 181284559 612322077 329776282 718280432 739052571 198179210 326326592 419214593 64954654 300963473 901708624 765602345 865706324 534136164 68673445 722961765 661330424 10617969 213341911 552744244 569916660 214523699 290710582 326401358 742551325 326946036 70468461 247193509 914916620 202290753 436065402 421200130 494283719 844650299 587034259 117041156 175983561 656289451 147663521 42888842 161909672 960138530 701638439 814353651 707249947 398083046 352292510 962944493 850938311 563431929 310149608 212615449 383110053 774436410 391273311 603716537 620931387 609691864 864937978 868267016 231177886 250264719 471281032 4442776 374463436 380683440 914748971 793076215 328920627 727163021 147411105 8241214 821638751 898075687 923424711 118926457 546627541 333192888 74114745 928617134 588506713 39813884 971362309 788810201 498090929 818379768 479699430 258493993 850444192 709966865 376436650 776957948 716471231 593915188 164186290 598233581 713721906 38755465 819523645 340465656 264025851 848276534 30354234 10027468 458639091 59736725 942678945 886958614 172797800 52897400 54167192 607482933 133962373 467271802 631231382 118929222 79644964 357229962 732701517 746136789 295940354 34789594 230917634 134177901 802029394 465345644 90592826 83069416 175385183 597904739 696004038 509469860 96203777 647569733 392757910 369799321 378780190 141806951 365450735 929186167 603786259 53012632 119059206 970657396 328672868 407771066 91951695 647205544 135343339 967399442 736037480 531925529 817446210 671478590 55781566 393830897 72344220 872475293 762887835 169289646 658228118 950752499 545983675 319005932 988206944 12804733 339721831 29674397 601426284 845892251 861624894 552527188 21683054 641674408 53120754 307232379 708339603 845177185 492780024 655636795 9767680 639461278 892639050 438012363 970368931 21092683 539386511 346694329 906497615 244293086 14739910 137537901 7884349 813795831 923092808 385888989 599942619 816645556 873934238 520649893 532600171 985538323 951608277 504139896 354541413 727197901 495054417 972993490 551960492 588010072 44959398 481369083 802325859 101572689 618449595 781830913 311998906 686965795 291972791 54730924 438356487 685891609 100570249 39073497 689419 420489218 331238642 626050685 696308290 728880545 743206189 48375900 383957711 535039196 643626345 635069225 298271108 995918881 262262541 811433709 60518370 534094535 50289303 762168726 94318303 996938698 981355598 988528435 514395003 35623066 353717081 190616147 431733701 31018832 383794969 484051143 856144387 35388299 597914715 917061486 664072143 33805725 17917343 435345745 995925320 801861376 69199058 227991584 906461392 747710169 364556586 599871003 20545724 187594442 388333111 760197766 438757709 817532654 50986830 508889569 862771867 537738172 908424480 618405311 207257905 366095636 707353590 164795911 491237883 427438631 314036902 345157858 97518051 461845751 266489980 319991010 522588663 866463105 100367118 126910285 866287544 819574529 177105212 652258797 196144078 881375549 973783831 603637564 398619883 999920177 606590903 770559616 45496645 11426462 919212156 629672365 833795164 29402598 536220138 263612688 532667139 765149517 228584105 940973610 884820446 234500327 158461405 106978696 625410437 381968770 523040113 64764224 470594842 31903373 280691637 215172589 515835236 277115963 937566127 417522484 626941557 780014968 264354207 202518597 531788254 350450824 909449402 868947203 183291413 352191037 381856421 889031738 642785881 575052249 374433204 272537724 787656 504522104 927472714 739824502 789160859 389584479 532609276 505405514 231223315 334494446 441413042 458140999 705238410 123455933 801799329 600369497 311264818 276326046 867312318 210126355 567782779 531130566 190568999 113333188 608158546 500348198 243341495 940621799 459250801 854481532 448467869 836684881 314187230 971341187 339805668 997078510 283280868 958922903 561711337 364981982 125280382 973962188 245924926 55831190 809212842 159993249 403431658 751240213 783251778 102184521 48923132 176444783 480942334 836805136 642999301 246445170 925368176 801165534 596528617 801452871 439989080 332370686 457163451 236538380 434190271 443516656 385777473 29428272 193663331 956214820 803832051 402161141 105932652 579289055 894123644 630931581 258268638 430418387 806603136 708408285 401205317 685069591 474008666 197729185 80990189 63518714 919055270 382831278 534982175 10027132 887429838 549038349 197897997 360902392 475936271 177086875 533774318 554957758 344592248 478193995 18385842 482061085 447782002 297071093 618383829 532886546 226282994 720833900 947451389 599737059 528507238 27705240 893502211 688773931 157735974 54041665 652017204 479485868 519729472 101566458 566465455 935242259 16527000 159055025 701577343 265185247 971694687 693853995 965584972 54284248 630446682 556622223 160516244 512838353 646562027 688483489 560226784 298707480 686497846 360253861 717088330 349145210 890345695 240381723 50507319 560532816 564267729 973079328 577556893 606889782 281313796 78476151 276948490 737588156 891838746 747210278 688280294 563657402 465791078 43223870 457413958 425275720 281854054 278067349 938373266 379974423 992149430 84070748 604367254 178805896 286812767 359202756 239750482 867038556 928715487 991347758 289581465 515309022 924630543 79921378 630124395 730915805 818650477 175096258 867897425 56689301 989479312 391676282 565185737 201477413 782934221 522564518 320627679 906738387 33907295 208144532 666028646 298897215 331709364 278329456 858336311 786884827 319008835 821975181 64274705 797678411 248959792 385189513 285025963 550053351 729911545 126229544 387380225 692159197 751361632 995986135 480265148 498230594 962038725 986185403 719567357 576993885 425348259 111683769 589381876 297550732 169626681 514405636 364953554 293310298 558343388 97858182 2464392 927555880 265247711 426386235 114175987 33899635 400867203 807645024 341933701 639196456 617787575 80250060 980802707 738584114 609040178 297621082 13944433 216210156 558686259 749318035 46017725 80195563 458567620 440582955 604627163 312551131 199494605 366730347 749712505 143238494 822120391 222001138 435668283 725785616 720976760 389051151 674023590 217501226 177599696 154321179 570356359 608059448 644426605 132348248 354029723 56227161 306984985 413168712 42651215 325952605 308505270 713135860 14205547 811310994 897112873 818986741 307900001 939746834 103397728 735509058 199213558 578334295 936116136 549543622 237906672 406597626 561854332 515354766 565645910 135537433 625742361 817951213 687942982 106965779 203348802 726009943 677403481 137051672 653769563 535806524 317229612 958836817 93688716 111369535 362907392 61711835 685478947 626945533 54881504 833308967 332902925 514323875 11513380 669524085 222209484 991743346 853625593 521454891 502471152 828222790 916265087 98739951 358907378 385386620 88307781 28303590 490206689 917982058 795031719 870613431 146550392 10933055 280098158 800069397 696809906 265459898 202323283 108268001 705048881 139226858 763630487 535808887 111088356 952915148 156531450 867902779 187162416 775173496 637533115 606448055 762210018 327978900 351201588 187062208 889948717 313907817 155593858 242153535 640008547 415843632 561094685 529022060 119052110 646116987 65755710 459988203 2306141 240531210 674591521 287934377 934841770 759578003 273295186 516923921 720743122 256983131 585154798 368180593 970871470 533288367 807170017 787726993 94058212 140644749 327196459 461351679 154646790 284636610 311778288 872789894 619961635 556450621 103685315 789532891 801889635 198432573 169623479 1785900 394955533 169522542 384422846 279586178 62419418 301765939 677460542 458549804 769309844 905491265 528205643 425849932 37009316 432788825 572519647 26416467 673527601 515791740 828555408 710766541 29442364 200255545 163308914 386144420 212546632 311674508 8136108 20945044 612278415 618604941 331826647 639782010 93449782 224778816 469537837 456247609 159639391 212766889 56257230 681299789 548965801 52320256 13579405 151482734 148042163 676820516 811808619 680849900 706693566 865370180 74433639 923264207 1951273 456925196 659781539 415480028 804104092 511271326 173056823 186158339 622953042 588809976 246253339 453694451 331325334 869245709 233261430 718199429 634966655 56611582 469403051 904496663 55266538 208511163 631158971 104309582 911752403 361434207 218032607 313347334 98052483 509194289 283185910 776633849 489192683 254620088 439571906 815078856 715441990 99472100 780359120 762336872 942912411 162935655 165867968 930346924 689648021 645922031 805855447 217008321 445514553 274824735 92319590 393837356 110512632 473994622 678034384 301907371 80517985 610379337 115238511 320152397 259303938 657672634 901105679 279650956 107819774 560418 203010149 816592893 617657396 566127561 775252708 499866499 96924146 651811037 115450412 793568642 464277309 150268704 532148210 540727981 278446441 463703743 300777973 609805761 556452741 695842221 757958317 114406423 554824535 21010142 81879269 691640755 764634593 830233524 967966973 452203239 355850968 544499060 406626869 714608310 943193136 140253199 999698577 160527243 37251745 87608965 70276369 418423884 521975622 23411692 839153942 785859177 202174591 217966458 309838853 561233179 167868057 314305132 416688540 461497381 809039853 909893792 441572042 166462244 615173330 600131384 624413624 203242453 444160008 27355629 101225792 441779865 530123797 148192941 387286595 39707571 689703857 541740267 984158329 959166853 949799828 850851765 617660983 471619763 578542532 978906354 864641863 348254775 171028099 229935375 734227918 496608894 286116435 521555389 183224882 284581196 867944228 122969166 903699022 452748128 864819362 899423636 817423742 710888460 329987021 685500779 973929203 341984517 419580235 583998767 831208648 293265835 897709521 597130617 138082354 65122900 797195683 858880372 377047435 431045165 950794699 872728082 875300539 646145370 847556204 369883422 643372503 971696093 974523803 645506010 352215982 774572007 219446170 310808843 912593974 394053955 923281486 664835364 689707393 776355837 60825617 833267732 411343878 692463775 898807574 683152592 231964222 159012225 927772216 368399062 66006905 269477107 587918467 275955042 439071187 980572650 216353232 687094936 44009548 698119402 252688904 639972137 867521694 986844238 937037445 305732498 476899719 337881376 929356781 110991003 32289974 250027436 308269493 523442204 249824442 725669979 905192154 421170302 865246395 305812934 758214747 776287559 575774434 841860957 456556143 383694151 686787421 295445477 552123087 385529027 516953992 867456829 440551166 842317319 838561465 738239168 198163884 380808182 942573306 392610918 758535117 546873569 441222721 193199808 6443769 605323624 973441079 835015192 229647601 501455294 459635749 54151890 493510773 565974731 959104533 306357340 406224991 506339744 868938424 907881431 472537200 462413675 362026458 513783689 113555324 183357134 858761571 592593537 607342782 134040878 310167432 175903359 142624953 631566502 776946590 762405569 49308907 17997373 459448089 863313878 78388178 948343295 498355296 212232274 352850577 207835001 376430110 391938236 525477851 32178262 672279260 62945322 491559790 727029328 100215192 485779302 680894685 438432147 93956490 669430746 400495309 727060014 181911875 30844122 403163500 426658705 918463447 841971990 293671517 220736459 892440820 79071579 298026691 175864092 333558964 691132246 287105125 576837328 642258693 462091383 341833597 200637142 522943605 776849575 55135278 843471041 806358490 118487438 850056308 314659328 205675811 207725869 801239435 917955107 351808718 496365100 236536015 206132766 480292217 485275446 762990077 293506155 329044767 264565557 22422135 436826462 925739098 883655354 3572246 513122726 511299556 26030131 788970576 377865977 836213994 261923128 28819229 535570725 661783230 784425615 888542803 278072586 716224483 370669512 604416894 824591873 91088431 389754556 885287978 42557398 428941207 906252415 250954801 710961723 871387442 914744513 418322127 691094158 73024749 624883239 30787156 734662711 678191453 718182300 334947195 392691720 159865544 945495032 359112359 256464447 22486156 987067349 759962128 289415966 970336430 600892045 980970870 588711100 923029527 468322179 146899534 639651814 976308686 876188021 331298276 2916867 34500186 401226612 604664591 980374 124004706 948989635 871695040 508522348 400642254 387456247 652242444 550670886 986024203 582989548 64361397 747822695 879180633 84022741 555404569 59647735 857308247 241357493 570040184 224400670 728081129 432353143 768133756 956543157 492978524 418770623 496677678 352035206 137488226 459605138 443737602 114780271 927573891 732830063 821618713 309427038 828024042 920283204 985710325 273795802 647577550 351460903 634059639 344559586 555419549 186086530 926040126 208156680 957498485 404842702 722920622 826527773 802200382 834293272 555671191 745552382 311858325 481007538 148629624 978715876 528535937 571492146 981336031 982079825 704820927 924695825 325579175 164188504 303501703 878171999 836100006 136937828 257164712 387500671 856136523 78797307 885154611 624797515 339105682 602602354 261819337 450282441 7680664 360006835 611483101 745010624 13065322 602635399 900388111 551604584 534378549 355533773 391323788 477771167 937865525 517680380 741485127 165780012 987384617 602571932 168481412 891515047 768946559 400940526 762619597 117049243 401610790 254655410 325553816 854645238 673378916 255828135 463239317 113382081 882899132 981047527 477811833 190830029 735373025 973716512 591745695 738357061 120656264 647417705 747725989 823084180 411032986 17225818 605667681 417540801 287484594 327516777 302061667 111685007 700229843 675996919 779312753 692809164 105360961 222691397 591049400 773549397 444205993 985812069 313224742 573687989 668503044 449705505 257469414 671394069 412741720 995309402 704794261 869917744 493456132 547429341 817701013 979336166 206830985 889632524 50214556 254416898 549462810 456711493 419506173 37114709 866783588 948462648 392258931 842411287 604943826 962327663 614352849 530235622 147264959 482689797 375043191 995364519 147669496 236157802 93804467 758442159 927982846 140973573 236150793 361259075 461172373 241643032 231228487 499072036 926321929 109632060 759380327 997937711 390162342 42607500 450362125 722309590 908760359 213094403 587867446 653545067 360174438 783801424 302405628 546084298 874133940 354511494 23778386 465265528 827231119 938671756 868192405 206414671 718476095 53214732 541117312 535369190 133894741 376247165 670856150 544965749 828573483 77841406 163986348 147195252 647649298 814213996 492278343 509323700 873278596 81970948 652169017 947992219 227961994 8901957 165175508 652246093 956559494 265262459 463529695 235261688 963345492 815277018 189069548 906790216 191896504 85623880 525655869 240504988 873016407 502719656 81095752 73011341 83388711 423211403 667718316 195245418 611727794 25463903 208448032 22322435 964554131 734596927 168907289 443405395 234015511 153309331 567056697 118128448 484606374 286695540 41735214 62225879 237365395 563860414 593380911 36729171 75736735 751730970 237526999 972478077 916610575 847915332 78085052 14359241 700422784 806074310 946450009 723658416 820556110 270564803 262509315 772408352 740935252 505643096 677450355 405849728 313725940 182725126 414536828 95212339 993142566 494343390 769270908 281749571 923518615 382324850 44280096 893973413 554726798 897338401 869161983 405728453 571018154 322085743 109068626 549789100 619085195 99641475 854004811 64958711 594031553 287724224 83350645 526479355 16422515 515802382 995716800 991651178 614095800 487091003 478881580 829323075 486716495 760257236 70546033 835485510 448501508 424168269 713744795 787468933 694102889 573397631 140267347 39260574 984305009 451071422 274012320 682268350 825403378 334480381 548898082 153546196 675303795 650555224 237548528 69851262 55577109 273743436 124268340 829999952 119471406 245295351 427249470 299863751 438370405 116298088 486818484 743547065 775290046 80732188 240094706 688482693 350316205 44675710 417391220 677816429 872978797 996461731 897087055 582631405 424353568 894349474 859424589 532444135 797750474 859055191 180720032 387351569 643306256 10519944 607243953 993481818 249945158 308062342 5908851 64211397 272220866 2221707 144848765 636207469 85881582 500751051 918437812 808695210 292511921 615309135 533689909 894383923 737384060 478953940 739344654 633917612 566062343 831325544 988533120 505542426 180734360 538694953 920470633 758478456 815490020 867521528 390690420 250700648 374104207 729636745 401699685 330425594 49031544 212502591 892233773 200999295 900962987 97721772 149420170 591210374 278220205 221999871 543581567 462696643 986555534 405851880 576873988 438059085 905389162 621874353 879984888 778476037 847172907 77379874 727246530 918728720 243047818 882633707 455239580 962938146 850372191 535582647 207805623 464371086 886159837 486228715 896002278 51657814 239512142 386023994 379027647 494150469 970087890 474583030 74468778 25301466 923983490 140919950 312450660 334352192 679948248 657610556 660460561 687613464 135413523 11436524 715523151 255807500 714582987 61937639 127986487 103513847 240646832 949519804 140352452 268515021 488723369 219715881 812000476 140566837 260364628 296220608 862500833 504595045 23434612 744414652 394709866 176368437 993799627 283998113 234943128 933447181 24051889 334445401 295147898 189072984 878434238 785644207 220956042 977527100 986725387 866820565 989851041 574251104 469766672 939641462 445932656 806482223 33261745 102186174 646303390 262490547 157406590 35522773 260679585 521565229 540868682 601989467 383189861 575462714 151036577 152178528 983170615 947622993 166726006 173776165 297853149 413762244 166156585 919487150 705845949 677369007 535620493 555552153 693262076 855921154 664232253 464283670 229243220 797109191 191878937 343763224 102442367 792637092 806355405 100476085 567954829 722952212 165688131 439792785 530589672 846616343 8500092 765327858 298356174 828174980 19098836 400403475 117208610 414850071 283960327 485644474 518895426 285666135 899131290 644838951 854981301 580508107 10783750 785525077 60575691 738595060 434842952 185509587 290136957 377608473 223715750 496059032 794841542 394407902 862373963 643066398 956133862 421534152 515207492 147323097 13039359 616320995 310008958 297048018 836012731 218126722 658262575 782437965 735954374 921044694 582592309 986643286 866449683 242135432 298570318 641447032 895586848 669364571 368347932 296645474 454209543 221353077 429248114 857243515 964952923 41046310 241318835 270119168 856593515 116333804 327566083 514039370 26088978 762319022 76091944 739130632 122672982 657811238 208090945 905944706 188083571 928365766 92737945 779714609 803538818 661488171 672486986 261797239 626114603 668576597 128327467 245977892 351421385 496257587 796950809 566831729 555511636 139379993 134174149 806134860 460179618 409472398 610920458 878869936 380616896 793224639 432280609 357312342 784224004 206613304 917258955 838896696 138285889 747022362 558134416 915728316 189536691 424836361 158746001 777886185 936690531 863522268 153230113 75621602 496558792 965334291 912963621 804668291 346134609 844026620 4822511 834190112 48340136 646528285 311448816 544031016 133906658 134753183 344281368 768265780 951975502 913712399 124821471 199315799 384827933 551955811 367487706 651823763 395197726 588882349 19081430 733628622 66681478 660190568 142033834 215125335 311697338 521232743 112727472 663349591 325813041 316554721 371771208 627405145 600496222 505241858 945498882 494261353 530759677 53215427 346826769 794162696 454765572 460726201 928745066 371175116 679755893 293000400 948036072 390420056 81837026 284353919 746917730 279197819 524508842 278030248 568061622 653353335 400725925 476191832 132709621 994072070 378381530 760102569 751879528 284604796 997536014 389104881 952519699 730667345 261884168 546436043 37754685 180811657 904921785 163156070 30544217 500692902 15074309 57547019 459899888 228271395 324275352 979381821 637829710 348114264 669100770 758064912 348800751 31603450 75564210 677487266 66661542 556244657 648167098 678634266 508618729 937382979 500763965 30556319 690950528 546120501 3160398 966209038 545048278 722052647 787011948 581502593 220254672 834506374 500176534 720284151 426396536 784807642 75452941 185562571 43824426 42043228 372320839 62148070 683639262 883032024 318176493 250313355 107480504 414530284 342702988 905679395 505923944 188186220 122075862 43230720 484771867 88318441 561327304 572215409 111897280 581527679 343038381 742172536 185754492 86636430 743218484 66406115 998562787 108811018 200082767 675458510 581246327 356757884 644620278 638132205 863446022 632620261 791293025 209078827 383946877 169190189 27711225 420254468 918566690 818044522 166901932 39261859 557991834 242965346 355831455 548436820 667590844 812137501 509882456 349747089 981924026 461663744 53007289 749176933 151970139 748801426 959306287 812803117 66876347 910914741 250037947 620043437 843228728 162197243 460335804 634887933 312253473 292991816 474088763 882441408 77590891 630996557 9225407 411366914 336202327 565263919 299570531 596087246 405579938 721797651 675003026 968259698 731080688 306248889 166003526 163578785 458644205 918986375 652637778 816058897 555831826 276150287 966060224 567170727 368468917 235126383 810619356 181385479 729359986 122147583 28849540 484150120 75278037 440211162 528139878 429560395 141362259 62628528 676966406 219780821 460606547 717856707 921083408 410062621 360172188 303448213 580183994 615044708 669087228 359811145 741812453 226166820 740633356 573347565 33735698 876487115 540248991 456688086 621288147 741444048 866898774 387884837 434239789 922716033 618337353 324120367 603509419 458685944 472675293 731732574 497104433 43138561 854436226 48602671 495064305 258737562 635228070 195506239 352266275 207105728 124779117 873478951 984196683 71483498 900888863 43337121 16815147 633545563 128195505 651113439 480884674 116002401 915834801 886793737 916493579 5302347 265272902 98731955 552950882 714964293 516899253 64364097 356104952 890487765 921730367 951326780 639675716 549932736 190240015 165743708 926175695 598530454 868603353 616314412 120266688 673172206 775217831 828723584 749753696 88620737 943050855 960500869 672331403 230530480 578681289 632272634 81766519 745620283 114402400 97602187 739939967 393628848 437845800 180510181 347728830 194114348 368435231 152390745 857886287 78228291 179787812 646100846 563853168 476977850 286199757 581104414 244125578 368328428 416678358 614787266 894320455 189133114 568169272 802793199 671780366 152258702 183115205 398502231 384821498 322851607 367688665 309909411 815450243 408526266 897640245 598236264 93915068 300182901 540067503 651892914 540366003 733922114 130905754 957965345 947561273 132721541 798566833 49381252 483794203 226123513 299842607 809055874 877346990 153477335 233343271 647977593 932240540 124759949 862949539 754001909 633034680 828913519 613574430 470054355 190179821 958550227 9262585 103960092 192315361 576364465 552712031 199911876 487286930 965931077 294020438 585004644 800595519 94950750 131478801 666397998 837372051 424049523 810445804 111936799 189846264 376087397 606500004 862819055 682577080 888667087 879298537 720654727 658498241 492027583 371829387 907974941 264486659 615178413 954231128 517073735 473352793 638288447 906944461 529975732 850487869 711268742 81159968 143346619 1533051 238017659 321641895 168378981 130864924 867083805 749308872 272702561 399854091 614840253 645605611 224043796 290943528 840677822 566396268 324334981 176378665 574415548 387512382 95626427 868355257 418203777 574962801 744550505 284367028 439161793 924922574 636699812 855912738 284450510 658270914 610013871 993746844 236501461 922221473 130873452 41535456 892039299 485091953 819880024 504513073 972407229 561239175 39355025 137673364 728804009 442247481 874405640 391375682 173402645 968196936 46521663 281382112 66536143 716149224 537614685 583103633 938492988 177734959 830153314 562019524 66808671 28978863 594046180 875604885 985026288 503825363 671568131 287216072 347951913 446030125 244808889 919653347 711493629 470176131 94353971 405391463 384346529 266858681 883971496 596354664 558770437 322874251 306098716 370812735 245521743 56063228 827040305 175230846 688122615 482191245 566227777 218145058 107303573 353164783 810772120 853640888 981633345 692985998 50024705 135926492 7378091 932014853 351935758 679008749 653345199 13284125 93502372 24765408 356240875 128935252 179457208 319886333 889083468 292659897 550861448 538665770 46026708 653883552 48308711 268570552 797798937 749595915 520874108 825402464 460794984 958831421 673628507 923971088 134298291 642315462 867270571 439077882 257123708 90239782 632160506 957413450 260327384 556770965 366787182 659906306 233322631 423293765 450271720 218140395 779113289 620715845 210967575 206465898 111411908 900193008 983030439 471131538 943792942 38488086 857726595 941649813 495585673 578607179 645344332 532015512 137109811 768329324 416953811 121421194 706687633 315901485 857132850 173684776 309177812 890505340 958849460 380352947 716640915 426456666 754570521 989510439 163390547 791468021 80945852 938506467 902419336 984894280 694049876 346598868 220125194 501483219 478607606 337656519 209309159 403595045 108245838 864650275 692323481 209447583 167247154 622699360 585499962 659515089 879245582 970528616 168343231 904681123 627622786 897288706 463075241 423625511 240634705 117036759 382135564 91533729 896099575 789097754 409789593 376965622 61184043 3992908 926841737 132253797 772991942 759717015 945107324 40902349 473357522 19598728 976371284 815478287 370599125 325778072 11714947 185186983 728752555 428389738 388431004 985710386 920911160 14152885 929901859 386675325 218463518 964590814 688870056 968678796 806373454 722560879 897787568 476081405 769469869 67464173 184363235 798561930 171829562 209340140 836688043 968837900 529790753 209235552 652114794 875170928 631486318 679253259 588898315 527587032 20768105 900283060 278181285 377715782 826042685 161261925 273288211 28087440 402566424 626402196 424170148 57117403 385416105 640966453 281559413 705554164 728217258 637087431 841589971 367350091 560353875 661534151 556278666 646576748 195861479 431127935 684842547 648444643 674970240 220906189 434496449 383513411 510919410 385308410 264535515 669194482 357025383 38246202 877916292 799945374 920231779 164131435 971912847 510987979 338462471 778809378 442599082 373557883 245917504 412002826 471800200 663391486 661748887 847703829 456143200 73058772 252799114 815316672 840280282 528825085 155941949 318244924 582825174 693721967 317889203 944914483 166186345 124291125 856065318 686679850 101601974 424591350 61965252 730958703 511917841 985645530 363780880 757262861 310391460 559933348 82151389 342312364 76179152 447184591 8865993 226528636 660354061 825173487 437501411 647178192 515446144 423147716 354367404 767208225 117882528 191538233 309341973 64895416 834800462 784952497 9822828 965809190 748338000 531575017 45400169 611359885 22409416 359474514 20081085 892409639 919622822 406486384 904855808 876577057 620389263 367543583 777857738 692679537 162473881 616623370 362059189 566852767 698669098 548740575 721318411 965160455 997551550 939890395 247033918 63681405 11982 949448136 214702598 152150438 867573243 944927801 568974328 711203261 880814181 420031340 935229987 429089905 847403952 33425210 10726100 45965829 85575737 50182142 375811943 747905404 333100696 710481625 58261404 69006137 349145550 377026123 317632662 648055247 588163070 436098802 324287790 594014017 350894239 318022804 758685535 150001885 921086895 622406118 614926716 376421024 914349059 984179830 36517420 107436634 130801714 853723615 124827630 395006608 364500858 32169028 429085090 121530040 430864592 900547589 464384592 106629401 672235575 507065988 19141787 61089667 917190536 369931688 883943003 949052602 667930037 655086705 858387967 428413275 86244809 166292067 105231688 157163324 125011705 624869596 804366266 558465788 214573502 796164654 11760037 853132064 275567727 608988329 657433397 65928536 385445043 663359562 699057995 342810925 936651699 304605466 362786892 405611021 302522085 717247578 399133567 392877895 448650019 774796316 883471669 533036020 417673727 179045633 367845883 201184538 219318154 678690541 69283194 908968559 459044211 13403924 57356275 269978319 37291456 280686395 613849134 465174917 892273799 143195525 624768423 879228231 979495878 178906924 523717753 100675116 955040148 416413195 254936141 916289660 722840872 960642694 620311469 397428842 452077060 910933880 971022605 901606680 260113325 235979035 570099262 413939911 132981194 938647676 611547997 223549355 939982038 250154654 7950802 922635827 760853850 227067144 139334910 742437109 851593080 53685037 332343964 184869629 621878689 610756878 479293716 657231757 18443314 571745213 288883703 720089157 1329504 519278291 716077961 286004679 731115819 583686128 953431794 359455760 638618815 213216882 877111651 913475018 367471419 814191880 957847453 722286161 265419821 661144634 383528353 335352987 955440728 531345694 869774936 536644478 247908752 100327890 368176013 324571809 750559271 743351127 40570499 516069683 893589880 130620366 204516401 949247908 493521481 837024737 192901660 93688186 771401225 745093352 424354873 954779159 404294699 140783707 502067269 776119338 284923446 149482317 461040901 272984369 602386631 79057263 109095392 543571441 955153127 305471815 503261828 640413067 541703892 816813479 168186978 442283404 527808005 372121166 115076005 70147189 724315563 157720649 614335387 41157285 887408081 144790606 632108093 396047657 680408419 87627976 838425440 530329811 497679377 53662263 568364961 106470333 82230618 346753034 535578294 836806666 455764096 607081355 51475675 96245350 692264639 288957851 533339875 500206837 355536077 825541299 536117866 206514966 580041841 484206758 843837813 323969516 1238053 533817680 886727765 712278842 927113154 675738385 5591063 985925831 530882766 551670007 783917093 213458351 854757596 538107066 471502106 291820154 948108326 507232366 266236995 64027969 170821628 776677439 670056208 200890919 517707675 16737584 5309171 859513814 642655044 818480554 857639146 78971992 264721077 45944074 682912841 891562599 940320302 544148316 250993844 778546426 858962920 294571152 608937700 311869110 584451791 277196306 411695835 698823553 708743561 979746515 489772539 859396931 873944396 217539519 140247450 469280146 314568531 972236595 724773550 768936584 271767180 44678715 739690831 309936074 174561369 678257262 981114499 945526811 418776494 91393072 221581125 307867174 443205520 952213845 429039272 776057472 734961752 402354059 196498812 24862726 993788938 223314668 521558022 983305228 257225693 182977915 631528101 201334928 804396214 776117754 523334218 622890082 85766872 229584084 132632380 783682880 75063996 584134001 307726028 361922371 870201544 62080656 742809275 842576445 985806248 368192586 486735488 488460710 729286504 79298914 820350270 571932228 534737321 965940951 95364304 661069064 87212639 908373787 916060707 948731660 865642619 920203883 580532940 979416896 44325254 574210863 262666566 235901881 239743396 58013041 769031596 56008597 129805285 424240576 837934714 501018668 223896317 750944242 428010732 601737179 157606646 299258469 270825727 113152094 210995503 524370539 170453188 322054166 55440132 8753434 683633653 146145327 189538679 909914564 127335272 11989500 883187189 358624359 760740889 194147919 185286545 515733459 872472925 240381806 570873257 702635985 290978820 563036428 397026313 161531901 239698374 29897474 305438325 160178311 658761422 494149375 228398571 89649407 581276526 822933159 492912671 377345417 450002377 782473753 757985039 964145308 619787797 67302868 385887330 522063557 100998030 261756066 942348703 21395743 250572475 202898152 128667122 572513216 205299044 460075062 401201167 466664870 134160456 382066727 333410006 254763936 789467021 370443151 992550887 136777074 783215686 120092622 519169804 791083244 379622699 849085905 407555489 977634060 657040626 258504304 281234754 944528180 762902984 176601758 544609480 985837658 608394867 109939486 294376728 843194493 928268010 519570098 300755182 518634788 586730025 84653534 723291559 611787819 38493674 182208768 864804283 544650240 642790744 145047342 257094242 901870234 140945914 725297002 510329954 307434303 982816484 312531859 124943661 159248266 923073130 906843625 938886572 232271030 577519648 781252674 454538814 959230442 761094323 18446296 286058418 584633260 713912175 218864421 388801620 568507324 363049375 908362998 499383481 871783758 321054376 410019043 414674716 253069831 221789916 367105147 704271407 29232906 207381731 366931786 805094301 726066830 628725620 398962705 14280888 657975438 845956090 867862945 375683272 693484766 745051288 607364381 407023097 362239398 728976150 365597796 759108026 495114087 569821902 802498237 984932721 855763016 425613516 86303075 947763909 136244210 691695282 116678868 402678834 745224583 609236025 252249632 99238297 133294361 800007365 5488810 488470660 968895571 38874157 704630573 991529148 128201861 152776339 783273025 983416167 590039132 683976974 411790912 566937080 488229758 643535287 463356453 652391855 244964734 886480126 577711975 132531720 999327641 70974540 996811586 801358129 172632373 988203335 149827779 60036879 167990263 357548205 688244858 212478320 29477727 412673588 534073632 406332662 409963076 668436871 80416611 191960050 237817986 347403143 57820723 276342355 832813718 890312330 504243257 524678813 563810010 282625296 301639670 888488459 309872097 674647489 923169961 772962261 642244105 466353402 353619536 298924139 502657972 68517969 636782595 25733267 841497562 894542028 880640005 605720794 183287339 272325458 298098081 120021772 83291233 823656183 242246994 524033613 626264102 473190157 561982593 425486663 628484854 435146044 259844892 260388947 999634801 775505527 510561249 435960395 518055239 536887972 905245375 363431742 51889543 498168546 158425178 356092649 51572255 425817453 450330076 298615413 859681879 143851538 537014271 280488836 681689828 363691653 36397004 969738774 281140695 854388431 100269787 630589156 41474858 954083708 776725456 98014642 428932769 117360386 524305303 403244617 401416116 632134333 65356669 323979843 609237531 780125195 838176472 265934636 744673956 605362106 37404348 468486271 963722457 929006799 310303657 948487137 775501952 257944967 506566977 208465868 146162368 678178935 556869207 844708367 460335537 97602251 381582092 645679934 48639967 468729607 581211106 71726905 959578538 978548458 656949467 171569341 867982334 593451120 689594904 357131525 288218202 814019456 815131696 479524179 449700898 216719546 117429042 925773006 423504456 118247327 526391958 289689446 188926602 326923936 236766199 113876287 879773474 670470128 373030576 108110983 46311020 266835314 8355707 975825545 869092014 720980130 742964496 988346958 714163624 682133450 127395973 342744390 422845333 74536756 747939595 515126123 629687086 899933332 455811869 423658150 24428516 545882240 682593594 419860944 385286530 656534312 287313186 76575881 735660380 837243260 40288251 719781876 447082644 873340996 550737374 190726482 149730733 435408436 166193563 759800123 663710826 691584141 258356406 711557596 271107853 186624245 765197550 392168070 974316791 182874324 95698477 171435749 898128447 566147345 795841264 498396557 999099596 189859634 671807071 820703239 633608435 233985363 259612276 95914793 476927315 784950878 975617625 307834598 551895458 454625862 100318978 50575104 139617159 656667967 446437155 227583769 442804729 294822062 351366475 124645251 101004941 507938638 135046592 466115747 704925954 687874719 202456010 594377398 818661498 659628698 198693670 555283999 911963551 701645205 14624659 852028446 50904697 354443838 915701953 13756942 489340834 230315415 95038647 550624062 656688611 110196491 325799061 461092458 383763663 429645877 236968132 741569594 593181269 482653042 932107797 809277697 731409657 536665881 349074985 990318579 913872635 761529131 45429525 68464001 293648169 921445992 965866897 777647202 190575614 161065003 899113049 933774731 702292476 754180578 910146274 951166430 736276188 723598269 579121405 503038 18629095 901836248 516455576 795236857 953144018 642697710 844492425 924976931 119297193 415031022 883448273 740782510 215730175 409015335 572529270 420140898 830093023 31240430 618189127 423951079 139129748 282261927 988748883 307024977 117239339 294083783 658724199 821742718 955768969 811643519 239072900 915819972 865882720 30359676 166081715 649894593 992760654 815725697 814818820 731820260 301927700 580575624 424199393 92516805 446869700 956517757 597297515 991058660 187667548 199997442 330897796 371805819 328440728 168819267 364538401 504193682 288939370 909999902 635248832 45529365 874869873 236256778 749245179 158773189 968881948 456476914 479048630 245916996 884202004 857161403 750926368 917025601 450717759 162264762 722766637 545529919 44370338 370026737 167788230 212114625 667061179 393835580 648850966 752482773 577637313 882955181 120882479 541323829 625152166 360331184 912552249 889855367 753595175 139885399 962667171 965419419 951815631 724460892 650237522 863281801 571138720 921184631 252271901 642827822 787515949 97645655 826951239 867755302 254363804 601380328 752756474 701892682 434484711 147359110 491185477 453133311 680614284 947339358 225037172 501415881 329795033 446105142 85032148 522436861 21160607 859851866 966777066 260911814 542226618 441975263 193907076 163950536 467101150 182183701 443356060 729104648 548560666 398501903 987346444 420779004 238849884 164674180 943115449 435943697 660611226 218942133 105952540 484912961 89927508 722929125 109780753 940547408 730408944 331153156 831047965 489211888 546785371 843602482 193195076 142701318 344642583 281824211 393171326 903249919 566713194 347147165 626042527 305204483 983076688 724695583 899364553 15247805 505298432 326849294 186171244 810009672 279092546 138166894 233462894 274634451 114545878 430757983 185746924 439696165 112468485 943471453 726219679 492821869 177671607 171097020 902558651 983099092 63220826 728650870 193957987 811284724 85747662 254382811 13516151 594739965 267014414 911488572 858602082 882868044 277429472 71405325 653981124 551454281 876594666 770640279 751843941 109702646 916047426 292644812 119870407 843118649 352468062 200201098 401476824 588613214 990934818 877170397 520528852 702060473 446994434 273627945 811110457 633091939 559673552 905674319 412280286 474892882 920387902 337561766 641719699 550026974 221817434 832125388 745759022 688206007 454498811 732081350 344693006 747711694 237145915 210501752 935789497 69115811 511663064 328933408 55010544 570077701 833723904 733740763 572848119 307244755 913806838 439123428 246370440 52059582 376767463 783070170 481220996 975510444 844170464 95849073 266948544 844699105 536664051 892342461 575501186 379111495 548630284 117995192 602091413 230281090 50369580 127238115 212538910 201618425 769867622 86009740 514400983 960731892 717742351 734389431 109580924 998991587 962212641 285218306 397502551 272593032 271255998 75084389 820384620 871131998 243255321 726741985 785709152 400307700 334784101 833631647 139724088 363164640 276247962 877039049 384438625 332816174 289907376 874477434 78419871 594249159 938078672 592529597 18190736 81913570 661603316 17333413 762453052 858372319 840080440 968936873 905512419 600235611 369015540 539518349 777703028 937437177 157544529 917044225 17917575 156847058 378326607 907812965 957096673 860723582 100285672 786601482 317687615 753356354 961446126 484608687 553201017 211239368 966868536 234525735 739152379 634811770 899012242 666304833 58869403 993045322 380420016 942010677 625561815 437834892 513574792 373305448 566463495 618272566 193203273 573568455 351051572 176643530 472562451 742735963 120352453 334961641 321762239 6869863 8891234 44285716 318371356 281170888 468458740 996730360 888209170 822750435 394655923 987864871 57753200 263083779 630110194 572274663 43628052 751019172 479150499 821421621 162678599 22470011 603435457 612614174 681824898 115234177 95198964 636662131 527551783 758346431 169967958 785732698 67406621 827034756 985164597 508396608 712713016 101600892 901003666 858473048 333806237 266622427 983317027 922944992 213305913 439329620 578339096 766684817 117579492 323529254 955664049 626647288 78207194 364993657 128338070 950662641 41036741 590769166 668645299 140949773 42198382 111636072 879743764 594216019 895197941 887605204 208601177 618354783 812395803 439600255 670153327 227818530 784294620 521079798 131440384 100909922 484407311 23999329 408140566 677932733 362076940 200096089 593174336 306286251 566120056 229034490 86087889 385054554 886985101 13339057 485903456 395639284 97585991 383512694 940793665 751951485 988516187 253581116 801837597 5963196 940299401 815710537 33564107 437746290 484106119 555521720 155831163 351167728 189486257 498296741 152098038 589172258 680057395 129200955 901780378 594535817 134777475 357901574 438051091 15456408 703892223 185361376 157413007 591971380 60809325 917513226 461229717 796341936 275796037 423652672 645295316 608554157 57861196 689876368 752982653 615151210 594752018 899582073 12954710 43849524 575808826 452122686 98707158 429508366 445996898 538106893 462640461 401790618 80854654 314584220 459926279 899140546 369114760 695733293 216737615 236645069 566986259 648800747 744937134 448954061 468777625 456538475 495521499 790221697 262575279 452403099 700786981 577574892 24541550 371229218 310231384 504338189 868229534 221265989 555897237 919360776 415902516 385665184 837163909 40936507 548064577 393335201 586474650 6499716 144258004 208329018 81837499 864386953 703505730 213220801 531697154 768902869 604662611 483986456 872022647 95909765 468690810 650453782 610345414 6429015 134724230 143228266 94107792 391396627 674032117 524241702 491170783 417660156 289065672 368355179 987245051 938800705 410130235 642897782 977896687 440491011 299893706 489048110 657576983 75924479 120265596 354462075 419448994 488199049 650549551 317116958 713457129 446961151 833838138 26312465 67825856 44107692 301769703 585564734 706531389 279849969 134361997 408570500 845506565 200616733 414997127 600777236 182356251 836141051 342251073 660313547 735901174 43849059 892443366 837682397 548880525 551295229 921883736 62901297 682709616 11807732 677206413 675172546 970412659 833720551 513918379 947176431 125711486 856561185 298203914 749645429 538091104 762284908 818849774 421089831 988628168 988338313 33780674 349122661 699668787 195307018 91852088 134819986 259639966 855776173 257465114 7823434 450051346 774843845 79659164 923646812 287892701 624230199 667894310 669521892 999134983 571281526 227896210 399388027 897884172 425956902 893532211 213741448 83988366 408014564 321781165 53551419 521983944 359995164 413324597 976915500 686910153 598121012 810715379 83545201 729817314 703478962 891376355 63852467 98250477 325909418 20110091 355370372 587452016 979046298 555364163 236599489 455326025 715682301 567544084 309004386 161452225 775984401 86177495 260196450 678713172 673492697 730476751 379388431 872180036 975693246 229745111 160096583 33434904 93037548 747464649 359693951 842065872 621092281 676221503 713432111 43218018 663266301 56138392 288157456 619258917 637890412 441760222 219158317 172896206 743635151 583950877 627822520 18422403 215271278 12903795 776868087 982457868 430171523 800254335 167741899 287672113 597831283 507889213 18467900 284561 441748295 626521132 618607750 306050708 98171255 827382795 253676813 275808006 405093342 543781675 450131117 325986589 553287485 645696013 2728627 109329323 534353095 954281495 617864655 789327736 394026989 774697206 185325689 590403330 367932103 98812159 447562840 848836206 867283141 109343305 968009368 877347892 33866860 134859817 152334800 723402163 91628713 279138787 841032277 849727059 737468740 287747199 988876356 712633579 653408960 508149137 422741567 38872966 633763284 660501410 317299512 132191093 424707602 44608593 591073918 380166247 852632277 703485406 87257401 929434727 552419081 267469365 932057826 108249691 175037805 437628452 365395720 579712738 826878467 839146033 403220524 200445482 9307226 47316096 79235745 437162917 718607478 285036296 195679252 624358593 774377862 625105233 382206602 413454149 650536368 656370005 669801666 637977892 725365075 798460121 986717600 441832298 550925991 417128680 186662929 307228785 957157941 777929867 611989181 940210201 790173673 890062727 894089912 233304491 904101304 59465449 612032618 211987508 980395755 631563760 270853159 985799628 61405317 439592899 928511744 909048006 837217130 825569792 66443318 791056542 437537508 716007243 189817093 584696885 70420830 591485578 559246776 976027567 397819768 200542883 83508060 427429787 324283558 270805731 821209627 579948887 856525606 156495884 348008495 270958052 710288576 572305228 265949785 282488126 497265243 816791908 414074504 807067254 80061047 974200033 145542587 52928672 63191437 455308582 594404447 180181265 181432464 179855184 307895474 787651738 816574559 712130396 124531737 807293025 515940256 421498042 921249719 34193922 531886821 890755993 381128766 675807091 70592107 52431659 181787832 717672642 926801088 269642004 540193014 108181251 105072434 947826817 925638135 594171479 937650344 795320815 284540894 695066738 109031332 509484466 635839891 401202295 111397411 581204461 522749903 487581248 691717579 93869304 686284786 99150186 75785384 591150477 26854428 109494785 684102088 82994209 714362644 387816494 657041189 453193985 680147221 688025726 880957564 578936964 112942954 517793361 79990585 226717198 626792719 282740314 2749830 567558420 460441720 259192941 625426008 652939753 732440550 762012685 17556998 110782976 77300799 4700914 901489370 518201505 33460424 620098261 821721907 785062881 536087868 3121240 132152180 352184092 70442718 684674010 751601691 790488499 487719384 631978556 180717369 194228844 333354118 3165789 811283392 28531002 102034186 847595238 182825444 277184162 174463627 989217744 757300442 935977185 582800762 792101466 256231997 745058956 570929515 82691033 682862026 434044034 254040241 923897822 798986778 346049598 247968507 607966041 346162729 983172170 617881544 903763089 741282976 870035040 34114339 838588954 964566088 590188173 343562227 182057447 467758373 999672609 417637304 127606181 862683674 587142246 577753925 807452290 689449433 200071677 594037416 707822099 925459508 735981707 756064990 604246858 887441427 478982522 416816794 310542372 448800107 321695404 746749277 591707662 69670673 2808066 4245343 581715875 904785268 624412302 933908432 401094035 423345357 841977677 676089955 61821666 923816472 996849647 798608825 709204608 58111928 93810619 610355227 376640329 747798457 123470936 608700728 653832737 301897070 6845917 834234665 541916280 713324168 913125513 265831516 605379601 434197591 997529558 690875236 559347517 76122565 946879503 126408264 638427545 228904604 175747721 884833142 237021172 426930247 286087725 837987589 239213095 567026139 568170044 632108939 839271129 645079300 904071641 566408849 141315618 607428427 582586950 193613510 842926052 908430344 90853420 755706613 358123769 78322014 201720701 108681676 59366318 827987951 33063454 849445786 809501396 870093076 375270443 28482848 584356259 43601388 22429747 394598662 206035194 119402751 763989239 620801747 750116716 389695800 758172713 89780861 133723844 931828062 331088724 160947616 630900822 281538635 5245082 565048256 136941477 210228 125177171 849066308 521435415 803523052 812064663 914239798 841070000 40799314 560402621 513625999 354740896 197302876 896875578 279720484 617194439 62605990 69168273 786680323 70494866 303288266 611760315 260029530 981182581 240047217 576713035 516233401 733613529 805104522 218062596 487778841 659671198 761681374 904819275 106600958 716216386 982892284 124088145 578349152 665609971 844880272 526285184 534163431 851449637 908067492 333662439 396665777 618389493 171916489 344397000 545609780 768153553 792984821 995237647 15103822 875663248 574591983 561690188 480074686 916859097 943380744 985299453 869991807 84750062 278634153 446656972 208240315 789357896 82014361 972546307 16340838 655737417 168548870 290056353 920178600 111028808 66800785 382130129 99861505 737676189 290751879 909213638 908503564 14013311 989233287 475282963 212961595 977417587 62185302 940871271 232543691 450028256 405578533 199990678 270468207 331641628 119235954 414477868 603529356 691500576 805739202 939264730 790319132 245177429 653917566 416862924 696844810 503598699 62110661 997949425 263579254 584080499 858498124 326426866 536571933 124562768 662188317 277020416 643461748 809349253 434470890 280731710 999905405 272643094 362136231 75170559 658046679 376946202 578241456 139830031 615238967 206839107 513834529 934261552 208122244 268198325 673819999 505804121 798834585 813608031 211083021 789555109 910779941 502351208 714367874 374237286 897753565 277637852 861115494 768652301 789406183 912325470 801969357 802999433 863576751 182000244 234944197 712210006 253540628 91170811 887000581 893736131 216087913 97907424 949032483 142670863 782484987 31752937 584230061 223499750 800660526 388527702 607583054 22280556 56725522 509942339 358891511 302530167 949186759 370545496 682266697 998950288 832934328 983847337 82471616 664435772 579503071 572821747 250799159 38306444 849430121 734866215 460475254 518674039 213680213 736371835 744421802 422874085 973032718 299737173 893529245 663193635 832752843 828754333 216848900 321063691 22229897 848565464 103142972 513841783 552715063 811979943 661938392 299130675 36604688 28235444 230925476 17951264 791595126 859745467 524995414 983015948 64083034 230720422 55069176 370685976 397184579 621480203 701368893 920820668 545268226 211269741 175757761 288129280 627611853 46409812 930772558 533073015 447611897 550015601 957548651 483504744 434352756 233781688 294539557 454059702 246200397 340566723 872201109 874612292 272777882 520235773 902256047 801247877 82738921 836728204 688556758 871618906 942717375 283219175 414963793 457753533 681705957 340090932 775968406 828914570 312120125 782887851 682632273 544158522 36691266 368091808 350879718 884469667 481030356 986824162 207809962 229441156 271525 411190504 256553057 887736325 648219027 946164826 102860030 693860031 628204791 590817340 934964313 282385036 286957773 379480614 698114167 235409138 781247409 99312387 9127511 659149473 605396147 699957814 74147793 749322241 719315460 504414777 508111285 120641973 626803494 504232609 296554907 974221570 501007922 965425137 82479215 203073650 523751529 835229829 137434066 940318283 733910554 681764827 779240188 910336967 935476097 746927947 297490273 165558575 857718744 786871350 634320981 563961831 985057741 164546797 904991080 153467006 696959687 806182317 821172305 118985553 226134273 265132403 431909043 370104632 513744541 260190056 854866471 412303367 36182331 105626668 244050835 702561356 8799240 969643493 236125988 236728614 756657299 692091696 823143507 677455060 220315869 80799941 104552332 859710160 183704512 559515135 33795614 37825664 856540478 414709771 15691430 478371990 646663059 652418929 650492258 173839736 857134859 348769776 576009832 520909865 290427723 443840541 688482325 539169487 563208470 24379460 805986932 653583802 718276927 856982028 891401470 12167742 413360333 330734045 810640270 565056400 657868349 899268261 633832805 994142846 846655886 391924473 987328038 613171851 941956038 977376193 160184587 818425883 504370629 727342632 710628858 510394670 378519756 338407558 226182580 191612944 715702094 663841653 905792827 34641654 519968266 633088855 366570111 622061949 976399316 432109493 984405130 818739091 983856376 885861806 788828193 730572549 293008020 316402859 248494827 946455161 491384896 941012362 278181678 353552184 845366837 610659517 846522714 540665437 752765887 621856564 258241714 400780897 118556604 480976244 890169911 734807166 797604420 414037773 99981371 503139552 334772264 30983459 132168442 853105750 68124134 890558683 990749660 869350874 746265179 844122145 825785968 40265705 737293312 206842639 778494078 824362717 42360739 719501969 954031543 71717741 176804286 380979015 133366052 521107368 499813637 113823500 531760274 419994784 730840804 309920035 340646022 307571467 253275492 345666062 391271292 718264767 908078297 87249694 989311562 401689185 127407309 899981424 511514039 121118792 67351578 525063805 603288236 422041293 338840748 438458495 567055370 328815703 308874524 628304213 869491837 656674560 337118396 833298439 728912903 27839796 347776263 578495084 279583584 115290742 702072983 911644819 581554608 366245143 847339555 611771853 897573953 661628962 210400822 232257709 497588509 825898079 448575317 550691244 251005622 85973831 227614259 837518288 409379263 486270406 660710603 332025535 424829640 363780566 546644103 512162515 414379199 915777717 87380937 332121052 358625202 254733751 864763568 87803592 362235536 528859953 43044905 797563213 846310392 170960215 91049122 237844553 564060685 161917243 321584676 677985779 3138287 3055277 668263872 570477160 513606955 431695573 790802497 897641329 387438380 250277589 368963964 345452344 13264290 19614746 764413185 193427573 440742867 305789258 387735638 232309158 244873600 21324876 421976802 641947620 443079799 353415742 961897411 927059039 864877823 700256346 654798680 745183761 24697656 131753974 49481200 323841233 43232160 431122396 291016292 719050420 644470223 838675734 142129765 820509567 870267295 377428468 935605537 566271231 672333792 701061039 16945035 558631240 416328506 9894807 699682046 304817402 159921976 802586032 205034903 901236917 899481124 805304624 102449532 12889194 746253255 238288140 398030124 732835916 562850217 977873364 775917756 317535935 58458068 561941768 405475236 735445130 787133708 478901665 385995198 983764453 353146533 382364057 434418590 970192028 54310427 456470993 610849779 2492043 590539 332463897 407512025 396290130 757177565 226075133 245183529 548707431 266518603 376290485 275341454 892679389 261129898 438707812 474415073 241904941 594448562 23528522 360703007 475313035 736292447 439919555 478945935 52031831 915499720 667152855 282394992 124728758 823939901 925093404 289539289 350065259 531896677 394749795 507882534 411959057 196290851 736101955 150116790 224707044 213947800 155434362 85492505 122217541 311229740 468167442 124342066 352681492 189885191 751649857 33763667 993741437 585655088 96900630 98235808 336299904 856944557 758967865 149004163 391521944 251631872 389960611 93546342 427994197 309696808 725417620 256396778 493641864 630803359 231235578 61384126 103796127 855325699 23537015 558858533 625206120 375622675 111484701 227008975 600530671 690656265 57226441 12975174 772876144 290856975 731737205 505548079 512185362 262149326 582286724 861544922 370570077 67468157 330901425 197192642 220848757 900952305 148830942 563119123 331816688 682659346 837850714 872754721 979831383 530786805 178634845 422282829 858957338 770621790 575434117 357658166 755446787 911103696 771721546 595230869 122830947 849328063 120478438 497338683 414855467 569488024 599477731 803306826 492456632 667183294 125926241 429592818 330010588 115733028 618167485 13708223 505761795 930492506 757802931 278065841 266731456 986667698 334312277 749110060 580170417 665831167 457877690 390002689 885889664 586496383 900932779 437284410 211334859 707650474 934219462 603946420 103291291 995371925 562664136 543892685 431939057 715665431 100391195 540110589 613318123 944853753 305666453 196026017 481641576 658307143 801965341 937526698 138477666 624873505 818547777 27795116 680763917 372495121 246830480 511370632 677925490 117932621 258749318 224865236 127289493 492036225 460487038 829120637 848308479 49050308 81014890 618281597 696536462 768246347 636146431 458353581 86611682 830293603 483142407 739446163 34535497 249225363 497122646 273941001 1656345 318070445 204477546 611677324 94923888 453280445 4995336 144849287 217181649 316253002 824491271 913122396 724777283 157170249 600423174 207075395 982467051 843985448 133202517 25030106 295375837 546254034 283349272 633435330 559633629 952641394 325469003 433505535 55823050 659188102 920287666 284004884 127805336 196724645 388749105 249995750 256468200 663537972 709211282 541149668 569479149 428432763 129906114 450370601 586574022 610503963 775127177 200858259 459449523 741122610 642961810 559134518 215501817 36116951 193401071 19284470 131416885 890290789 251413793 849918860 328024929 929589761 801992959 156353441 263211398 125315957 447770972 13794257 280301682 272165940 260262180 209583645 148514032 962957894 127663783 589498368 467276532 825495364 139135285 829741856 225390893 258471552 244843149 535579564 525198154 769506495 663564074 625186150 117471941 963148815 527826824 553707926 84531767 143981983 905980119 57366532 996772336 252111995 206702875 313719003 669357586 482071948 229228918 222160226 659048070 919564030 200802790 891068625 113779210 323555380 786780416 717534623 877890514 309400184 272256672 564592431 102153561 536447901 992073350 191418746 514209504 505516241 161338001 395954013 757814261 478038178 42180721 903032654 694502832 294763804 687848755 227663824 860046105 554900164 603906501 265549238 633777080 579267534 786080258 983810962 314014934 535696511 994228805 176616637 69295275 274471302 148930543 120268441 963356270 847677153 229446237 24758173 45484446 726090185 893281064 364749895 128111091 364692354 764184036 397558693 586348590 342583014 418218323 249888700 280924141 88197499 317709350 252716969 517702480 48531746 803246129 379516020 268858709 500885430 847512484 319655854 922932592 491240424 330445978 676122316 219609732 214782228 783088393 552270307 903992489 681257929 612616657 525852803 705825410 106743568 146401614 657485559 904842025 655956680 480862241 770617032 512551252 432691589 195868180 768395751 833645803 614041637 915557106 51113293 521061906 320374546 116033422 228358553 604496788 214706471 789196196 581249827 436231707 381343208 118391974 127823036 443891001 614267577 677435109 854955783 470323652 409560896 879962473 892216457 853543324 646431038 489552607 349879973 181221495 641214855 183652147 655528031 829377455 33565201 997464527 444978425 352038739 858859449 208016549 147377643 224940992 146253525 359590814 692077943 575050876 481886468 344672469 534353448 727754297 784807427 104210122 930700118 849528057 822979095 517343260 173218730 251434161 292475502 539523448 114047593 625117177 220588535 536836076 108043238 513441281 421399183 638782761 398713321 381171934 976321643 108488377 50213594 77471973 482908824 599081947 547408050 100274102 90891832 667441899 498304936 4016746 535796393 655435893 117036199 108835446 722027219 416312184 68154172 6934881 696165782 762354032 721138301 169652816 320838452 678165575 375734383 333686356 603138707 57054151 102110483 883465330 52090123 689054149 220623403 721053898 368440553 404953498 934105104 217579354 567105947 152630006 539531270 171319822 806594705 401683883 751264364 152249387 854321542 437418828 320575673 972293874 876533948 932140969 309472600 151504428 171575539 215851274 745151573 280915255 481171525 518318412 33077001 30173581 494617295 643709304 322637780 580458162 528118939 927506100 310465145 900773372 276508464 53541610 287079799 414380562 623147324 933488877 794163440 10525027 703171728 39638663 832392425 698540579 497240745 979521449 153254279 479696085 515252195 336165456 356978337 333033641 117571388 260536840 705162911 264795069 261137252 956727711 508508932 557521114 117103130 658113209 856602268 405575325 583806592 923981216 176922744 242925982 876139992 410109300 17243299 451611810 321320082 462919201 942830186 56751502 965301857 316880553 786032487 131285444 507334645 90681344 839482227 755074819 452579086 186666010 267824445 281499027 91067603 636414883 991557472 893007423 93214875 628980808 579461743 659692862 680270806 419644761 697536219 141575419 361021536 391692640 422438749 103302803 729057129 839192179 116834079 889822050 994533066 692610883 469602954 24908781 360646478 201788961 45176415 696093789 380639580 368349346 87493225 751433791 857426444 144870040 164757718 197258620 913635048 689781484 297028977 569813065 572017491 470568583 798815222 384993488 153485038 332769918 632958083 361340869 44058174 259583557 936542630 710358920 404750842 525040839 548209387 360420223 625808115 434712554 160685050 318086315 612109309 723327619 680889287 699193320 312449736 483252963 853772254 261978439 520890136 744739143 742432408 298471180 342511908 954563998 817221130 19569620 838504861 878679998 53461678 60153653 794682155 92451045 226266135 830839623 564133284 387469536 111935696 317126835 674645131 757469445 305584857 675324283 851511736 615906488 339999930 193428242 992042551 456077632 570773 434637352 581187947 239234181 489321007 312190599 257004801 62498240 900090905 219339751 576007649 317216480 291296555 708805258 227510322 230930638 439241508 891385926 82853879 330650716 337579063 23658317 705932402 751853537 204419563 305449164 592734198 890361565 123181742 560004608 7775778 159999752 168978677 57581694 509457547 548260831 313871872 796859347 890290296 143767827 144482254 667773202 544255881 646971753 178124137 469935295 748724226 793721222 106318724 769283513 973276615 628706419 811569460 116635256 609558764 85564040 444381935 493053739 800298915 966472634 249938935 7032290 717211491 164431831 238603677 783741870 242956377 529715371 892761555 427614359 838087263 237136504 354132284 762371919 142583620 161366723 563417574 383960356 568322866 901882203 593097606 488161639 801727346 780086282 117117201 267632708 754698412 15608381 993891423 71686474 155744593 219556401 193662911 447845045 965795342 969912203 723426204 89011409 308724590 14870899 236520832 172388992 171097358 994310453 137079432 302468539 647457939 440680781 598808961 502927452 951883335 365439542 534899750 226350472 192094221 865215804 868258884 65077717 996458391 665019214 902694546 712872988 552073465 383457461 534139340 22503666 504336939 605799856 788127933 451476849 151365621 576505340 625128083 240168617 694119653 159388633 997960773 114700560 175982883 878585461 415616783 581558205 202368690 234547793 169330568 7335338 145444451 448272615 617808554 818612347 209989612 989685932 134000573 115967598 776850360 604652736 875754209 351313256 619478692 887958303 419105953 330089284 677502470 345334819 617907877 597598503 550797192 325504573 394969865 959268696 472119685 464230735 560261072 465019925 277362704 40689734 20198819 598276500 953182742 225798101 974188756 520255146 605322591 758747688 752572240 687406211 112452196 773486526 870820961 694764860 446261221 501435728 947957254 309272613 644286966 506803537 204703292 622784412 163478025 709516082 73812043 256472203 389638197 433388385 63401222 7362678 420054213 65362779 870538340 264258418 225811866 210620861 335934737 149151971 483739537 262588462 418269510 883001241 326707406 976156996 211567682 157938346 524116521 735706855 228319546 209849622 881485720 285032847 105302360 472371842 948184944 164922393 528607297 968372832 449670139 995712186 848548637 101846122 579157792 241682974 131400606 551242484 579956541 564443150 700172625 709518786 727859116 745166619 498707836 738971735 566074578 873213412 524558515 748208408 703982408 603803726 305833216 988775773 700474277 994101275 121785297 864890073 332873684 337460903 475798865 496157412 992153234 232577621 617376311 663212480 373570389 386184367 578138701 743214948 227274911 628716807 215542222 445854290 400360 516357723 558947736 692115319 799174776 549892619 390570805 541355553 318329511 344832364 369707976 592895375 904735550 894048258 651332863 897094002 22377764 887187588 499764290 427008115 931091475 641631798 361015945 436330617 582883851 472972686 331170636 710021468 725609369 446810029 227668306 93762898 768183495 89859477 610962343 611573450 733896331 626762531 312005319 602630245 347127702 747140374 50026104 840569972 252589510 699584827 298844129 309466159 169183200 16518138 548213671 617452981 677257949 498501905 663903845 926553558 815553695 762633488 397714420 661902065 839557438 583852383 491394416 116395635 337559826 832612014 453715267 411744331 753303522 170385841 709176406 734589496 120943694 515074082 149346181 256261542 697960070 623897376 918758037 51632124 752410040 889395453 322567624 827122043 236498541 34336884 593934688 894317840 754761530 822485067 815771502 943070553 130816612 889419864 308785851 336144469 678637215 161435450 898576240 566987212 721853035 650643292 891828093 748535234 415190731 629902586 979258052 659161148 750907154 217203624 218118952 478901946 480736461 735947873 230862483 557190429 964164111 973224037 787083346 380489506 79197833 135799101 912689856 851215119 333585684