1000000000 5000 168520595 822830182 654797546 682294887 885149786 368906447 449658147 357783567 515567134 380974805 779848403 48252767 854197814 352818706 981011684 787072270 868860307 251263830 744860603 692903818 695126429 344353647 414296557 369404756 950879312 241506217 756615943 475577573 681401914 139063282 251928754 151825074 990483150 268364321 775251900 18605920 846761871 237269994 568469160 520689984 753579014 5660443 913603411 106671706 763375246 82941905 258505489 995826169 999379464 475111860 518980323 142677621 708764770 343950356 829995385 229616190 534104761 659303741 928427514 430804131 614227135 108731391 686387270 56975792 901171721 579281125 933281192 834303007 958997202 52051488 784676772 751203160 809561791 366531192 972617813 33609452 86993304 70999617 160413465 238926728 475187805 331102426 862438308 839933373 921479576 204923712 341754820 94284437 955884355 532026787 877748872 127271122 301622552 334196519 566806307 409301577 881504056 368385054 585510923 325828490 885866959 828148880 992557175 47281685 266306186 109775476 567489361 58263061 460007652 267034352 422092799 91190049 396953450 673952107 690311990 59489308 804149933 277428703 389427979 448631374 872005348 376041799 759240423 252629541 521939985 266981158 494101428 393203085 771078455 541087314 855281429 77508668 359858871 237749188 958030285 740186695 919876872 378742688 921225305 82282979 179640041 272887429 440707212 145665942 702737224 437514559 927362059 286363888 667294742 638212187 909177513 215288109 499368461 96413153 790171173 44451804 976651899 340314102 664898912 72652064 395681818 385896216 814885367 458782196 658542555 736430810 788806774 758537349 799067746 42100592 555984650 157644636 241046331 576246345 865428435 716724585 795334077 545956429 965061088 444780490 708935680 376064367 808427907 197249150 456587896 406446909 761702670 140426576 308156833 108251636 253176157 357622373 426909681 161593231 963286451 355915715 615124466 434602860 473749325 403045195 527840772 676522339 886294889 579005204 600290035 374256058 632759583 231822578 374495503 367612407 725532729 122599430 336567737 210099113 874830763 13543827 114675365 168424139 332425352 216210783 524856568 160690081 970956743 138385331 201284242 138925214 176760394 436759668 684812300 909283160 990726447 858736192 915842893 105512450 375362526 165689756 917821229 228209514 341923808 676852690 789546350 8399353 855887324 436018612 660042814 214903453 832598015 414595172 891340938 66191735 544369479 119283636 442012816 935786081 976338576 56314875 854371373 309055519 876070593 598238122 944696962 165180072 421764104 86636692 271690942 226152901 379906732 368376493 483541384 226537163 512418519 223348472 449807015 149061184 701606737 376181363 736534264 337936516 822400330 781770671 934529707 422939194 736116236 323345841 835258414 207369686 944355200 760246587 942979083 770367502 985007561 135168230 361381881 262675710 670611225 522868382 660427665 99421314 676938303 359920948 855127178 447888256 542601430 188036732 286421304 508168452 754819492 218798568 489919176 253809319 469525414 244368711 593612988 401724170 668273698 343128321 745692173 78121261 944006156 955989288 986754802 243002612 886061294 706839110 912681276 92205997 541061186 315250848 856989382 203060841 313121466 406669217 520038142 856091814 959222872 168277844 744753312 39847698 220339685 230603233 611308223 77912392 577775384 384356350 692975696 478479535 860649944 455292925 695195992 223323440 230334615 324084751 882938333 162363166 383138300 784596082 930992359 411513293 550773538 320159616 320476756 454647588 908749283 114999739 851401348 365284689 640021990 150118772 498556798 454654751 792587564 431092229 563328454 613828524 720355634 40681351 933212850 664931833 709208432 694994143 931650072 151439560 291212223 80226818 596599987 2500400 467236341 114540656 751102504 622233835 699104283 443742637 487692103 33006300 291501104 68572325 851555254 575492757 687578863 191579441 512344645 487356005 912277863 197671376 810024894 204953210 337203212 35124036 239902321 316464134 862678294 732747780 966692886 307763066 687070937 47017027 587261504 216648300 605926497 577197756 603211773 348903058 404383659 840477621 945970018 181482015 228405884 279090651 511478079 379469158 900572697 149531867 226597346 772636959 887815425 216491277 572407790 54823159 828834675 38935895 687377404 45188734 732613494 666892994 870916333 269763353 580771794 101130689 176214176 23833205 536349358 55332621 696944852 623717573 870833132 5858507 190494259 613286880 844636923 77434809 357014007 368650096 854694675 817693875 828887877 370535661 784926392 731135080 997097711 357801853 441979800 177351318 513360565 160079450 376325326 507615504 927524111 414205048 711983699 692134991 963308883 682294519 879562247 687310770 955970300 520477905 952482429 751321949 789823997 666563569 976013958 42905537 96759576 206507188 927186771 489118592 820366808 4492538 474603967 79304313 525681401 704771288 996778563 314982808 402292871 683985875 717948626 307016873 850612314 156387331 485753522 543728128 700995398 625735139 900223007 37373417 176638500 221773701 913496418 309536455 531099016 326253458 334747002 48758805 764681403 311577598 728128558 255297739 342171295 194613031 401954332 238982952 494222230 794904929 909956447 400395196 602676089 478391754 839600274 254256544 562201268 712529515 848048525 285638052 480752298 631263998 850379379 114990857 419624222 673163939 849902915 118972434 858599665 431693437 764418683 752412543 777364232 457376649 583189120 390544540 709856361 385149907 543076777 63586378 770438910 327002373 477573075 256805782 541937806 54822309 104985257 263632162 341230160 787231305 938820395 810333734 827864494 408167491 527576136 708866448 713182066 735840330 885898147 115665043 643008085 240256573 445588268 83800340 835500018 16558265 76367176 45179323 152186305 78913039 540628184 135873286 971035551 429633539 711926422 666116385 879872899 145707428 439749651 109860724 725783255 720285816 840580686 6604981 108617112 4678196 89151975 355511820 975782750 290323170 684486355 166612560 473593665 195892368 731934024 14516769 214563499 176792360 200178133 174283047 292121119 218773591 350603371 66781384 244822762 145382275 157023017 479316998 861661645 225934896 557954430 70337945 610540005 161067884 943658092 64717578 715304123 99227619 706940252 42043132 941569408 428768536 874493532 159867159 879590811 169169933 393716655 360918458 726245331 439082973 674276343 91066264 487797986 258710479 349694638 68803358 559026716 653304972 779855111 809715450 883679457 45809819 861158078 80136331 110372959 536402920 587740966 333949325 412409982 2629140 322820843 289818024 575364179 99288633 890926078 7705797 927753861 237098873 266873941 658549819 860065492 528028118 603837153 209968927 765988658 451428764 595208763 684551733 691160426 236479745 378877779 323768511 354635940 378355442 612848046 851174919 877951277 153259832 382332350 553717839 768125402 161415807 754615603 934058686 997717018 859527296 947728252 228664119 274341160 485504913 564218077 188635327 388738119 494595980 770741964 530243420 960880947 754050147 824124502 743458923 829499410 359538537 754311711 665078224 941857813 612086687 766275657 484293200 908572738 233521785 980439243 390241671 945518635 122008733 901397176 326481778 332212944 417879260 572322312 779882255 915855210 209840482 422622216 314398943 760901264 510535514 894027950 94948509 975474360 401821299 838295759 498119311 927284288 213874610 426576331 154541987 409041266 283848165 980409821 32991536 759022421 884759567 978638679 242137520 278794397 326452428 352478783 889458151 957891946 414987287 704332330 532078352 777953021 401625708 439358211 89918027 317370255 76877189 159258316 474643021 491248422 153664269 426545547 71652194 988685046 116236463 961434782 216118961 856903067 719688249 897330514 607471853 801306689 645543456 712510881 535404799 960063660 603847368 871537336 35388830 814077518 203425537 322947688 313913253 682629076 245315149 619510209 639264519 931297596 754238834 903486436 170088911 566294741 93139945 97761226 343342743 636148354 212530667 984333188 4087282 113442093 697574163 983632248 245701758 323603989 832448656 944267488 769423381 806909957 427699578 644954193 365082366 599387988 226448732 996063011 857713442 976284525 205219142 627225513 761141606 793699800 132489040 293342018 531626776 703259221 587969197 779684607 21370888 175088781 535854675 989546207 13494436 988140758 99922649 215724627 198681720 286247477 288455104 354993005 438439978 948354497 374252538 702481187 144449236 329014857 188708602 496190296 235846384 741384777 628914938 911501934 317021298 423989037 231282560 349873562 683581447 980765852 10403890 237057517 121045900 743408194 289939125 427097019 652397277 937913067 238540939 993254426 236822194 434026264 249341394 435734402 506477805 876434699 616025232 681345919 16879249 386321677 156960986 858351604 111357600 141342924 241138746 320716182 516508060 528994898 302782889 390736596 510135121 898880066 330622513 475930370 491184880 611107606 87590935 956906585 121813665 215420033 12951075 323784549 774700767 833652496 488427083 967936504 361417729 517078050 29959377 611084186 105239697 289606463 684422321 772283461 308332724 948411880 189222127 949569062 636819767 969360790 150840253 681027290 225927598 893204215 141826154 839508237 795703187 952667343 456624947 684702528 71593992 151200118 158248490 184160548 58566986 160470635 415797713 746430586 392297525 770144823 129701984 235774866 277734944 831438171 484099574 517947063 75048960 708962235 534602754 604270538 91686903 797590216 508897829 660109624 405848418 718294074 694886203 767887485 53862943 301648115 127626068 744926549 492513886 846403895 654547267 908053768 664278578 994002751 539924200 894829470 122568681 162984524 469550300 619569371 601470744 888490800 314368868 980256479 527949115 659785045 186262980 984968322 333185689 573025364 63856750 169081171 336589922 518508401 120734439 582020589 499380954 856109389 343551673 368180062 176950286 294919722 577568978 779164023 532472149 613937429 534330833 596236112 25460299 85429880 642071317 693205243 128382019 186126144 49292383 140725548 607966750 751389739 542225768 776323663 363309641 491027219 689049693 810743651 724859619 744611930 381484185 665382832 825871242 922970854 203909979 222526545 126304477 772287726 77082237 669495054 32586616 598397412 312402470 605616369 384042135 610393042 61037255 378950197 655616852 673841799 171929482 987978467 76903183 377469259 911706196 971264102 449766577 632255041 268885279 836941261 697432034 994151088 44096898 543311275 368933732 954142540 218319759 624861125 121190717 673495995 419306450 614630844 302321691 728849751 42693684 795053378 356699503 612058873 132428838 732111222 130997667 638146094 54670915 733839894 747623640 793784711 449553827 844131860 116520104 769152030 99297383 349365443 347106782 899030663 37803488 131085195 421940006 714347391 284607987 716045809 3776787 151435023 110980462 168897042 580343417 904475948 299812251 656162807 420342319 815975717 135556977 499075977 750965720 876955878 61002199 366821345 660085797 863607470 486406452 497717575 18910061 286476616 523987023 705907378 233657559 689011351 448680561 989127393 330023231 920878972 253317273 746751896 65386824 528628694 190767865 902639777 754255991 845498272 352243094 483215117 293589335 966404042 336559941 687597770 196782042 912776645 202521724 723542395 371468737 375880614 585061319 589150389 176592931 706195088 319223903 347502832 380474355 560887979 151488685 594894405 118779888 319782460 66027497 708788396 545085740 555590756 107853965 560961127 158317154 206444470 656975736 734220230 892765693 949099470 413065093 998935978 273726225 392335105 808506372 978762828 407801732 510339360 299618011 613336022 344580817 911738205 181693017 238578801 9430310 509762920 356277421 596421043 160197294 341752284 587378613 623027230 241306403 878711126 102491629 538016796 123253486 792903765 268532131 674857191 423730727 673658009 924793273 963065273 230824822 643199457 115754914 777724226 828888217 887128639 221810365 920532736 220612666 401218124 394903872 744877216 95358990 309616620 315029775 756494502 142708611 610924431 132953948 628516632 281506262 759473926 413787574 998199219 661568152 714586102 224737705 614426517 638055521 798131253 159461453 294469490 563794769 990273566 28513992 320311203 305956703 523966241 249320523 953461362 469211864 514373416 72332553 937967998 132970059 199022097 388368947 947140014 34558254 526603062 158909948 914691630 409779125 768908307 418955059 611013513 6441765 978378409 333274177 712136183 740425113 743045828 340349302 554416928 69475683 190587809 314234662 868921879 815233631 977828007 147403249 381114988 238631250 591666627 627179192 878118495 950889146 969218561 130040919 430592721 423884687 913521393 220164143 370404136 125639418 799694755 99709398 354472558 601774006 931872137 161498347 556179986 780510928 957352673 203957594 457647500 63280608 805522256 505306210 938757251 63619020 191582846 765053506 774729631 256570009 622751962 410876894 803683035 25610298 443248983 199926370 285536108 40788938 394690213 506148129 622569215 146114430 906223514 79618563 905908938 951853453 973265519 140649307 904539619 471447324 934652436 107056595 221397854 506536987 849219351 799987867 861385125 349269270 826484159 259936319 796309794 463818880 744020438 497895317 516626650 610308138 737917305 688637315 712464903 10288554 924115371 391894704 677481787 196222737 574081857 286261538 662892690 969327 305348799 329872371 508393810 167670558 530162648 153460607 712595830 391613305 644998236 893357363 930640111 297049477 534843897 239691453 561697030 52487296 683094081 34666897 292999011 571786662 787675211 387441360 665978111 170260089 351575945 306200252 609233536 862939272 911390803 587923778 594460707 405065004 947952315 951095357 964848850 189590305 911372205 316589993 706026645 98186736 315237586 6719762 996400453 102247252 902166499 252972683 747571374 18450767 621955390 382273365 726507201 432750983 612060020 100872518 466346155 528618225 634464898 453757715 471381775 223392802 809477090 634319478 753656264 694581133 894096947 756065824 885967944 35531948 995324608 162414565 780237290 802659756 887160255 123422079 844685117 612044472 776493923 413718448 831227127 539986556 993959737 213236559 502370554 236258254 767754446 99928011 447667001 446787349 851564407 305422862 959812857 490621126 627262613 89998899 974037103 674121019 743783901 126697724 853184965 533503608 976857851 259450044 784386915 4519607 196310632 183787702 720308546 559125347 909158684 280189837 832276596 101156139 825772588 479521830 826510442 211079796 829011277 157475503 226968962 86856378 593189864 339561551 534856126 284241030 481272053 920027219 950788601 171886948 658973256 203060262 692350153 277988711 368052238 934346039 985501313 685074775 840387956 760290855 875026862 86833916 413812517 594409064 720467931 90806868 110578328 19120410 723803900 307561292 449498666 319659432 980074654 136786582 707334100 382075354 488237649 344105451 962509213 91648448 891342378 341679799 987850183 467523660 656890464 489165090 926253278 238927696 881306559 82848131 801422226 31080277 918054529 267895815 388459146 115037113 555893148 98079412 151897094 30668713 408273758 430896719 737339512 684945961 693801226 749529304 964040635 458630938 480224707 625316193 751052012 412067041 886086994 528470008 816052733 752352021 997448104 915491364 962303019 730800479 820501246 487444347 508732991 199052796 838496234 403738136 571829824 21073755 748740674 49938022 188529131 455523173 954086093 215905853 261939928 119633244 557119879 526195886 771716693 234328082 530396886 43368231 202384842 633368641 894433171 157210390 644307947 117924066 794020728 827528640 833081882 769225721 850142248 625149842 848656304 187418994 836942949 69489337 762761134 145213242 600304325 846869997 920346077 293739759 642110845 314414253 954158899 13312587 973158572 71818459 808376867 751687968 792408034 277172664 946977687 282263127 930584488 14267622 70464762 60958279 143009898 188832609 655315836 653936975 823177550 501463360 780968723 362446109 598411811 180486921 335428925 491412780 497860990 490965332 523839299 71946032 975104853 173070841 828398406 235542560 378904999 160786948 629759768 74740485 447189546 703345300 849836762 113203510 790701150 252153440 774082776 200166876 546346590 233657941 248485405 742002540 953328001 355215252 845335806 540916519 968228054 401507397 434824592 298581264 635719080 396039417 828598592 272127570 712537218 436298485 949799526 802137568 965871901 497366575 932441137 260113683 473248277 24774071 619754725 404668410 500148889 635563471 941377985 622637053 771831368 589828871 879344152 574835925 609378045 15577665 753075342 187398469 903459947 139561640 417664488 385785242 943388086 319635141 850543284 255108168 730624682 101113605 166489522 190761879 700139858 238525205 689783032 347293195 874625888 313579358 896057680 95565462 824708259 703152205 757270878 812336441 866847935 540275036 906888532 176836046 672721659 78443182 391074424 153818328 813342258 418998529 697007999 858126683 953409297 851143545 982072632 289184376 557082059 545196138 642219398 414823792 612572363 405908916 763365951 718933747 994455077 30712299 178477172 632371799 973850671 40971315 930541317 550941870 798920844 448420216 875996756 464201860 970654803 327627890 985834922 28550307 459086766 239218278 470850970 364830624 641556357 681180910 824844411 259756825 849648985 521222183 936710799 328890034 382380769 165239151 907499858 8327490 965204001 667597496 710685185 459473047 768844925 125528450 409349262 240000618 965135082 108389972 658018472 590457863 988183538 476313477 725531727 124189573 449577982 261268950 613272660 129588933 963536689 791837872 808547488 541873198 933025747 183528545 183636740 176310294 325009696 332960331 839243597 691554830 798818080 64616206 969684728 274475952 735263966 406154580 698060199 528756240 850787086 158422066 194741959 338710640 902315593 131133412 800223372 603217573 969450454 96041539 676433990 14359439 568183914 440168450 586974020 209618189 678202042 58173886 128327841 184800162 574957360 30152068 621720749 237956009 868780351 315551877 400522386 479377653 826508973 305089719 963653795 367853037 411154741 400378352 583599137 1848249 690014243 602948811 746052377 244683698 848680577 139057195 203712702 763893339 907930369 242837612 354562434 201807313 893358156 267748906 345951368 31236713 414800273 239340992 579282232 80856083 782554271 66368158 492719957 286198638 817091692 287299504 701870834 148636443 667157426 236535812 525243878 64214369 596866080 74932686 842678886 456448367 635048457 236198893 329881870 477550368 927980677 232043513 640425122 99566116 518456676 184090529 328117327 436030222 509275709 152750306 253221916 250867282 378244637 542023130 826402888 557936511 687501844 329356945 784454494 437293131 920778176 213164586 312121255 793311438 834235430 301960002 898414011 844797036 917702123 133882808 325584566 191880638 507494122 117219994 445690005 233006731 442211241 163338296 572099276 111707193 654152702 624399588 647896211 416966969 793994410 287822992 732905928 367664987 590691743 373475421 804496788 182683520 201259382 61904583 373390283 8186581 942761289 356419637 489069502 195361291 518019871 645805300 897649947 666926766 947435310 155340688 341827518 83667158 794325930 280091066 650698771 274044489 750089069 329399455 805525331 119437181 584364891 438555082 566998931 124212202 968708399 212714389 673639650 75310222 646803182 20789697 973985774 118026325 614415618 193849039 307724928 261094882 685049685 164181010 743354674 523984030 972071374 550497400 716184891 455690330 558320397 160915028 437912571 102696786 463362714 624108600 784637091 637165422 644545490 278318322 736662621 570681646 773101212 886799203 932653259 224308412 290103431 603402493 982534567 134824360 449279385 167980388 907204925 69560980 837469032 441217615 818712389 198213112 910890315 171218862 627635428 53023559 188734764 808002703 886469713 781710514 866227537 35041158 620236498 209433840 685873951 516717616 737339690 67587701 771914191 488637869 700115260 134915833 790823442 574235281 638489445 340225063 731843782 41402928 879195596 249546476 859591509 135280197 936428258 368519996 725707845 510819487 643442918 394281148 617828292 221630609 612426195 246988209 609324707 370297936 760596002 603583305 684468406 754076058 834760222 751646995 913156814 773416825 924296538 154236318 238025374 712721756 714124332 164870831 605577706 231535467 272906543 300129970 940282499 325190999 337187221 577226668 975652313 238990939 863713677 343359545 931482988 874282626 911029200 810841782 837536824 191119194 564133350 215233258 734049425 200733347 916130012 629006969 857153753 386649544 856446373 746566315 854811634 161647824 666793937 15210326 472269290 216292753 370069611 52510326 832005749 734678976 998890966 274926870 993049765 186362417 290636400 902133850 944410804 802364933 966611023 859807264 986083201 345044046 349969964 269888730 584239003 882145472 910021146 10729405 881413490 162071888 986632204 21361200 451363781 166201585 542560024 184898448 956183879 180040850 420566039 101495371 615716886 468255954 958379310 397425880 801535306 8188295 737575079 397309826 824883769 202116417 857872191 144481795 356713497 214759871 219621705 53844192 310867311 651965300 874132165 352336574 763876797 139462753 828806496 502834190 881817262 62800222 297296699 309150391 864523982 841096624 938220708 456207028 577986561 257700241 668354278 148295684 423069261 305747802 534893550 375742115 617983125 253055314 822181937 564220758 581065943 56141721 400873026 119193202 215699755 18207146 195206672 819600826 836305995 759993522 763522995 540280932 794825348 45718845 385459094 339788243 767876897 403861293 433943993 573687649 962423858 659765015 722664818 792576712 986278448 421671462 553298122 517116381 887103597 365461653 415388778 559152589 612544881 39476638 832762749 2754363 31039437 157494414 622785807 362404417 959354236 134284637 544126696 486609724 704160546 209107468 557723196 124269452 893904469 717571644 757231769 217327823 550887102 499318007 873132342 301805775 473454135 110974364 380778019 187436184 737308055 28912377 562044182 674615023 935666110 44983501 63533898 178707809 459186420 396404612 400212390 359416923 992005509 323831414 721487664 39697329 723185974 98727361 620649085 71691280 774034366 597759735 955921488 140871520 944185016 372297662 663903784 807064096 819826380 308998767 564291038 518130892 912126435 598836307 663190909 294881590 399813554 653952055 706675095 625769581 946357553 75064384 519672034 37655776 209682679 133150730 146848667 96108356 537921105 577805803 743049904 673239910 891587497 769023936 869167580 120885569 755977653 609441433 762796359 273423737 482485690 869557961 990476858 430761844 952232375 151475444 661373684 393585604 569736085 289084988 745314912 553020373 977160128 758516759 839533352 420604861 894603475 743308087 805642770 359207598 734585198 491854243 637767743 845495837 853225467 682217285 884644135 217027701 665224465 216687060 928267246 624321741 908044753 191343928 473453407 93211120 105842078 261568221 269221891 307004083 778050401 227261809 735169374 44130644 837255936 602375607 820365723 628371336 784029484 214604192 633946908 682484389 803459897 203218949 426638853 478112180 535284506 195746493 468811664 40516406 403267750 898946096 899077811 428831409 447488365 401517817 870240492 360766131 561795763 426438375 620223160 303883517 729458543 84200695 613157392 720120419 956047295 204393734 276131281 203329623 353745761 756264446 757367100 343616276 672766190 389264913 464522624 250399462 798118118 634202282 932542094 329271802 865127764 417115367 773801510 583599725 768633413 57676021 633399813 874235747 885407798 651260528 671700242 131164117 472243171 381197986 568616121 32272438 621789053 215255973 753732341 588770523 822949419 164314704 922032711 460873436 881414990 260879039 442110617 88373016 427633646 74576748 443488964 22759705 389319984 290155017 492136947 664560106 972784177 91179013 984406487 219922945 329420587 749285465 940841433 715430709 815879465 168983778 295727767 146756377 766129832 29466092 67605677 4290454 448911383 528276071 937573920 58077526 930435469 660761988 846834257 35779501 577300548 376475894 507684462 285680821 789969359 625638657 730149895 592226537 604515994 108868230 205081349 83904985 466301843 645627717 871145732 112361136 773131356 635761526 782474881 303625270 988449636 756401498 957532381 519500785 520975818 507892224 842005490 528215504 739045958 178847487 232361980 177845402 245835673 579077636 720667003 96244094 374879925 423059262 479390906 122810999 238362964 331084236 651286129 908778000 909299532 542484593 620021684 365449589 449899075 105565841 987805202 474146674 954679003 285766271 483126064 17117820 863083799 381549329 410602269 675951373 792663026 7073005 121981308 262218123 856621768 24934332 963385442 375435469 798172725 352792915 825887052 752361640 917292148 870244465 947436343 272085556 932723755 355824348 650166341 838530451 884095419 620382467 973446539 701130256 732813856 111867761 429699786 13814493 896810357 71855679 792785404 215699436 540383563 270619499 400205906 148206050 322099816 160750626 261666591 427045255 851072496 473279396 937890084 563825261 873081125 295199612 932524576 562134530 713043893 52532900 56510879 15200126 631383943 41258238 144482458 136046329 767336582 102763806 827594981 391172478 835595465 121660749 663793871 525931452 793140885 603862643 898597214 280087545 307336493 656485043 794886466 212651140 795823523 282453733 914344139 690974587 778206414 292950456 503525128 230366052 304996897 294625506 315285065 368038819 372038276 133512520 615959755 239584350 444993307 701293110 803021759 423096555 949049109 684362272 957156437 353470425 975923591 291986317 480566398 457464922 571455305 374259150 794120763 394506605 743427288 229365845 385832926 670421273 681362274 688424009 993256078 152004253 641015306 276043139 666206118 279716461 718027750 38785860 127831024 378606514 826722382 344058719 624661998 361420982 954585861 390969755 402002962 512132479 554041324 223167478 749374442 125747371 484221808 286350839 701447558 74491523 348299949 830817870 901896874 316133382 438332998 599670614 922089164 388939834 516297808 371555058 800771124 101962087 982352471 3595303 808776951 84086285 166158300 179436536 788445369 115687709 885855735 252394380 621680583 417786785 810332047 622632644 638719392 51258452 238426046 299080793 855785355 301092086 838658837 523604388 616433319 300412050 469086335 16411924 342544945 189042869 243270474 800706 246451657 147244630 371723565 37646030 132132412 240414176 963631662 196740315 551645981 223557920 452222865 87900286 743903181 713405430 962115143 601735429 995014405 248419929 514238927 159669091 216347576 411150999 750482510 376129805 499462485 153001977 378220509 720067597 912691427 57127651 344811009 313665857 315872606 91641287 307966303 438715747 783267295 148610877 870724522 73342 896085519 44303143 134504145 598763290 737729994 447109580 961839828 393538736 396535990 716625419 844147777 480993695 683584952 199368458 501189174 793632374 821144637 266450583 933674816 466712347 686413094 57757674 996291671 251177593 629979170 196785182 384407700 268650592 615275393 349800182 808796740 321311295 404008402 604855605 648207962 745228968 875965320 400955207 944521942 602544608 863251030 142025651 552702227 365974334 879019887 185249770 692640561 202736805 975655345 35842129 199610731 419906361 956519434 227814630 736876868 78050050 789003638 212974845 778771947 476711469 574957055 354935263 445755114 315699077 454018852 246799245 546374992 540849851 797188239 470500324 668804951 111373189 444246169 450686537 528099603 80787614 140156342 550649178 931627835 65327969 425508723 237365541 574491277 204373792 500100093 792010976 955900942 148380610 229211018 98389314 452242215 393011603 601519864 36773812 700939587 127420218 975870140 120167678 972923309 88707024 700646511 252271131 624389221 96419738 890037445 293728820 793203447 300317378 615374591 54871553 425267585 748857432 871257933 465982629 516940735 269047490 933614433 359501584 412641495 239451005 587072072 351343757 739506606 405988007 667703727 263882537 501955201 566147617 834952078 101859240 597256973 359216262 501077539 523032281 569123897 342635445 896019716 747312943 984979399 768757514 834236995 391960775 596114237 286273876 830518699 491416161 551012341 586545973 636726028 507786003 580614495 211474434 619137449 135555243 988676575 921631665 931595323 141755257 853058442 171336305 930653240 57672720 782916853 488445564 552662981 196457558 790885850 529098266 548492313 705622993 709816222 587707051 748708674 319479086 729591157 426728923 702172552 276761605 419390029 533014944 776281470 90526266 650189465 256124471 586854357 185501528 395825170 528321852 741742651 266852297 651217719 558530061 853778621 543997272 837881287 385660426 918711361 827222561 856221766 776972949 859857146 307191699 359328739 304480469 420288130 130039367 248074547 241052519 710245384 461189522 850761504 318311693 390842325 646085727 861699970 235508307 980127756 41574565 117806618 795756003 797936029 795332197 941915641 431842078 668577390 329240249 532350646 528658820 854027159 140983981 201095697 398488274 993502559 28555733 574403276 257110643 697633550 169031730 608041295 460007506 804832062 173290029 994509602 39247757 617757643 495284088 589721967 199999314 683388886 54767712 234456789 35862643 602088338 67130368 321774833 682666270 771677672 167529067 876958812 247737831 402782303 120502353 642382085 207863696 366437081 601024892 783317138 161003756 323192059 350072188 785054094 97419239 806137214 160023503 776582338 61374972 164796429 552853812 821020888 688115981 937656638 105819998 397598815 116278705 378259841 97782032 287706086 585843924 717499007 434987379 982317541 498161914 716249797 381864590 722731929 823517701 879462816 448384023 967961833 407641591 514386708 30277196 966208877 611903888 972829041 199917215 765924894 513245419 909265880 526656674 798377097 56128049 174421006 33995592 913056220 235729460 301254413 160658287 773478965 246536366 929738037 30883885 693136807 813818086 824850931 411551258 677472498 343257785 902499726 856470762 882532875 94578860 366913958 25221146 357264572 520613480 935749670 398858897 600218055 843401688 925810736 222767903 846692148 141087057 194221903 130209246 850585719 180208307 821593142 360996087 574807331 225363093 377629020 173014992 205936530 457199596 982324248 2437953 108417412 310534777 801097705 405155448 694646650 178977822 231527865 529176582 640146808 76407278 710184308 34308187 387996907 722979905 949853397 321841919 660093629 323328769 874504989 477409092 627360607 561738804 595586213 112596315 767303755 23840738 585616882 181327075 980636688 288813480 559228186 233345773 924818646 694265002 744471987 416105333 853337350 539896131 604984257 109115848 600687666 126155716 862104286 549625269 746548557 634826154 856438845 180085752 914704872 515958268 906830020 769446902 951304748 214741581 806924353 504959259 610640818 496870309 768208504 630561087 810573715 797127317 893512268 382687145 742836891 132496878 479616137 616190325 746187853 778835474 980605409 569335413 691515113 614943039 660281483 404066158 585463804 685166749 951118387 351931959 649000630 640762371 666831198 186245326 868751196 218343020 813713304 162110289 812551039 98566192 522456376 140818895 792806790 642122768 799070680 622661692 963311597 59806917 638573588 65846587 433032482 557475391 600821036 75338584 746869252 499457026 684814129 549328559 901519229 191031328 440964988 790820870 818092135 675782270 912715000 187062256 790083743 358840338 597805377 499572059 721792452 112171419 227536714 475187177 813371346 149587857 250119307 123495488 952253235 179869874 673012772 219521953 601011496 10909800 585848856 249318253 680349050 521448949 755196141 545785858 885090958 340720551 933635699 36731458 367932047 28571190 350092053 49518641 155596856 528749902 871758316 103772320 656420055 546415274 900259421 322067742 731440839 235841200 441935042 158753950 860960625 281374722 759485791 11021705 404264505 123024354 382825113 532267082 534980079 277920507 847202077 633761970 910222884 57490089 885097956 37656632 636699551 142771649 566021390 664456791 901326686 166214049 888429611 24838502 656365261 940547536 987778126 736793123 836743112 44062064 800027024 369346230 800621606 269834097 359455981 581734197 914993702 361491084 611358449 549148570 787616457 153403509 920639581 345169780 917603829 411916100 839672250 521374857 823818106 405264763 727525435 754961590 892994539 229090644 239744918 88050759 391285348 80905520 520151769 253456316 318048499 729527196 933820859 408388005 544934389 78346485 389816651 350996626 931630704 426568234 646992215 135778200 910548826 178521913 706076040 127711929 227442042 16638196 676325729 216699347 672308146 659842451 975264859 336160705 838694279 287191048 758422873 162087725 930396058 447328360 622743706 414994107 577564483 771967534 886030615 222527010 315240861 777990237 993606258 273073794 670715391 179008264 824517919 233898881 888043090 322179506 942937243 55566019 412393306 663876639 942127800 189508749 896519780 177426609 442637022 77142955 294146252 656708202 873225302 589451162 916467077 38897412 534687430 171935100 578752757 14155357 712918397 363510814 644121879 555616592 954162852 525989443 678301493 9276023 65371210 350619554 723517162 221532502 752863541 218932490 775655716 223831561 968579821 232537531 387074004 461442137 639986678 89375929 415079174 337909559 422259293 500642859 614036021 40252817 560029755 104281999 360830627 649144111 982498507 571773695 757860577 369274949 686462583 9603037 309435198 342790262 565266740 333557381 656395632 358793813 497812185 38171695 50624207 761374515 932587327 227124124 790855327 155074417 866468142 228918846 756309858 412146526 901416284 383474668 456014629 798346715 908337962 120456420 884432745 471811640 733134944 241202285 800528940 435396933 627779939 49748226 511567199 178090662 815408688 507301828 675737744 645592109 923287198 414894087 498097256 332406039 426994505 677392653 854882194 424972361 428228764 73751702 200947706 595489517 942538271 298270219 833209245 173997559 896453922 355009136 563697646 582043524 987637673 373501175 504299560 29378729 832619164 105679214 191463033 22023601 526441640 116012769 776336017 545861012 916379045 79210486 419285960 588722239 599308262 508309647 708729348 324553799 878539461 95179164 269327821 571200503 701428839 244259729 383200496 785514 475830756 15581060 838322939 389265530 720950737 237458881 296773778 416868402 458017200 54290489 518579261 241743626 626288150 444392898 904874712 147459268 346254162 458484270 776476244 116237988 541352838 44313506 287677994 76361818 314473837 218282521 541971305 25224212 872074059 79537092 549332748 920229178 962323284 266872767 565708032 514282034 661305136 92043897 229511773 163378269 684298459 678603306 701449630 390733708 842741866 617668212 676917603 416907705 673227049 547729427 560882020 69028729 808326248 172650595 716143384 439819811 943049721 408885825 944173622 26697342 967533293 155010139 913124345 159733762 517585340 396590440 608914289 386191879 423330600 101666544 497128962 55724298 349494882 122733286 462497289 90744474 790169175 92327820 648721715 418195463 836644873 400915155 700106270 239654620 780615051 125454640 956412568 647710431 995597562 767688723 786481919 398159701 886346138 334171717 928540673 645789247 668566430 327764601 756595178 24418125 82572759 392292831 726645809 121044980 207105616 56696311 295533306 96366254 331278761 810760117 930536257 543062454 560790489 92765943 951171902 734027 352032909 651947905 755879735 310699885 510035526 280273498 776627772 86283799 301385665 263947528 386567647 111648186 758733269 277699056 832635080 18049879 927689820 348650025 468616706 949338646 968522860 286805208 477240025 506490623 536725214 837851974 993192164 253875940 725728694 209149534 858020815 273805640 984492572 267420759 878242461 85487560 519769795 84157416 174405548 618899369 734603963 175990735 696215802 12008503 180962621 671330538 806594457 201147439 655567273 427669542 931228468 593856262 908937736 571860043 760076682 81769440 372366743 178504513 720908657 188174092 264375519 520468828 911771166 465927293 561606590 500303568 736198807 116023874 786001660 246922193 457707168 128687169 799839190 36036600 527733706 486542516 715783411 374574431 673967982 109718405 595730980 515308438 650070968 728276948 990797763 95572790 769535490 317053812 995862182 192283793 640827414 734050356 952382615 150237931 890522585 322885898 443740646 74522692 757286388 388540144 615817554 304437638 916127015 555995584 688518081 184786667 266353350 381538946 463293372 157822302 927437373 559216046 714022862 265131103 899441462 562051247 838719307 457067223 676089846 42300735 590618159 326808090 833841234 869109699 972845098 409017109 881627271 239713202 823837548 421808038 576477842 616783507 767155705 158295262 751114753 399089925 677960290 633108712 738564715 563959580 930937517 571513576 663647480 750268722 865560681 300405532 488307692 248199590 901902383 482505219 828707982 128723776 323258007 430928175 434654530 572281764 675866664 86226850 695922413 9230587 92599834 708799993 791582969 805800215 815647669 722777101 978951569 25135223 254912114 650438586 999646622 95966923 835957060 35855381 780156492 365943208 602980597 383264374 984467062 80786037 306020574 473919156 772956651 322291620 933252341 256042136 663272126 924782157 985796363 219155841 637866709 816513666 900037589 270947596 395236814 10951980 673748999 319400210 731843010 847465083 987409101 681014055 766488041 313544383 949155845 681663163 859582282 404281515 724076126 459382075 655467688 833343115 840722361 279797674 539975520 102816549 783703044 439700929 508740809 325125275 448628311 103311680 121043034 861679 733212058 754420474 817429556 104961489 759032523 138689503 986278266 43635332 288089450 42707183 938378378 341206880 418990033 330768495 507525166 109262450 238417860 257407181 440829260 450180502 868125283 601122016 645291893 381376637 670391075 763913372 954994241 172919963 245361955 38495744 913308695 348741691 745039525 238337721 480594711 468689855 700149882 465262533 628053928 798098936 916292053 223492247 904543490 200320556 862651488 223458450 441795814 646020446 816098238 13345153 761398625 543853534 796288159 28275014 533981782 329439075 633325583 305537257 351562042 928804336 980647298 698156324 966238850 10180958 822076538 679961342 871460938 709067443 795785260 5592649 420378043 244558758 694254749 279268249 479418546 791103568 971989884 434208209 669734663 325643550 354100513 89508923 758378035 150697880 323032664 314817105 904115453 94452572 769854409 304824353 391051593 174228213 514769346 678384593 875174249 183646335 331782618 103862900 823551659 361454880 975185055 100436939 630494969 120859564 367138807 221587333 331778536 640809202 734834513 107244663 371470860 173497636 319038799 138286042 651399688 167913885 263034530 255562264 423168470 752939 311963495 403090931 474372191 60146970 867850190 671020318 777069019 487332316 973844389 898884247 937506335 265569627 923306987 12878451 940460480 173034285 718678661 83324193 230792821 537661577 851147012 85472165 152332533 151231650 170112132 120685616 850407672 218858904 487145002 186177303 905606418 305083051 720046615 217813406 596752931 150161791 314124677 328810728 385829235 345573131 823825140 616114689 676317662 442509956 780477796 129372697 464926094 126144031 925077143 320771916 471537346 395139910 725684178 688208264 694349229 816135275 870299775 624742978 926681555 115560758 749673918 316376330 967722766 237398561 383941533 171830220 772269875 803785131 991904552 565770724 623824066 373238376 556576350 6385206 923536146 244304112 530165179 782192820 947129639 512020361 598344090 210458409 237096013 177031971 879292026 50518167 191577370 495372097 993124424 259035565 665825684 619992347 722341341 425651974 469034504 501852552 505548758 397596883 860627744 17353331 577955812 12411524 232085277 304322858 803727266 149557081 470582246 213430901 654545393 337358443 600641613 450933763 500982049 441885389 508913445 556092147 896095307 628156673 717342603 399283805 743180786 546253420 628974521 174995332 200004535 349376941 478769493 415121338 914031552 115454292 571225009 446145533 784617487 211983347 472188636 121277737 426155607 582455976 865239122 224631806 336180947 616477062 725387567 174379621 786201820 119502587 277306743 533107451 945487310 574889468 831228673 543248171 843118994 488039792 662646086 24780888 300616839 389040030 534329635 567872885 612278624 449749281 521405694 15396602 778846450 539633060 636021258 168023862 700672234 32656159 848328449 291631584 670009913 645419343 734080440 551797176 628809108 484899006 740346411 888826792 903385554 337983975 848552558 212082660 516157565 710829271 927783234 216493739 426043872 375278664 643604404 288886757 701903837 50281949 221842805 96747270 383169561 110458178 928815447 333692061 456412004 32154831 254902129 53828294 928923256 255741422 733018328 315178571 978163712 885527216 981292104 110962819 397537808 533988037 645456670 701157347 968932841 611191652 714472245 69077897 648676940 95886329 596652398 671095843 978135679 22901519 750040865 388119427 433059223 411023569 688427979 324976494 552343678 527783290 947377562 428023509 686985508 387017334 890246217 217226097 236073042 56968415 204382801 110358132 502270352 713220272 794437155 203701582 394192333 663602904 781457698 267492413 681490160 390119634 519626905 91857571 267007489 179943585 964638593 189460471 641443336 945728222 973523861 348951783 491164146 397157404 965692121 267909681 736708632 397454797 777102335 511239831 590411331 385067163 960857378 31776246 961762473 413243617 751374083 193024008 981288407 751211781 982241251 158281119 438131131 829589605 984374161 228686997 941028959 489077042 497538626 891859468 963600354 170409918 368628350 872688046 955756907 35364561 267343374 167840175 487997035 199011920 536872219 245074827 528932573 389146009 664190027 697978376 900287934 216637980 637437214 48322753 188344837 344728907 499956036 514854082 985652481 441485630 541895454 592211636 953683926 171168012 597441979 256508564 470813142 217867403 232823684 356574538 840919747 78846632 219777161 229065147 729388976 337643247 928154749 122785000 217654751 572006174 692780691 332666111 861429390 640039870 891045717 333134171 356869655 542846230 634056670 484313448 688990670 249490153 889362551 137871862 406391980 495091975 533087780 88581820 744485634 792810192 804802795 327660159 816740389 354399157 667366969 230991322 590582503 810079645 910554473 18427696 440284703 41938636 94392501 113885219 783029489 135995258 589446024 444141808 799037241 114640551 469617660 238709843 299460137 746543916 813566646 297807011 382377540 156424318 878211551 735840008 907864409 96300118 986574037 366137356 935694446 437041697 930420102 296726025 866812237 743329775 934986073 309571098 792516298 300970540 722032440 1654651 683378350 425615953 651896288 433702869 915465206 297955972 714221171 217522702 570419666 39239150 621392630 635766290 985316862 404377895 996121423 167082502 904633954 55740168 632938831 8238540 95477217 764872542 926546734 92068147 663882957 149429808 501424008 528646826 603713645 600261197 979135538 285612225 608787825 232179073 810236175 584997354 996793357 821975251 955356986 462989667 934196596 828577 794097658 823584891 891209310 248937941 889242747 209889123 660150903 363750430 576089887 594196211 877266779 241018312 454495962 591504284 922131152 605387193 995067448 45408220 368224537 163274121 324725960 732884852 737176452 141638959 407934747 371757183 882528568 266488755 564046723 615268404 998538426 91838371 881762433 22458572 68282090 481565496 625196815 72279732 169211453 93987401 359990131 508374928 898744809 246163854 708031989 118326075 630734085 111332360 980961641 281060218 906689424 123888029 156223718 199087210 964058179 643208730 852749825 269161045 707537214 4796964 725916780 215429932 215544742 229774323 375746867 566192020 891528698 258328276 495101337 280739091 886374370 164063732 800023802 255770564 883681349 448970271 638448754 255407083 804173126 396169044 943278980 347024973 439289381 483287745 830202309 719368894 796481427 6320567 206980443 145094710 914912224 297853045 948783221 205685495 558826234 224946783 255763987 299413308 324093977 55280445 956461372 591337713 613730978 171429729 562707796 35716837 399162960 175359926 678448519 136644169 747973251 523241690 865268684 231648338 558370720 313310845 513862778 194294324 455970851 49926425 698547937 34758198 151425495 172491107 520851719 147691921 835375098 197789384 800795930 267672087 586111052 148167081 986409713 330613060 784238849 173903603 972751546 30653127 896011483 220816473 615376960 402000813 581735456 564273357 996484422 520216323 897497457 794628808 882351016 219800561 479329042 265436844 883835882 892690313 917561926 680218834 720500993 252874903 350531604 522863254 546122278 81388258 164259678 601343731 665986910 290521663 495935323 282610067 995309229 147127459 913577425 668423913 760930180 120794817 131593477 159317868 635163133 177691568 644325763 118680272 220881875 134175336 377171908 108430500 555030588 796289267 798321364 23565178 167035503 383430736 998134575 472818514 503278492 402081027 628747453 183479454 333896940 216778858 605664379 199956241 449323337 787005161 846913610 257544474 633878804 351822954 953773133 121793790 439258584 221882785 304411063 639091193 853554959 88806729 950271125 15995051 771039954 527029008 540568512 328205322 804491349 677334739 760948848 94514974 121323332 75197011 725942137 456772590 506948540 121556097 179362977 86821596 547660484 191203105 306536924 156331919 909677465 410862506 694330611 430797204 514341409 416046480 711728082 772790006 823451557 587515641 668295783 379575093 504495864 306759701 534922023 106232167 600306948 400704228 745841587 253435961 334664818 231703742 853906603 402075714 858910418 254678936 741521620 727087833 991504467 205097176 830714703 327755403 756302546 203981450 639604773 99476210 128390511 82153685 651295842 165344115 582771817 568823424 750439257 251337219 353938182 71749325 435857972 535823856 873762163 53157952 448995125 56813935 884416792 639615815 766256056 375158342 697428863 454336295 660957970 442923725 947912400 265258711 534528661 87580629 914360665 142803504 688911923 584920465 604126591 268960520 859814219 186008411 749039318 573072316 947872905 437172654 865871698 41946686 740412126 524126570 900625857 274796882 754824414 314550777 878508093 840804885 844322352 303583436 842515167 793819369 994942280 555446935 853727863 313386777 716897816 230358032 446002955 265481214 334247798 255696282 319106946 142139919 804655141 144627692 678097275 377986514 429052524 95789790 527750370 244174781 289893648 102747909 353861273 683769168 791972080 287499195 366454493 675174115 880708934 485403523 872491941 539232692 935950709 457357381 608105135 42968452 859042413 138224565 433451449 517202103 881867929 200473879 409201912 142364108 792565542 555541874 937320275 170971930 714943437 514554367 941900501 541520773 817537911 274052007 368131630 253895393 408500709 820724013 906064301 674868802 848177162 90983145 958884538 70744856 464059184 445836369 867836603 150380431 977239316 190981073 548386074 269604621 647229183 149475640 324048074 18246485 166269949 619144933 886385045 772493126 902654284 81315408 441996538 460674360 629383455 273497132 769071885 331937189 866440488 164973019 312640633 61814555 622786676 253883770 934569417 71392702 786240688 627213598 714175153 208691845 844231899 748986037 863918975 799353528 972422789 725261219 997632456 406489024 734877414 184027514 484004850 450709309 460800836 52905610 549564469 145474265 551699055 274289956 570183566 163723191 406855796 210937233 404935449 31980731 651873767 111926338 263094009 181374055 331917828 369268445 975043956 310646732 400492262 350857990 867504728 134625660 647939839 103790955 984875740 298323457 449420081 156680084 451462996 616046421 967303468 821469317 980826758 130016405 408977820 118093580 378221117 7920348 764741669 220075484 515056591 281339271 432690788 272184661 910477727 267852638 301438018 28816926 429768553 123686087 544590314 614561415 800295516 376125953 854145216 25760949 697688718 455931167 507324166 508436134 667109651 76819943 391339735 874575428 983423696 859417913 943768649 188509260 886430285 81325213 761319053 324462629 488427869 715419055 838068335 667773441 746492697 413028046 454765731 299409336 556515756 898336038 961926249 186757024 910778750 642013720 935319596 403284020 734806503 648490682 861977918 658855490 801746235 259030383 720412699 301090938 639582632 433820510 806590499 76043781 396049333 192433052 907322798 54976903 865282175 230600111 610451138 689777058 821295868 91059445 807507071 41432266 402785810 465066047 496057321 289620128 801218534 13489208 33855178 145968832 431773458 51041913 55702322 170543645 571356435 116977568 975353541 352572675 868770845 408656541 609556021 318371519 722573716 195765406 345876805 480413455 628611321 827731170 876873924 217024115 991839455 276812384 810738208 392800269 612477559 211862694 983932776 496989730 831946402 522265398 926519477 250570692 416741894 412896036 466118806 102772501 186034283 504413862 881130224 199737055 575872263 359337336 531211472 86264699 340357264 22650074 856905841 161695199 846195951 151731737 761686930 321597709 621773835 397822476 512424513 46449691 486381053 213784131 248443924 39285305 190855199 469849324 499603056 539418437 632219714 539511167 647767348 514901437 726263848 208595574 515459366 390571194 655762140 328563420 616180116 777671937 979414111 147760389 245917589 60505706 957519336 61078828 298766253 2171758 330820676 73246503 428462948 437116672 921289288 69209313 830973132 259974603 910961858 444232411 759132981 49565842 504689828 684214095 793877813 827118662 984240153 280018317 919755066 649179445 763356275 641563773 672874309 638573919 832805802 287299546 949865535 751237917 828056772 94905998 717108980 37913356 655388924 344923010 890113527 338653176 869034888 667058523 834397615 471408750 501872408 114030617 816778883 886202817 968769890 245832452 598752717 307493795 769392371 168412499 318198747 178120242 279039538 233259351 505100281 136178477 798826377 763781118 792486035 133055152 157630346 617611829 793710295 129070943 783301897 222236269 716876902 243625241 306876135 1280017 578684207 239283821 590214149 280913726 402049177 391187216 798225666 197972797 449276728 575905791 760336020 68033148 768718119 250642193 518329871 384451870 868506200 154134136 829387781 312600929 720761292 128623548 954859632 241953736 761942329 326495224 711420415 282905645 736017950 111059464 607594726 625840068 807646624 244626935 318412202 130267384 584230679 807514221 847747537 189392897 747750271 632051578 791600315 80669971 793817413 297307275 843166610 835822825 878113614 59775317 958923329 218509409 429982783 582272196 820489288 458509297 578474029 366277551 401824080 164353325 974185864 14878130 336868523 117350156 327944708 147001233 939543901 548776155 687520677 306237151 977292751 509247968 949712195 5362467 95255511 935625935 977276331 6274263 362417084 299259436 782375121 87067717 870706405 365807213 952877239 43595064 115004753 272139622 487124480 358685686 923754354 25223270 169903914 200592259 728952839 211463069 252226399 354844853 524238448 125270507 935827523 76795024 845652805 238082432 250903680 648546359 713530208 187909283 603030706 627312767 833854993 296231374 320178678 291100187 414178461 271287113 579984608 470602803 957725277 600325322 701457071 726394470 917164150 130026552 463718158 658848788 972185982 856625609 924573896 873780226 950092305 85599461 322448309 26038966 311058831 145539149 374366749 215131536 359705479 67497787 942259828 408734551 444236962 225678604 631947784 277785492 516786070 788222223 853726283 678981782 959265896 109852730 420997172 340438203 454697143 596050414 619355114 723498217 809239520 601591069 989692414 67735712 300942601 91249485 112785885 619975713 801057390 719477538 794721990 267494888 816387895 184934313 220400778 394906534 543888979 16877998 643654785 218750666 771364256 329997177 464127029 383024693 696354090 549505454 860707742 811796490 968431475 78934762 347075171 316188849 729404997 48603267 105302899 151115394 175226408 134385521 146067966 757343982 794359120 339860267 885020387 165529496 387627159 509054601 968761013 464248797 633457290 637635943 692403002 392095303 934271166 144768622 293609161 450413498 690639395 233298640 931557892 39534384 735960389 477063206 912617605 102311676 548015910 213833348 313474733 318426620 960962444 425231580 578724321 101762051 110493297 463315662 717314519 64273490 562637053 14859794 384640199 786475757 875792570 117031187 269951729 173451544 971536744 106124063 128152011 90219749 378487293 512004535 839237090 48923642 537831848 320261136 657024506 584846795 905961614 165646300 827763308 714927 847422396 175824074 521471693 35279619 908060428 44353339 988130100 39182438 574903632 67878382 160890973 1304312 40093341 301358340 484055039 63030519 298031557 621176354 781604131 632236577 886714911 670185045 743723475 67794714 236998199 145689138 402212707 287242848 499591979 80138631 824860392 456608538 779952558 548011688 562714089 149235860 680842860 460059263 463343307 671264677 792272966 215364597 979430090 593458198 987447729 537775835 882267625 452050119 587561952 109708164 163900363 131923181 337098125 84599465 120508883 434875138 943043189 569198813 669680010 275095047 947277858 254031309 763542380 159652829 660841322 190140108 681818340 534267897 943635452 421461519 496638279 28807139 265497976 334556026 349215004 168724954 425254932 122994431 204188475 710343957 729010908 408656684 773039615 14230111 773808450 801808066 823655856 527502311 550944444 232167378 578337921 33774391 148037380 300505714 644828050 165849802 422586144 75770743 977388755 175091480 446471946 407830250 793182151 715268962 789119953 117848405 977233267 402138723 755242908 70931064 401918939 932310241 967565327 615936885 920574073 576498451 881718766 292385419 972449779 58894584 764278728 303597678 472110099 268022195 456699548 145096224 338638174 150751190 234495803 245845463 282470567 503854100 583915317 182931637 560364295 740603371 863618549 34604459 58235980 669801160 916263678 286768879 491225524 66323297 933812890 701265456 853352347 21030907 473794327 754305457 761518173 258298903 784177511 395677097 616386806 433531224 486724198 19667946 440594457 41808127 362637172 72695 376223902 466079337 718833180 80918012 745422637 147950159 402092322 537724737 698376153 544450140 605152480 431258679 711292107 293039608 294300576 753200743 907423027 137667286 174509838 6005417 181902122 743402660 954345956 780518775 944880059 89059053 93306504 232060412 878073640 131499293 156610299 505185529 724963418 5832298 784686442 269441524 468211531 79124838 960417310 252900840 281196276 456750722 521184369 95447315 966900223 517637002 626048502 186693626 506012840 48878936 440390394 472172637 808982078 100223092 894776938 218250233 226772770 405254639 630829979 77032938 507942190 492655046 738972437 133609305 465429374 887472835 967829898 200656562 984806600 27099189 41298523 809230664 938667480 379486923 429555462 659541 997990726 100401801 543471411 112624730 722422574 47698148 793277540 78417477 162813522 607880738 891366527 594399455 630347702 419551461 699627921 54124087 787187084 414456721 593346896 127169380 994314921 849307984 856388403 865478103 974453968 21773647 483731574 545563539 666039714 386516498 728810818 50360499 944907536 99995062 942560339 385567884 829401444 521355721 579360820 484314782 703378418 292602633 596823040 178591311 659838394 326735400 473566280 1208136 244275068 619893863 728365563 465967805 563430493 910480919 976964395 138854918 883754152 112344234 641149929 63710086 640131104 857682867 936804803 46965081 597366004 751968043 834646270 310760909 678160087 172795325 274675413 54608612 820881904 101049425 704782173 544870501 915393321 130823763 703597148 21333569 456433517 374921035 610588728 28867268 492514335 189210710 741538613 178191523 790909339 432090600 931135975 60589507 818894116 239067228 753467817 572242191 982279819 5720469 77905675 301156255 571053053 523358791 631544612 626966861 640838954 259100012 749767402 367383538 769047468 275418621 513231436 733571241 994803020 782323031 970444687 39905096 580315348 607905564 842256487 287523414 336705707 68261483 622476340 403411526 431228947 720657822 988052124 142754681 632441559 145223767 853853903 458502037 763115610 29152940 859175764 93141173 411381588 348946082 660422475 96840838 584357011 109809450 624397621 309539696 556479642 133442630 898295731 423326369 811404885 164665179 171162344 399648218 649375978 343702455 726584489 109907714 417583063 63999505 502594612 131976122 544921266 164510502 775485265 36631740 197103283 815249162 981072972 377237715 940235656 89409904 632877340 451206485 600715018 415971427 668210480 434948158 954573179 399321794 912287132 624273857 929098361 83310230 220911583 328053999 502882176 395391347 516265885 12981250 484752709 101461817 495056888 32805100 729352340 482499406 914927931 118536607 191740586 734583267 790302779 33109601 367395630 42589684 532787857 817232575 854268534 283940919 495099164 1276072 525045054 488430422 512744724 110124343 973161717 144222204 208577636 706239317 923296270 445308175 911147317 698462394 700438107 200099807 449682080 317405186 856444756 262695697 399938102 626786208 801681551 230770086 846681768 778238827 899188451 366309526 995034398 532496692 701448813 611863254 696456128 660344045 852357817 217121613 892894978 595684009 989418572 44310691 565131769 65244124 847563065 619468693 859909710 653158682 983317541 836628027 888433949 213675280 434147803 27851400 786970181 291080637 991891206 189505936 768956091 120300479 777023828 318644922 474910456 448612037 475879026 353919040 535927949 585493703 903564440 486845561 698102151 182280174 327874644 416552063 658550850 1847636 738004304 53022594 117157665 85254492 182870043 495126243 850893727 92614310 753065901 27723175 707677906 294047525 478509248 654258153 963509590 399542331 977365983 690154674 958119397 416050387 975147412 374045792 781176117 202240650 470486457 145920225 314654035 86125360 543379572 829141705 940820072 4285998 714314528 654085963 689954598 129671331 174486215 82490330 305615313 299441184 356101435 618667472 873760874 340161709 389282910 2971745 602843531 190006187 272772853 120429362 498668949 622635092 849203051 161262834 426596291 305938861 814469945 861894609 957116064 54097646 168094682 360583550 877977213 300604750 398651541 85818114 421989334 101584235 399794828 85942289 565690956 349390788 851266858 862822761 952224742 545381889 745736256 301011328 640370447 379055381 866280498 82432058 243976238 4921047 17238125 180002833 906078461 502099536 521730353 143499268 746969554 326512021 944694540 785004892 925089730 275043003 374740055 709777045 985062696 706355332 840914840 368184275 936304286 54864791 770278372 570259808 806865868 242810111 386123041 232862130 387028732 13023351 113587068 126186008 526699723 287836394 366206089 238906400 860163133 597266918 732912834 58209255 104992066 299183033 532444683 13762375 971217187 113657798 169507351 239066775 717100766 281105075 711282915 227464304 512381973 61385331 437354273 828189088 915765503 339163598 879604482 256787984 394607360 301084193 828624718 739399093 838686821 245533698 552524977 248464452 261054596 75879291 509482255 769780812 990395068 24425335 847220829 27746277 241029934 636150667 972462002 120281181 489822180 166764492 479750768 589035010 824388660 870119991 908881313 2396979 921759970 407945468 675899968 35419175 831054661 375101146 863333954 153552517 352201356 17503218 546618074 607496377 762313963 309649262 700747401 94716163 351999077 367115148 804585403 382327372 712312529 544432374 918430439 140741697 965236106 252697052 943105994 305976832 687836249 132780806 167256639 212090166 602650914 209850081 244143402 38488509 757373092 445081364 514051654 365501837 507544803 424256704 869773473 1828082 328884755 437642653 953144757 528268922 845308657 145535176 573734231 34666206 847154905 117619044 541266658 371511628 522748480 911886080 924085267 55316065 578731187 518786510 856865511 32370000 864916710 604252148 764010003 233080092 721530958 833611004 968011170 167782848 637740708 406419233 449530247 122292736 892989459 205274214 778439219 214970461 652923412 883296915 990980298 132973851 705656685 251526241 361841647 554867447 873101151 285617634 297105890 87458042 876222520 656234758 904843127 183052942 683922386 57434685 843823969 74758489 797405353 103623853 253968945 251871570 776090849 58468034 471739649 459073852 608086607 385483552 980125042 65137476 756627163 410599577 830175520 502622611 672410800 208668288 468183543 687627038 840113398 256421683 403804662 342708511 489233318 671386298 722087654 532574814 687240527 662552705 962937258 270759788 704528653 292758225 392430090 279294369 889394268 145140928 851920451 538923645 655328310 127488275 909885233 423099587 750524803 207045243 466250526 26445684 755262129 10496078 847300826 345695497 424752187 95284178 179619236 623266534 922317888 465926221 546813147 111578048 764133245 173457141 824453376 417980947 885093088 406961148 852097476 655007944 931156310 430735218 990908425 237522092 747645263 343931759 833291962 294101214 560974492 318553472 896601588 163911818 216767010 364632955 850450979 125142087 178227963 297311978 712519749 487937561 587882022 9311278 830398558 946535463 951905893 582751741 602084005 230614388 525540615 208858165 683669429 471990537 889977252 591244711 993949173 344031007 799793156 358528506 895886918 662842246 867435723 490604952 659439183 332003779 488072214 391070237 795562850 71663316 999903912 894553048 935390727 520143775 997262791 41953867 908654459 766758643 863647548 918553348 960833699 200466414 770134074 403356236 631023628 195684874 505354728 149520897 344123917 35802671 422960459 457039162 900448486 254078924 802027639 124547200 719798889 428233809 579450229 278891457 783050261 89852729 432997374 319344884 475580287 166404060 586945639 938292185 990587154 80103140 839182848 314068112 839976656 254530980 337535462 688093355 765809279 458528300 963954337 72459015 885417766 256250119 261363456 716955677 732579170 632844650 646752780 876057132 974484069 98185068 637830895 562104277 858030514 36919927 627153159 64555599 898492756 16615054 570545081 189632291 957803049 370497463 412926792 6539948 859776957 432732888 787721911 174870106 573177111 244219151 578695371 248439087 530379382 15535728 485705375 253535330 709916051 151728958 415093781 565584554 643018704 233471378 285044449 115948457 829881753 105307233 629002082 189422570 337667091 70419443 667621106 34981875 742962317 480347666 752767970 523208859 977931752 241697886 352291310 353369303 708265674 589869578 664829566 209284251 525247907 420409512 743530350 110225987 346046880 196258502 938466290 853059512 926059154 195710892 303749923 173918041 470802858 90132525 413768375 508083710 657154362 15644949 583472277 14942099 596534454 730259975 783394974 199926852 973042200 396877599 998581324 76131260 803528085 209187681 517371372 408669510 803142635 210823056 348117713 404915260 964540036 82009160 882523116 564566218 797019815 269834732 314817440 625214649 784765683 122965655 229122180 44537030 197646670 548731636 999935595 114214540 486760821 532331863 684569271 212490199 425518835 341096328 967694240 382904992 689438129 260735382 604530950 439283555 907536644 331461752 731314210 262290795 966592725 198924382 594704667 723473734 974456082 134702677 247940698 332342289 684655838 289881781 958105305 258229064 986560441 397884922 938403756 446597775 805666663 164932824 594467952 745664639 880264949 469401086 817978122 67350850 117323142 73559375 832731593 202271289 733734712 254720585 385071953 499820263 726826672 476014623 654207874 237797298 286766271 544941948 569881651 228491886 895779084 842699420 988910325 247596798 252566581 404689637 747081243 657536240 727312453 316788768 949332862 526621590 734621680 52252133 524826668 882814446 932769095 581154117 728327343 683349552 764886624 247853038 424732303 345208697 617593561 903295822 947199183 238416306 360905123 547991205 795693685 221270078 594119942 619128800 887524635 395953667 588906254 712210794 975714047 201632830 447509564 732551157 836068235 112126023 457727592 167540592 661036990 767493961 905575985 536803715 659676049 303598442 945283936 484073274 970740890 334278263 348929780 131196965 507562533 668747635 918089639 682456941 905272912 573326273 891719746 332367602 592764728 277122591 585421128 183416202 784001119 329056810 916386641 486087088 564393226 818453532 857129210 830458099 967207246 304651236 939850027 630050362 687381690 523463213 940884223 376971617 938250157 304713006 440959674 45223889 493846387 213547738 703028555 652969745 689481733 225541384 474851419 79065651 658801360 310046564 753313096 271136439 932617018 143539962 280845642 718356159 965725835 377088436 748213881 490095908 736429326 198656244 678745837 159499612 390443830 155109758 267516103 271562097 458402438 141428281 215855162 48941975 795626974 83291148 910000826 797382811 890175651 357106070 850218983 33242979 539895546 350376804 640195987 765205410 845115996 72162697 399869008 233842310 769876068 21015011 181968559 63285451 362225265 66112839 305842333 519463985 858288286 304518779 562491009 179860780 925754595 292872771 687945809 110530623 397761739 225628729 495501683 312743300 407299866 1116327 480026640 137102390 705239132 77547802 734157228 332022162 698248847 170550672 910347217 878005922 932959257 123859796 619099350 989893336 994500447 222124694 334184574 136914782 792906784 951742568 994899552 303434588 947417063 66993500 560593065 102838393 587545347 40995855 100392556 55981897 799009067 175411924 931445094 238993351 527424562 481086414 864081434 111599654 937840270 56976334 239496974 288714645 413867300 314776925 650042470 354140394 480941033 569481256 681315883 418260685 437635207 434334780 678912296 52410259 554373744 720238287 931288166 9790542 994771397 30704505 578392244 464137317 599183875 366402913 832916328 380631339 401309402 344712608 991280388 180907807 682462722 709193569 829929032 527392088 827633593 565590040 723404288 240961705 906741881 301409957 493111416 308752185 860916314 917508756 977558069 338587324 639467598 52007796 749523341 426748655 823172878 484675116 544390657 126176595 849728153 402269731 539420136 324200017 740304317 169636289 673592607 547611350 695926662 30700257 419588599 775147392 867177494 60914359 588638958 176917376 477961264 17170193 856676581 786217693 891509420 40897992 466938314 68605610 150428533 124327562 244407551 143864875 198924237 30773122 822890456 42519452 872225965 578537183 719208335 201316505 290201979 350609149 554049016 261326818 709474451 152289411 435140409 376090316 509285932 128265473 170588781 27658366 463751791 6521934 359490833 114393342 760670084 629424536 805480412 178823902 565000502 395465343 586128852 387146340 674935672 911231198 917969607 117401068 267056403 581747478 963199084 699312851 888120644 60189396 198228913 78685878 511827401 613353233 630304563 393557704 955632200 280175805 747702243 158246602 414834614 391898972 573131876 425204606 721652653 347492857 721777319 168249608 393321984 3408131 827520934 783330707 888198319 420890760 620586761 91561236 132484842 276883603 940418198 128939224 273969677 401579812 649205813 670399915 809383921 165989402 225858143 24425171 447611781 171395937 658958106 761877348 850878168 65834925 429130935 87964029 821669516 168603326 444217935 123600013 593793555 331978764 633582613 248556698 583487437 252460966 593895125 41282896 99759496 304931457 935860147 13835219 139350834 342118222 930898641 437080837 651845125 568748541 777404594 157178471 948339260 265333003 693765747 173319027 608277164 550954857 711922691 595004830 938048983 425766281 587210300 49224770 373275259 354163830 992850937 236657160 453730486 179039426 183259719 518778468 532667699 478307995 955747065 794880860 979114977 317774735 728861472 631406300 854136587 794570400 812788096 188157241 213883260 248858792 779572338 253078147 416333902 827429351 965250707 319613480 359235094 748564566 932019396 731309190 874216078 879476862 880313585 798331718 913296674 752958906 833020945 594274266 738863167 361184735 397955472 600647875 655673056 369063549 719415141 485603867 753540537 305926827 597013041 247735007 411139949 486156320 991941778 29282325 166383668 223015842 695619408 585387311 851865020 29987221 546043475 251840813 447275471 702289693 799854908 157516828 851105672 291060200 771984898 34876475 219496764 124051162 727668697 512763753 768656257 239984339 535511402 130571437 767667402 564617607 758621376 168996245 778997043 7529998 255084371 76217945 376876861 519421913 935104964 325047507 566714816 723699823 923582755 388160066 979185109 251053163 903284149 269702877 754964462 227230477 269536584 102408403 128850670 212044049 636366659 424082777 934021029 153884784 223275773 646824658 908938654 511492390 791059401 222243017 958566293 707143082 928341126 531845657 538794108 79097289 260103120 320235594 671127148 384662506 944076466 258316939 332800028 100418467 279066526 57610595 555429774 344137719 503189662 304698263 618449163 699028160 967131232 321918197 374824059 110403180 278437655 2728311 438081450 712340165 943535541 89929488 412482093 405918094 407094314 410899534 528805905 15232491 125454459 258610299 318362359 359724030 929543275 293060984 918085267 45530364 562263319 345946076 893938065 148493596 411482406 869936019 903765727 54498948 576656222 29807481 355209038 553122364 892895486 681831354 780012177 422574875 556443758 667991339 806352995 747167659 971096340 343332044 594178244 310121670 677957034 368073120 420846948 291767338 335651989 418710642 741911981 367798593 763964972 489924520 712979785 527777517 734058344 721400413 784044401 191581439 690917279 182615677 737231482 227897246 680466303 593865209 736587721 69089634 469178299 800511667 958845229 545398193 961722166 802226383 903205995 30026621 662008626 433754132 640325535 6469392 83429644 253437429 415139410 324661278 893208834 304709670 767080161 369333453 370171646 213546560 542743870 405673065 567836785 311598932 978506508 716476931 858053921 298607498 897048853 815143625 945529937 357749653 902830387 365908937 839331142 545352427 925904901 7465577 60541194 502824951 531740628 244407889 615745750 448119794 592088967 746437252 933391984 425847258 778628028 273310456 874112255 356181419 502565080 868837030 978243539 42673654 417484524 42427259 747703381 126966640 670514471 315653058 850950312 140126736 183287876 20763791 762340676 441854212 581964614 142152649 384541302 133749903 693453876 354177096 892780623 401290989 811669703 468071581 987633224 157672383 970310512 384726280 834566336 355183970 651851167 16975566 813315444 107568531 692881118 616488948 904935352 260625654 840897721 71168137 866918226 664222172 846563841 699693190 816865443 206306110 279329921 486856321 810397708 54931225 923249953 159701511 895526324 87222375 808730864 271091060 384030605 1635236 864753436 391291744 561711356 100230690 363077999 133569505 513152202 338770584 764087357 32177577 641625576 477003194 657540088 606488962 758253583 661140410 796866786 313911421 899039956 27040342 81849619 122347299 165955492 584594378 992180555 325252631 391709242 131936144 356184222 520251987 669500784 756571310 827873847 190819622 381090293 418485752 748890842 624833691 730971312 119633385 997866277 268354639 631374235 32204956 66491864 624053415 877321843 175646240 561280223 159667754 839412739 196877010 467588405 430457165 454299659 339221929 407949357 322879083 837493489 623074155 821849891 9083953 706741486 18743581 777261016 631758233 631772878 5996990 901416237 71229006 96628652 342219659 376745457 265232699 628357901 241969423 468348282 311284970 386395734 435182208 785125391 473061463 785502654 348390451 969287797 652085544 878114019 33470525 423246315 551729817 965926625 108050305 961563963 138528488 915359492 114325714 188821252 265011466 507599837 535667814 922535613 422033938 565273281 193545818 515767666 230336211 260407504 270680680 917510929 406402631 894383175 433266642 557442130 185320110 396768722 120885187 165790123 330935505 992056040 199976546 591482588 118804008 171717049 86660361 679286253 371615379 409525035 353826203 488443672 37730747 945521609 222749652 670318894 208841158 413046129 340757410 764042963 310020716 848788556 280606888 773772126 14249791 605462058 302395954 961012903 107300748 816975697 701570638 712801663 66314663 603221843 619951982 948172116 87247818 372056227 246761050 584334211 105730659 409364177 376794145 913953563 33189650 516699597 475117492 980944849 75653104 658938194 591064266 687131181 20098019 334942941 649799132 776953206 99026645 759990402 227896484 976157952 444710380 827894289 164380805 894347083 688112586 804760098 288836614 303350451 223860530 815098256 295524894 633401481 430882521 643342919 423068888 515495951 190805136 632512807 202716513 381370351 679266059 706955086 194752525 910065563 102703520 409596911 415991426 571908451 868708742 935222619 679873616 897508173 752778211 888032447 423973880 931706012 175554812 888186058 163507980 972122115 570389641 717418576 64113788 823052038 236583301 715776143 546986593 999277131 738331664 921859861 206499104 538509667 295100957 816918623 31673286 681167227 359922205 853569451 208815635 941201404 304952646 657456467 259402796 550180981 152170443 795044181 649929595 836059123 151095923 314398261 131135091 857027327 618441409 862963929 159105045 171904820 540470082 892316169 421312654 551553159 579796783 884552137 512387282 567585233 654311087 685939474 225729378 565253050 949474620 999169035 122767409 251131164 105633533 122248237 200224077 458351202 830466273 864812359 220908709 355111129 477316435 705446093 623850776 745081745 311139499 340950646 454260881 580977368 623667799 681850877 761770561 943869692 552525416 903563680 759011498 973452068 239222324 485657855 102419223 472870749 302872561 944530591 101663891 836893912 177258582 767738620 152224687 520103262 76654065 780768310 85389553 456182116 27448026 719620772 361939231 446027084 9732478 528356657 109171108 364785913 492208700 786399433 623906223 861886801 826173822 845251695 189118406 781084754 666224033 815954995 376558060 894950847 130395163 643965108 46266920 334921608 246909583 616088247 70531498 672003286 260649542 900704159 271073899 936585315 202031539 319350429 384160056 878310665 532032929 863151133 141938450 419189321 514870780 953814154 791652690 943811674 292626119 410881463 133932250 395190887 434065353 639263347 235776225 357109022 314140469 706563205 86360366 976464836 157821701 550798257 318989853 479606359 187657687 872475382 115906694 832973498 77555218 929535431 74204200 466352428 131776259 177364290 241221098 694532504 766549 278699498 695553498 775837844 364374849 394726868 30618462 722387931 2129050 896926428 688099789 883272738 339376764 746333866 45237797 197052262 384791204 933873681 553887787 644091104 566262135 820539880 62423902 891434343 32355249 210969293 71173676 204005204 40018421 799569607 48074500 455960067 66159582 205975562 527337081 683752729 362340637 528741603 378954748 509509449 379226902 849425390 560392250 835099334 843069636 940380335 19936846 565717089 114573519 721759029 144926411 876647096 140528954 853337090 80406692 893988801 43784445 75887568 399457112 447575031 514246151 716236475 245994581 496629094 493691814 635838677 325967250 580173472 588429005 750777142 560673 557225464 482539688 846538287 109637998 498981610 167625765 281387953 511246910 808458050 736474546 751531239 217273120 299070165 71045500 522446294 415835955 918144093 305080440 719820498 612786270 720505825 295247950 672451437 476285025 856784140 681617873 862789630 897319459 936930336 145482163 423502206 109962691 579881438 29721074 261876270 704422325 946990933 171569435 764886585 952885120 998832396 249144528 534600998 619215333 803174770 210062684 506088284 63929565 634066413 826356417 982199019 15262352 188200913 426449631 866682601 86969959 331914277 23946350 732679951 647466894 863492829 291479827 804996930 905140552 948326383 328132283 569154628 506459046 916107446 125752406 718551502 613519971 732848757 235729251 941446718 372934475 917419313 363905915 834955579 78255775 455974610 409375254 891768894 569929 390430827 132116554 837230908 549584347 549684800 262170957 423936678 10806595 910464690 79701730 346532808 648705433 794985980 284143657 633812278 504331153 920293039 426442140 463084276 406015863 976853646 155914265 264488445 20239327 912725180 339194368 410743694 224129140 224891823 524671947 541400019 880433596 941312507 267811044 955566499 755890501 814314806 118576411 305678875 115894051 350381880 666632081 981115727 12683404 664120241 360948944 380175594 468008763 914438446 358778011 465491569 497156206 822714642 726933416 968519433 105282996 683261080 29604845 986681397 468380648 925333755 306774172 933475860 475873918 604716731 417839552 581261658 457487327 585411534 109469739 174784069 535980518 572388511 221753656 913663699 267982406 291782060 418922857 565244881 575796390 666461562 419695656 943781573 453924768 837031981 116123731 446514129 323992901 970058614 377945106 913382087 502758434 693814575 304577542 395743534 71091550 874158447 29315844 69805420 42704581 502475654 628283995 844591198 260921471 950036137 381992809 616464225 615439757 725468905 483928702 579154091 118816240 413057344 662780313 979572036 113176783 476012806 657709934 714671050 77191402 281660608 481548881 792442662 40382150 757416640 302371657 475665750 253616977 692268816 411006459 885929557 263835211 616234574 520222794 787639552 714862160 807949142 411758748 511699773 30544937 289253841 606814451 619002069 651674114 952210932 415835033 912854217 514662039 968917679 373799483 687116294 220768649 647888486 182393329 553581438 58516127 71276049 544340143 683598574 42663474 454630396 201952114 982574564 355877335 590537482 283692671 877593498 841720435 880869024 661268719 963976789 71764587 896740179 224929140 338099140 818115967 970195659 98883850 333627741 77629749 263470584 92711851 759801383 462459749 967920341 66890737 417675795 608163479 890252943 211741176 215654716 367557954 638479851 98003038 540981381 474257533 616104038 699023216 754747849 342877144 350945256 505469178 938651920 87790388 378927782 357839528 625149142 87295862 136329723 528193079 803308792 729923906 748875289 251361189 390656019 583638299 613379968 383136762 721900076 472431754 779711157 114274425 401039558 222444064 642135964 200774872 729237646 636408644 774285037 473205253 621451467 84551209 303904466 824448708 935112934 33017500 126187129 45308737 297642595 73568558 304278503 354280232 613307472 737591552 784405193 409899479 989429710 63101066 983056737 135619602 875905003 507239152 778177103 83035692 744748224 703333782 817085186 149213788 426514899 197042247 520364919 206817421 793797126 482837882 633241129 11535504 318306848 21900125 390397971 77295157 332379198 117439548 136756676 565406697 728257799 436517490 932847763 82701094 389372109 10973988 704873867 209299845 285935701 20272825 712124197 122027835 394724477 41789887 548199360 148814027 588757546 39112806 511893623 465086945 821601971 50200448 877860741 165317321 999889710 152499229 525951764 541605466 683713064 407372542 679055944 496767514 673355186 306033504 333140522 192756708 337356461 308025324 480522536 2744511 805894838 950611000 951891597 513909977 976400799 82207429 384922061 160088290 541878126 379856124 463341350 46560917 300657210 158341585 864629265 206631784 840988588 317741448 889387130 284186224 653293619 142078657 466172942 292082146 607488717 196241038 877525043 335211488 355777781 407395464 635754599 514390161 575828988 209526619 249849915 113630179 491002827 435230085 611343739 679760129 746447248 121412914 896080763 230039986 763616407 215047725 620312255 576275047 853668080 500133658 666454530 45477581 792384782 291714428 849552208 624091328 765461933 252907941 414807616 343982719 924138393 182416468 937668466 566771604 839567924 526752203 743374121 406068197 895800714 499450911 852999538 103471660 180935865 437507904 761523192 379993604 461456128 108952227 585091679 437034968 854188596 785672353 862470059 97909067 582163679 349188674 563584691 56150556 444100544 133809193 864721101 470238910 839346885 285026550 600368670 613529493 807696074 420571450 535887594 711384193 957117655 506993473 951051954 33040571 731638135 380919645 477305513 279504293 381831109 455971661 761830720 31343657 368468650 67139420 429274353 139429278 194815462 558710947 898939620 494377600 742192102 648260284 874539081 103384354 924801959 197269724 926535056 102775533 773611037 319547305 798972955 444111899 758204986 410658620 654139613 524552205 765404995 692370884 701859857 243770178 778858741 267395315 902363275 914696357 959017165 88934014 859327381 87237143 283814871 346814406 937167442 580537209 871646294 488396137 572514451 455694831 516894705 8586028 618237368 281730063 402420580 780552676 963265429 270808463 830628722 16651762 429716042 124049735 540245454 179737144 406875414 362230009 993469712 158785606 692703920 605854636 896510446 233616179 564156141 338674355 406123531 534951716 824833937 504070617 735987453 251401227 476813234 194128830 861615748 2064809 530864921 459124025 465486787 80284624 260756127 323688112 939803089 224140461 825620678 565492142 623144824 190036288 731193313 83401596 297132074 236956219 350199290 138729158 761416642 824727019 972222491 61638398 527471350 321754068 415087376 157644965 875408534 107152643 775149961 239262663 539173046 86636377 546359522 476772706 833113245 8516001 635091331 16330622 754913475 473165196 525224104 266409172 906679297 324975198 624975045 253538277 384144404 26693317 117225595 317646070 424378372 298262419 964042121 524575278 674829944 87406196 374281809 539114045 743083048 184333954 709415754 171768909 413649314 445263896 902877561 639238792 811667157 290953818 332275848 188277966 538552835 87889403 593208421 232504311 796594595 788011668 918015464 242662488 545309782 762905377 882587805 785457735 995615585 142888785 289269101 109906689 456059170 173712564 554849368 136793197 810386542 579268139 600709730 485479922 753168033 5752432 166924200 220716241 662626846 134441641 207984954 628216217 761435855 572600733 983954535 393920223 954081224 135717435 547214537 296046165 607766527 315718020 625882434 373357579 529192093 631152632 944731169 516455924 988402350 532438675 675848953 258549792 294179546 248582072 439910249 102491369 931887146 44627436 274020961 340001714 758100238 241551817 698389250 533500664 802250208 63099936 231527079 236212460 752578910 695462356 749945173 548936503 976066559 569714570 993875961 31580233 307193806 321002458 848677215 186521647 484178097 636554603 727040716 503114372 713856696 742272500 846767589 269022760 329466851 167236686 661770505 262191229 949943915 133288143 253218285 718719178 745798969 522194692 928537521 412357762 902869108 490185952 555578395 166325552 545017669 147465401 766348227 58376040 926810591 674341429 905948017 70772534 721102799 503471996 850285552 169554233 192315257 103897436 944223331 39963371 734817016 317804565 823981024 222804121 663331448 12818828 769777781 72955037 187843785 559101179 945529091 238707347 811954454 219136544 964400842 170941809 432688000 139185177 143888505 386873285 693582781 238388960 514492653 97614164 287906858 158443769 536624707 27480467 306837463 729794811 956720981 138849880 697100962 429595336 817914869 113550024 714341124 237498434 754530572 395061247 923148502 52667201 764627337 756578474 891457648 155155682 678689998 57544622 847001201 193810131 787131422 393030279 787458339 348773731 763112958 789645090 984494832 5693570 595440170 397898052 663956557 111784401 981133612 115862181 747664765 54653634 260326746 212252603 323833971 221852192 649281090 92631416 183881364 703839 115730367 187972352 485023814 728944485 868950478 369607838 918240663 494711261 504059105 46817080 320189075 255365509 513920458 668001158 773799269 571633244 818505867 251200976 951455737 337325584 719347242 378257369 677584034 406951375 756103479 299716896 353561167 303210188 818301538 722034351 757631275 534670061 872341407 637521029 685113593 300597861 701213986 821860594 937140628 103570178 686978129 228505911 597494633 608784285 823143540 224826079 963653750 8357787 958794962 22512613 588827196 497509630 616100675 203321168 943147588 235558759 902315987 14195294 185677511 407263869 669298567 448432668 685730925 386320443 928513815 376325612 443814550 670938962 941613488 216571604 429082220 453682909 742001145 402022319 944485979 193050389 281820921 19653733 227376176 262327164 719710491 124081480 219127670 795885899 883094324 833788955 928407080 16252463 89599568 223924785 658903090 443735442 571042033 505096038 811101461 319393373 753028224 618611978 954971946 649695836 701014287 17856341 923666958 232596169 236396402 286779586 543947173 227419967 257721410 575511442 631340374 255722955 862954413 64240979 478522249 278715377 678627272 39386906 479078340 293020472 314101742 633419850 939288353 380445604 545263446 15454074 441042084 585431968 950967546 385485985 614944187 205389715 362592858 685298780 992338063 682741673 917448716 583379353 835639155 28303998 298745181 20206036 474264199 72086868 267540659 79361537 466736126 493943400 706002077 250216780 884066923 290428365 420964532 1197991 533011370 233468723 455628852 595627714 895515785 292096028 649322104 872422957 936231149 779305185 867847081 33946296 967898871 340076465 689196822 613099597 852074415 259792155 752237914 785822723 882574670 187447695 491112345 651527836 801231341 220802683 843551801 461977540 466766858 245296131 801814091 722611851 825959241 367230867 935356742 30924986 394773623 294655011 442611012 95448408 520013302 245340536 332064205 253041268 889749267 402471459 965439631 211402249 980493359 608295492 646112609 253373453 354945775 524340023 972810574 250551037 258573702 534511976 744758003 70648574 616671484 226191632 782063690 675131253 896690529 339192382 803555381 125821965 837225578 100122791 608302165 846213653 938623783 344958574 429407478 6423217 767754468 712258680 917830360 363816264 533256169 809011819 956253563 235403190 409968284 322917709 767992759 125279200 778819187 327982019 378938220 408343863 747357167 141480105 221410915 730413986 905638841 202773227 668498379 324877928 853109975 215453604 495421651 499533512 678819457 365991247 534993863 491767625 745238643 352186057 494650617 563825498 856168830 57345285 410565747 642773207 720000811 105048354 124684497 151090219 814409594 262368909 410090715 173385552 685759968 91696538 982590357 470897529 838761615 697040579 786147621 60622410 310265401 114442706 955894039 6005854 622894124 136125667 662687616 212226258 466586508 13526016 837969243 289194557 708470047 101764144 702682280 769932871 787338121 706704925 716125469 486882650 822065958 90325747 107090846 587913825 663047514 227262980 738361834 354772353 753881928 821630198 948975035 283528668 567516671 210098837 837105575 111863896 139525023 444330291 845054615 252414576 460407227 959466246 990691025 494521294 797020975 347630185 417058289 391822168 746467442 310110354 777187017 44783296 677620980 45087912 92728528 638721461 997034795 338197461 674776828 613651293 765221226 221859112 434245181 105392824 994376111 466954730 636244071 457131775 611734532 394865687 598189042 12290853 951362573 644071424 881103681 192253088 789110787 227444588 661444975 503297146 631239947 294035676 354635796 17042892 150386774 167314136 386395792 426632943 440407690 547919025 909287817 13432914 753765593 194374654 387231459 113033406 318194820 174538104 669726052 120621458 295693132 80136599 968944800 245398340 420188278 273658578 686665764 79017453 578022515 476630491 724817298 358447140 652988821 581228700 986226765 500171551 764836433 557337198 736808990 45712532 864361098 39709583 693736832 8095340 369200025 124164475 575953137 643439449 938047602 154567666 993767271 336525287 510517043 652600537 986846264 364574315 649609973 169952023 302212922 263100251 877650048 15003350 394513952 191675399 794043930 272822210 511297144 186774201 953438817 489452575 916397601 128905187 410731561 34025212 430580105 717034283 727709357 201218007 456799011 497144057 938185320 151080011 489767970 300179512 605698210 404502672 759710199 565048658 749920036 736972959 966927400 626443744 987159614 734185231 790812355 298264332 537170834 673548192 804794256 45313604 259770005 513920677 830773632 143578072 478989114 415499029 714650014 168195662 915129806 137375593 905270449 474876582 789551439 312127664 731606981 242514200 737174649 599488787 692094295 630517529 651348656 78795634 207682717 174107758 448224584 656012127 961096898 58176107 371737376 104427229 770144528 637648812 922644409 254842478 719800286 12903188 694765229 75853067 731120290 259787745 827756012 174108756 589344340 151678494 767601939 115689348 771105936 187660146 891315155 402481767 421166355 129027138 157962878 219369197 436739880 95834726 573984714 88425599 952088972 412888046 917947259 289542 423307043 481677792 482035802 9956289 516005868 124144678 279426031 318109882 821436269 267989067 866953656 357768462 612494035 667311262 868553973 640709853 915036660 92691321 913088867 909084899 969620267 401585236 585767469 203717120 403464441 251371892 494926929 367979500 536246137 291402783 700491990 484156466 965392559 123337817 779501137 779785954 894719409 375372879 625868557 253644120 513836424 234031815 260920349 560811260 983578978 645793612 741524460 613414768 743241822 92886430 410106605 841830598 933398185 246066062 714845206 699221738 747100378 759919568 770421466 381419058 628316883 836839150 842917059 542572456 583703105 340198409 821660827 280832728 389087025 109301467 352620937 222691325 553311569 278231074 907424857 4266005 143994006 149680989 782183836 344852005 899710091 362324658 760794974 416976533 856188137 10305971 590077239 235131847 512391788 51426607 438884208 21549028 761167638 946516277 989083256 297911903 825743792 951734985 958389949 324160925 325651830 5671905 897656385 229757632 706798859 446361485 805154956 298420019 718508103 614910659 979589826 262776532 656077556 199645653 496032381 406773231 568100975 146832871 287973966 178087306 258168598 407463674 778974344 660723807 734026592 354332883 844423776 21550864 352668453 611045610 728129410 7835439 832298841 94424747 465446450 15597732 39940381 54333284 713504315 575799247 901689275 155981206 733698956 369626664 791590521 422918877 430078040 565338090 575104856 72807153 367950535 563490141 967971775 585047678 652023858 85024522 446491464 83014238 859752144 532758841 541473166 177142560 854091929 255139755 570420230 391259276 717516849 114602135 719429464 694890493 918496081 236935010 285954181 245863589 929076744 595986694 683837841 141389840 477062218 299184696 950818504 78002333 194113082 702080460 958471827 486750288 503448550 160108174 996372367 409647936 480022698 278503651 620422258 250057600 369454514 652782783 796198405 113622792 778833342 54723003 710602082 563578662 894567624 329733734 770603567 16616195 692486679 418562957 865204860 827053682 867115640 439840411 536384815 26677210 693609380 418619164 977237086 122856640 335529956 123589345 359125545 484643588 755497791 409345209 967933910 145951038 635049763 227248058 873863223 640618574 973779075 440259381 682833044 583454703 881006142 386887202 894418707 455338242 549719835 276859970 417452815 477184170 761336000 523535389 801959693 277401227 932193920 153111605 883560606 226854310 459494420 89192514 258547216 532803721 915856468 414935584 665156319 266003530 793292569 525193663 936223791 260631303 689908133 150492252 927936327 890870551 896007040 422067586 838208967 479073959 528715692 238966332 816853117 786892976 818474639 854139419 999185948 68222431 717409389 763690339 843104201 366626036 372268828 228552998 376331102 240719042 969777436 188105537 648836346 606999713 881438573 659148951 671278247 145038588 234520823 576356803 965420852 240513718 438824018 401296193 770580709 112581734 234177478 379711310 531991984 374756653 497378405 296186791 668560607 209976630 619507855 111725551 679008633 304746774 942333617 946180764 990087541 127522533 832457055 173515626 981085253 418515966 929135353 16487794 145435342 180532194 754352586 384260549 984456074 357633881 549207661 183851928 446056448 679155062 939871269 586370682 650339766 477252747 991865339 179259461 501214446 188015682 614601452 124187688 632064312 305254183 835036977 90833722 673782837 268177359 625817884 6315411 247437696 365373279 864840973 317860082 507980572 234188434 556111557 28876796 697440514 540380690 611198056 219732011 437686058 209669852 997824383 135908220 365283615 508126824 672337560 61688986 366813880 29958732 837044765 381472601 384670086 279731796 288182299 564027961 791608059 209210856 517457819 260700721 312411013 5798927 154053670 3413388 629139215 29069656 732424193 135474838 486155235 433791290 893470531 112540522 723149547 283285993 399457262 368462616 628689995 56838711 247857201 158244635 372534944 768660101 768784900 140291909 153376156 250487642 346282676 603292742 659773125 136820032 586622770 254565662 622569241 754429719 790920790 7362134 703369895 27149128 741644109 534129298 806284136 885242976 911400762 821834973 897760322 387660302 967806648 55985336 928051485 799161347 919979020 397897110 593301877 59729627 157966859 704732849 767032474 487344298 826730719 42539519 843877047 198056721 415767242 662624682 979027402 427193186 920693446 98197856 356707813 64853499 513153694 248847641 837570074 552925766 644205255 49231868 317847481 653748085 762556349 100486828 163165097 224709537 553620448 118055049 221540203 29492013 796060423 190511715 205466294 836844283 945597928 162250245 509968861 599906434 636602947 34004116 614260716 390274577 812053690 468272382 770154636 239013517 733012822 489904451 909498606 568076373 847381880 102099423 116712325 170545313 338611753 288826669 892017505 116228279 934477371 656945324 914374182 663079072 825966119 7434921 523283927 518876026 590801355 422328991 866610538 687893685 955458489 563754787 823960318 416073696 552758938 268758384 575532835 16685201 176991666 180210645 427617854 589479159 692110391 219669315 733994694 192250363 622897726 515547443 915326952 497948542 944947323 357562216 647697023 78577698 640875632 270504854 270565484 124227741 423573737 69649262 525212265 77200918 650648098 67494412 709023561 756858871 926979236 12669431 953899892 544060730 831502435 200887402 823819025 49852280 312751229 180071625 404943878 614448016 688764964 303969309 409920796 344993083 601313942 603291505 961398867 78792184 443047068 348103391 750043490 420202315 761018877 499014969 638412892 189920718 728058641 499384813 856929125 149255855 964000106 623025908 975305040 38487030 218958656 535479067 723798452 84574599 91702263 318653059 972885852 734583709 889161279 174010786 735550000 595412154 762878811 669037846 743060302 199964232 515949001 648671928 817610243 536115276 786681250 511537457 546185084 550392963 558392980 319245238 690069426 286664702 290098555 142951375 326231161 527022461 865342409 67351015 348958036 382909789 891137044 197346634 506814002 247792445 393022686 310312679 990717904 363590469 499475494 631947122 996798847 395815228 563729127 9584767 449365412 389917167 474294816 90603277 93103330 246343826 691461685 894741227 943098700 139338535 629836868 839786719 912827504 551292299 723302375 25815789 611220247 382771724 584894610 48142450 627466163 18751836 345053281 421492458 537766613 447352495 872939916 133810780 644732351 329373785 853833704 167514995 640091033 258729251 588107034 481933667 733369176 292692394 752007342 252245022 314320927 486027640 666146189 121052772 626280170 358559063 749167999 211287368 989654511 237857658 960808995 175828563 824872258 523316524 783751448 366791385 571460196 409737558 744282435 61127540 998583120 62553142 781621185 247677837 982915450 76776496 853229294 257649941 891851902 593258415 765504394 50362311 148320323 300233669 780175137 497209140 806374421 235930256 760629773 206797689 662963432 178312842 507030278 495608927 557315793 637976422 689060800 639392314 981344658 225273967 518781938 106586293 408081307 181404847 273689602 120567674 832475006 590060753 972906939 189407317 775199193 642668780 770577056 218072813 277976598 296379528 671547979 181391502 222496995 42013370 513946287 745826613 879858827 286063943 621098684 365192597 895863577 23101300 540793754 78440798 267494643 468748830 687648971 210822048 981058075 545465967 571212416 53326015 321666464 714061744 899258672 42396085 645486746 822769479 841209350 774371337 858116110 33275142 282255013 176377162 425928703 263452740 656611164 222554031 431424928 511628978 517166082 408300997 660134041 496239716 622285423 865547784 990103440 232295739 320969087 283613157 623741096 321530367 435127554 675363461 976605207 485020673 721723971 324516696 757799191 505473053 967753774 70588427 827808923 5465371 413667552 210083629 814552252 343695752 468958581 202601245 477250146 171014615 973824022 356733003 986429688 7399488 237552290 950539574 979603620 563529619 662913543 119396091 389531293 447332160 627763122 177402722 221276248 418759598 814313537 138685040 213061921 72642261 522674371 111665924 386416431 588105161 956345155 99336305 786433339 22197668 728177839 23527881 846345280 661160462 864825816 748153133 926957023 22396219 627839455 334970347 693928029 400795770 948149593 487817222 759272335 370341725 718624364 376629933 487175275 14472407 998998027 402383505 776331458 626251729 993190792 651997517 967763818 636313295 990644912 390105216 663069264 881944326 984865377 131179575 930699540 643738238 857309288 180090990 889085666 167543229 936397645 207040294 874227513 17066345 782608897 325621563 583980306 55662852 463505936 598755402 719285777 142756597 292688348 587266573 935897823 401570166 915856951 18144201 936765630 15131738 348915904 771324924 801637569 156641859 315112622 446821140 914886248 55054326 667476468 251442577 797997963 584267452 752406561 148540456 492766483 125378845 431242282 552103626 579874643 168188907 301231716 222486100 697039250 369084380 537843687 458083474 812426649