11704 361
54488171 615499826 63422766 735798121 625922613 358265023 748395751 151220815 108085682 956747384 5981831 860953179 598331737 498927712 276590754 114263218 289399773 626775486 633257997 819977912 653683765 672687638 396814814 469227539 153952660 651265837 279168873 838798503 140846448 717458696 146387011 249442970 927917950 385695213 257243714 55670353 897157043 168919647 568772474 596050033 940977220 167887141 564435521 808203742 456810918 987514178 672956715 369247677 784221838 106479101 296491790 932417397 481262576 55330522 445475582 268449449 432155395 366033310 852534352 452773694 44239674 637488207 455845529 286569818 474502731 409952048 513441711 573226850 77210155 120814280 970768807 142092795 622708495 493384666 173118165 419308553 852729196 341442925 748534734 842123954 907811319 576577221 736594791 755405658 743578532 903635303 669021366 845468071 602019242 184758041 615190800 892904830 551594364 119272414 259006984 666689284 742732497 519558141 218774390 5696669 270498204 448509945 193593196 654621934 969600019 294647961 910123585 688845021 441357995 325758689 612734089 559181199 49398809 342849558 94491418 6666345 225636690 452163006 89884936 524919567 361373066 128307100 420757929 248509799 946456632 906955703 37271184 949524886 443870479 75954258 746302869 49837568 451736582 236560884 757757642 967165771 692947792 687779169 274997894 664133723 984049507 930209694 63382366 995489878 558409972 22988273 245130790 147704481 347950328 83847645 901337587 673502944 772206756 14566697 27918362 865321721 87242604 734002136 493758001 105573649 584278279 503808049 374347789 146024844 851793768 579707064 773002178 811078928 532709062 802147890 910189989 733268609 682680212 280720292 487106123 907853062 174703752 265738836 912366218 524154881 969299095 412936133 830910327 433246490 423846646 737984446 862443621 88975412 822644506 600345667 218238699 768268149 384176823 536583577 204688606 639893313 350546372 797195333 348768850 921638462 880703092 69822220 93954972 687417169 659449150 132280563 344306514 494058398 662352085 699011904 366855752 481619595 916881967 919789942 560164243 139632061 911387777 818034012 33710217 658127640 21529408 292127990 454338750 644453570 383032865 693754505 596886536 365036831 62596377 334757530 910763643 977521365 838097500 918518767 722404461 223173321 762950241 273653643 773286513 728015392 529077211 130376885 448653663 460572222 102221760 783638257 241000521 850133192 668908870 595157508 23547014 693971877 255339488 416097267 697154475 121893112 460723012 796092163 214916491 456050470 685805414 553801657 866677309 405570262 137285245 783783643 339768854 728300267 181592829 702119276 820230058 166035082 567481242 68790963 544353742 806647577 819313995 983383604 874358680 847554109 285801795 132713908 780248668 180867035 776007416 758427960 435947952 939341847 816502303 342038789 80749415 234817879 47241389 103600545 772146073 564985407 264858839 483008464 863158424 856900021 721478930 726078614 40311547 686922974 21998098 450500922 932211095 812802846 140730574 6853440 580230016 698755099 539274873 525443181 943346187 292520378 771909770 477416135 236046542 421370399 989706420 437147281 538981789 313014704 686371053 173601874 649173645 180989201 866100586 58586317 433563124 39325993 16815776 675722505 957553766 548941082 642672451 402585674 146434233 417921612 360565322 236949013 595136000 57838178 411840233 401157680 706803603 876091202 421237396 127099550 431893765 562654480 158624513 316076966 57513515 398146098 802482213 381530571 916065562 388176717 712417334 787337684 796165672 375478085 404254631 954225349 625541097 300934464 979849517 734970851 114253619 170881698 709621183 164086452 442177306 930357522 424851089 142693115 787207924 424697971 698672919 781121215 512388181 695165162 73334024 456567875 672310034 421298909 254321751 821962766 148994881 371166449 261573434 104743140 709681462 786290186 211993127 91939274 37779846 106424654 892276177 518579718 19151111 554550306 674687277 94045467 719184077 416213034 125207410 918531279 960991790 975377228 441964564 864445224 895769790 199232429 669703367 26937962 640231506 704356785 90314114 186397978 850920192 422850046 422371960 126639613 262390044 84259193 807965216 846508568 725791548 194747206 122531117 542240945 342559283 595249355 230380693 314921291 279612185 180549036 150561677 47919021 232507201 298297807 829270409 482360795 435592768 34869593 494698048 784831514 260597227 637737135 74498470 941533935 75524184 738064501 109351919 758056735 827385307 709760400 700354961 575961519 524687626 494763815 708853058 410114021 11741369 10175133 161804789 878863684 156112894 737449879 475465440 530757523 262316588 483141115 536991608 529381078 38088923 793282542 90637170 611229010 643179997 617098197 735694018 406715788 209433417 142839380 848349087 273128010 588181876 212067921 119536252 876827791 337980146 183132400 934820880 602429346 283986584 741754775 187819854 849329927 980982139 593632235 958796652 79446659 349804785 78719440 957012959 865422363 609391759 202446188 580148828 696072724 725428776 552397092 676858072 156979955 712950740 288688028 999602056 811739518 493074405 901757882 850677984 622621880 393933554 125027491 191923095 298612712 458548687 283106747 475672736 450826386 734128018 326802088 554140978 606678651 253654415 620643150 362331328 936183720 396241244 95921619 98833664 337149022 722735309 726503580 981044711 221285155 170373623 373794381 815174570 669452474 34110256 275328461 58471101 799679530 830949132 592407614 402593751 179055799 953369696 702484744 684047340 413437414 416653890 538482126 439722032 985869692 273217542 412087925 450742809 615179647 816877378 22851875 197069660 131053106 923605962 14712381 79283694 728902684 809868211 827589736 174844932 357779968 713720659 688632968 243040787 674602725 183071550 418768323 211885776 402087439 706954826 665065853 233391408 515937027 159265675 946330460 474352231 216920967 549484118 191841605 263107564 358987678 967045697 146427740 63167858 172492175 532619552 657303047 564015855 518651869 622319368 729468395 618014360 386108239 480694863 740408812 898740450 991470313 815863178 2520368 723555458 213245424 891543948 270684444 77421677 341223914 176760684 457748308 888503768 851248794 680120447 70649790 753044023 570814983 254931545 791219838 416021313 363874420 511537871 723056635 616020713 909845096 896135159 477611735 203985765 796368551 262263333 607775738 533325098 472867894 421861870 520288903 828390637 780978778 732747304 897049060 534215587 485562521 14062055 186201013 892013697 123479734 220366465 905955808 98808572 569941176 565273482 183942282 542126792 515092707 732061399 522549271 239005660 295569340 804280958 344011053 868000363 557277704 434141395 506569392 581204203 757486284 215799404 346700742 904710673 350759758 179255837 580470740 3189458 299845905 556370171 656749695 151031907 585062876 55324252 700199339 180245049 493630899 474608084 810182014 574265353 391257307 580751160 85449820 283855303 981506009 137085598 863847659 266055082 114105714 805166171 473957392 111866405 35267755 721567490 191584495 14472686 442160330 648913258 49584366 311607803 454047570 60545192 362512818 292266879 842746378 91192848 353151775 705269744 457557238 984071479 738291035 564142850 406486619 357057523 574883530 192510636 163202238 842876504 681136146 158711074 509245669 91462843 718211096 846793432 582934483 845463474 387042305 37586053 86926031 578467857 607532849 391959324 903187805 29447406 810174285 522472403 236808514 500904861 859521596 76711455 451501187 757507507 451300385 167096245 824431973 893372166 207049569 153381002 336380525 434732458 916873379 162094802 465381473 199263220 146666186 101506820 793507908 749443194 204868859 949096916 986676573 715691025 673660060 124153398 541845296 70961612 387464530 914154848 234143618 797539074 158225154 110857927 710089304 178163016 792858576 540219425 626848247 797547122 478115362 291914080 395652325 605125781 491927708 665567932 737404901 631460359 775360548 64383145 516816894 638085468 639805407 214235612 67538548 212451177 825770289 686380873 997832396 81101124 96954304 519151143 898143435 34778177 629395825 845915113 668504183 781004790 557843560 871921733 884789779 646282807 902594315 775487792 488304166 698554649 496144382 316772063 675845491 644947186 504131111 467848135 295987969 277604438 855340715 829145245 179242516 441842203 198393071 639074389 162711601 477709653 307931287 140183590 951426334 610159961 296766857 821349763 208089822 250149821 196881897 754611235 141383096 475115605 197846557 161913337 765133359 204015927 699495626 588930875 557920010 963711159 622522580 858736222 980751693 268386154 80810337 227904535 777706045 236354086 976179669 883207515 366608224 612882431 247142359 232758622 11651705 345230410 389641033 471175063 265191311 541853341 192873555 173487033 98875109 316696780 337385304 579358139 500207874 72887533 118084862 53421008 731438250 293953876 20251689 502578286 51502306 674991766 521962495 416744010 683700463 56355209 525730789 256462937 194842711 617390913 376488831 6284240 619291869 452099860 699451059 865243171 412256392 779090070 540428710 882071817 669925276 716080540 804208828 799360117 54672030 646617148 31238299 378981022 508246611 457123018 74104872 192009207 589316032 266355164 194769543 755967798 947117611 955528262 448634654 659814224 623597847 917039389 233838993 638951290 647861323 702983607 571897286 300302121 641687499 503799720 988586466 812788753 292304859 887965894 326193737 168625193 919732995 554517284 362576801 168666533 22066181 283087130 319725263 202581753 446610407 640077114 177834743 708613851 953512943 990935644 301467519 345226816 558001568 420944786 270577676 158185565 234526401 692201011 320968322 568888487 673383254 751682515 223722247 452492499 549043620 356277320 48780800 580562646 548588592 905964454 528790033 24973028 764202432 554247234 997392416 316810612 6286679 776164018 178696017 624009529 285519932 812557770 759526666 318931241 61082099 533879968 937629424 114233978 175647296 104823944 513524455 147572895 93125931 481582359 963228949 147823438 471985398 728866851 26789343 859420795 646172711 438577088 408585193 645762141 990378884 928544324 207104537 256111976 373205008 900226115 500430740 849024592 549886738 582812306 94672318 867555340 876852750 88302151 942201405 154803663 387230409 867984566 347651317 831578895 634314056 568084852 605419020 631240065 348499920 210378839 511015399 695035162 753055975 694029683 217830698 678741007 750454608 101072158 315527867 995168469 558112274 633648108 180206527 540752928 968465521 250092210 512554394 316708071 717844466 681910406 173186546 647763037 37691994 333810877 709718700 638113785 763776431 875260650 516958700 354770798 378946100 282147556 422425624 402960050 283291248 483748032 474056149 534204410 100024614 595853521 464788999 509124539 859256669 167476143 668551636 280724137 424825433 253636140 60493472 928540603 818683807 880064863 952501265 430827557 839464693 751565980 201150988 330787675 779728478 969228153 436635829 211923219 468484641 531026378 93023858 245281091 68199105 120584101 796865000 561610782 376482053 319021918 576087035 94564378 838207473 516215178 140029905 853943276 982522058 285981951 245107919 944898184 176584982 483940049 828990617 924510501 399296664 908957269 486928661 266888503 96321367 43556641 411803751 90039922 711658902 874092809 882043126 80777932 508365276 51373603 278954852 757103227 474274541 197873347 58282137 235622898 793245646 425113471 483468728 372489191 437850052 467022634 665298983 181970255 973562453 420864732 530432906 468084574 822773572 989103079 197599175 891340683 404858008 653551586 787966210 307296650 638952085 132958370 770528162 662973263 31440832 55896122 188904522 796919056 158610654 671744770 64017375 962347331 64682228 259667852 704389511 111947419 854233928 43465391 347159207 519698958 995725149 905537919 413439716 313416913 236216058 270291282 116634658 466295384 779014178 747838396 472557191 518899290 305860892 852546195 104081015 837081291 273133165 401561067 563848856 999266783 429326040 113697305 226725327 355435533 171958115 947141555 422330176 450735624 178962772 272501133 583744081 560976070 285597230 482948284 651685542 575175036 299411896 511270038 88145446 148846495 793859062 509502639 196833012 127774948 442898733 86637277 249433461 731269439 288971746 623236916 451042895 637208807 72595163 984132105 326960231 711570000 146982683 95452146 112328417 353350702 250855913 358312387 868204836 610146679 895262921 185779858 485482706 884911968 12131199 554583987 191460307 913742174 797762578 441535675 313894474 308636454 232080071 593947008 850567324 657712301 991550497 945808406 420726640 110128680 716295910 933393107 721235368 876128780 129543708 600645707 236252780 95410957 890750215 389574995 100214559 48877089 60107052 253142785 386819943 297086078 841301072 858045609 101778217 321415063 323203704 481288160 958336649 954991394 203724265 301705852 803874284 19205908 240851241 658409106 18299897 757233570 890682107 369236597 330451859 114511680 467549286 624710844 192084960 915349157 509715118 153567292 485587012 458762437 520861528 833525769 115614821 263824084 169724457 394031480 143571495 402539592 550037286 503741982 314778033 231432407 911901845 277129169 553207654 814118516 187572985 157916838 877624299 978038101 97212185 825707249 475767846 454111726 139803641 73879367 462757692 450785014 609077982 5005949 762978962 421266785 3491661 983991209 645380556 303759459 635333900 461926432 76823247 609275251 660113950 137846133 216812482 157853764 770731210 170626432 58547976 558165708 21261715 392957011 449195334 739627840 694277952 100730949 601036643 795836949 391910101 152697322 320163970 612746752 954080151 254121496 747639816 539347446 69566731 77665763 395461019 496897324 14216439 318557857 447231264 98385174 376117598 68606949 777905340 729903979 85926535 930525063 665562835 387013662 966325494 13608345 770278923 834637669 863861104 528223858 922093896 647838645 104783610 469016743 67381168 695724483 586652889 115645708 91050152 247115908 761479827 329281206 30967764 715648301 379949547 817843450 740777242 26996019 993609448 423383406 575860895 455832650 148237262 761371111 996740807 384112745 563334946 203287161 260186168 142845891 915121065 365442425 848097751 240654542 629415528 195770236 728011464 961869375 475447460 516809048 458223217 263334155 303341027 743156770 300776054 29501031 445031401 514957613 439635645 881798600 119337658 515125776 679031147 11942627 379247773 249952416 513983204 597789100 896844310 976596721 744913870 684179546 90183147 890278232 661126926 878927712 860253471 824939627 671408072 845161845 788945657 960537342 685407074 457033100 330923260 74693670 614142337 967572699 517797615 91526969 272506889 774838999 349468374 387363787 411953952 270546228 311964406 176114098 285642027 259042281 840302548 450775810 353121486 103691562 634617910 265148945 100002030 550775147 762634527 676973938 538931378 523825507 176024022 215731709 796171133 178331141 738674142 380888772 667329781 185233031 75889918 850250526 616177406 98002014 267096890 370601120 88650686 937003839 732561624 445989661 913174426 57642271 986892379 254740652 668483382 172919859 695810185 961334178 531356536 399889135 231071848 489557139 187828100 88842250 465283388 974864468 690385089 135144567 154406026 428054523 251771090 765866860 140371991 153343708 114629020 688639583 352420840 34039437 107466565 437764355 332473410 986842337 560101938 435595598 837941163 213449712 745917191 742716276 976006886 63733772 97349802 232437228 701111546 804232652 483305536 496386410 284634411 123070469 436302637 505696994 852681470 665680843 713133847 918882187 62104120 672280179 47319011 936047832 465520350 101368211 375704501 575615615 504655670 536356095 242197235 135480949 295988163 612689612 611580994 328796399 814891852 373620560 558197382 790834274 597024981 147677471 143054565 784762243 879549347 534935311 583165123 404623175 46666555 916006451 972253638 896244450 276236130 274048483 176688083 7506378 371374622 893367218 719394062 518595509 971825074 243052405 28077533 409132694 9877157 168716609 176222949 845666467 893615035 754668908 377992970 144997969 610213369 658194570 642211186 258547285 959146660 628731761 887412098 315992484 565093185 106327349 915467486 395749746 547878294 851347756 378854764 189511990 718958502 62736618 77582672 900911267 32098744 111283268 708910320 901767600 607354960 682738000 613484785 840160912 124803123 102924898 527693880 195934649 965084774 329257487 312779241 979731424 674158126 170739501 473485673 333408250 632402193 472406736 867247711 640338748 782158546 418748494 9606830 92684570 719114616 14876475 925209723 763423051 236925767 801578348 525305901 962713026 990862532 4928247 791622759 395762870 265704116 952465968 587660302 496479898 318112796 927178669 500459080 508780068 789694017 322914369 781761146 592503881 213567145 197759236 141648457 465138238 414161176 753014089 551942553 87448440 778528146 943025317 819015311 898765740 491401310 911702253 162648978 33942734 342447104 725422135 702230853 115033365 250274110 444314839 700018830 327194868 318537499 870099811 199795345 533270817 719872734 493408943 210616500 15713425 852374538 974889937 252852379 314347129 282836582 135481372 628317741 96139342 129138678 329077544 413134220 200283077 612949759 157747399 262299936 826356435 967855622 473135888 810193804 316148140 769616337 643032664 646114742 132707527 415008611 32737587 128544450 753290455 559401475 405879926 74007574 237178579 665057588 797206838 897518935 257817582 686334653 970792137 510690922 254488990 164033186 675497156 169038707 587062168 591253801 263930618 214610647 315065809 645665493 452648323 618783036 419522173 546679916 636931761 188323207 59595283 646605044 767023387 355025629 610747206 585365937 499729813 258238626 10389261 23177256 58999093 677072508 188991643 645653534 740411727 64236623 547696486 605731736 759047545 263848514 643914019 447311579 564168071 650030263 783253447 863769709 963344270 856633430 729929607 570751249 76356068 679843330 275137752 45137870 533391133 969084128 816937071 605070312 744713742 248929367 341674304 969126628 880061389 446236682 135131265 574911623 648918958 676652510 420686248 444048086 594364743 924277754 99884648 837861911 856352876 987935425 240529591 906883789 518204210 718516440 628640458 564943295 421739503 318826277 870284054 463024625 237974327 200088269 230341712 937826984 909667296 900639540 963295596 99071849 177536766 880573953 815195041 516469241 304133094 321582870 581440098 847332958 873888302 229293211 17327462 839596763 228699050 703396595 436971680 363609591 598726255 584630979 420297798 38049398 133384915 619487474 885927117 377247069 32739691 552034979 899716330 583504369 388781322 377021755 976453521 69817271 611987655 388878944 196268537 214008949 931697143 162549239 836060054 805432878 591091758 801350693 167351324 431222057 885850945 959935310 582449537 357679082 248407366 713402904 145794555 193511734 402371217 608050535 903629309 9591826 504409527 145986657 557453885 847849411 611239822 440483947 857653168 200675279 517330218 604255017 582962058 965746169 598826465 194129025 969649474 945996360 617642823 442794136 5429900 364380928 200869681 920676818 377709916 762475686 236148661 779965653 969821672 168198655 871081767 195132550 144007846 75145744 973465629 881681929 932534857 583246878 419620203 507814084 30062023 301505967 873570854 658610267 876216405 3751559 296405924 389868212 711156072 704304298 894271865 435800564 274141876 737160287 188260218 113798271 583346736 44860970 64843197 586663163 7013903 57148113 817935511 649345101 591996616 507632471 251268251 476942745 364264718 831791874 432718496 874525253 904007639 902628696 650431931 897612278 61296216 647239197 758608704 636071056 761755654 270200662 113516740 912147001 64469142 973765960 572206621 723489109 995341821 130961528 756560223 650430603 456560751 551365035 542120671 796717757 11569251 837338599 798185779 912748307 869752460 337432176 588347183 638026992 499253216 821896906 616814569 389613050 211037076 524021436 544119989 502977557 253767454 825634378 788489000 898122599 396109360 583518650 921383192 520117845 503724738 806919055 452289689 387859331 784219912 598469263 409363456 916642263 324665207 705674688 987312099 15226485 244254403 812665958 336292631 645445828 418458083 209678854 700014767 852270694 885871626 27185253 780265986 58874179 49350830 922054536 751580325 907942782 9085316 141553076 265819756 722932605 967275137 539529583 48012140 414070244 943544282 36883836 441634811 961665945 134307332 864152802 970548397 757857729 834476467 404878053 358610519 996714432 636635614 115866378 869787663 726091580 18354104 687050006 225860393 424856090 716535479 92467470 396948795 693895294 996869265 785101112 461659161 919825102 350555449 809154583 758524888 61067183 600683749 888003186 801417934 224647685 320405002 281093453 495698831 697414901 489176412 8548845 690870001 430620646 128533970 680312791 873970184 910879867 189981343 78783184 787036713 936372378 647173434 589876958 441246954 833718887 78387030 300304452 552398367 915826248 374981865 665653129 904178654 621872866 754435625 288564593 458104443 591957273 625405833 159906049 648454283 603804691 652454846 834684798 334108900 313830709 468085695 731288173 352357018 664930339 249445568 202187668 391090946 991306435 433771061 414282486 769147826 757008697 220691413 623475418 763680382 544529899 440036243 238362052 850568572 568476030 751571365 908970617 275699456 591211735 119227520 156965886 548642207 282156314 43204825 181468568 917606959 693730732 967399845 12936909 424939460 515991092 406187545 215625056 944254900 658472085 776680362 811156312 20940691 820245236 195418636 158546681 885470518 299021752 22256438 664447688 802240691 460632963 917765467 250581386 735733854 852925757 608037617 103626308 260889293 755940873 351658158 17187899 849087700 477517 372500357 79263989 784091528 648680621 518954155 192640054 577300031 325566992 584340887 927883266 761952909 933385624 362774525 277475488 196023880 398549933 106478034 484513428 300836739 226348786 220103498 43877540 765405334 350612556 834283739 477594579 406613011 808794338 934706491 489227623 683725522 123062295 858165597 88565478 708199397 292367248 934549623 238883860 845400739 39911732 452243966 315879670 719617184 951549733 174918567 373348817 826177458 241361355 702409574 424459050 171282413 937289673 131874674 737574342 218697126 931464197 888947774 755754155 358907251 604205475 662139009 127939869 29768744 712932873 900966190 61741216 818647771 375847132 65890171 567886075 37030624 147141120 130434269 83418162 116262348 942991259 620033289 242494090 457525109 990679570 82949620 779153033 881510383 946753033 237922771 903855858 681968016 141178470 725648154 854111436 929165036 210493518 413734016 806740827 930383576 989304613 454520568 465620004 488497770 500544657 537095608 678483692 644929782 459784822 947998774 834527160 32603665 955063546 789100581 502505165 561313681 427784322 328234363 506697393 562324874 600242611 85147757 128669735 30232658 314840945 662527855 719857206 437769853 197996769 728925496 918750242 912083168 308030826 261309115 917828464 848619153 289013935 90646319 878979557 553836773 642856085 314572295 730189702 129903 579103555 329762041 216904857 404952582 16802075 851180026 733445537 502166719 404507845 479684415 931522405 520252909 668749092 302147901 41045737 717277224 877291358 743379625 91682162 485390402 917220567 710660728 885129861 899951442 42107189 337063902 626049511 796402860 371553885 355602514 630223774 531887078 308098676 480548743 575206381 607237844 686528990 170485619 24346459 98573708 712616768 462425675 112121004 261899874 102674305 86580356 287787237 206893035 169641924 495400659 631381835 717487869 207356782 524057133 995303779 622468268 894419493 257032135 14335219 376980045 991578574 982612245 619314686 853518198 508846222 60997070 801817803 182707195 294244553 579882981 993614302 106914290 276955429 657458576 123696124 947547567 558549126 312376644 319997994 981429704 143433234 875381686 81701293 609380624 201943342 813478875 280259595 255345311 82817918 811668200 970028807 668662215 687450344 96542290 26763944 733858847 600657297 544429005 619390258 163913596 789809117 927635280 514730794 264806897 131278962 698859278 299092821 953042390 400089140 231600509 74023096 119013821 326282314 892569426 217871000 218131069 56705046 598787458 312115835 989563178 528599872 530285890 300303396 493028122 453812139 854519303 288248730 514851297 578240381 290984838 856590113 394323797 199413530 721893811 352871742 871603594 27842344 413957829 922993847 788710613 677532812 542015279 473334927 206433228 187753066 711654823 678680076 320139075 401959976 759761186 378505908 148192335 693237611 463800022 728239179 767188038 871089687 932878901 350861526 688015548 924462674 146042615 215037082 491910023 19192448 193163536 602646044 313963707 926757192 426710197 198445089 395413677 372353932 603859546 296641967 543007219 118131828 959313589 324012042 323524449 818232163 250084028 86210742 402673677 571308543 619297698 456816506 579421515 356005420 723538653 330472026 893608112 847628304 704631842 641856411 577290770 763724816 965465958 253867459 38755717 580212944 830719709 708476309 753059679 766631222 104083710 105480728 887549492 526675046 929606781 739518096 18186969 991500742 928502862 657049730 659206244 985957115 441010599 483282355 983411241 576194026 892648445 971060776 230094269 788276407 36604677 828482086 194794742 297788872 673073844 583192627 506282473 839982529 526861631 421375250 140002025 792177032 817176347 899719626 613055629 183387714 952061 679824799 170439082 649740627 461265881 356932118 69658452 251171937 328387814 42361588 801494240 512765777 256892311 964028990 986673123 4636231 502298018 410257978 79451699 96785833 974507260 693354859 921122789 896256539 914617818 400599192 963898701 142172804 493578417 349728453 414717696 178082310 277798454 962654519 517866451 616359945 868136285 706024307 848762076 361595952 291006813 239574334 876280688 437646433 460992425 733615262 612736290 270158016 648546296 836197334 575363530 769802675 430297149 566076269 189508474 505903583 24728238 582394919 555682441 919600168 939391936 357551881 336065419 930069940 502659112 440523096 359886678 152340456 622272219 896460953 520441598 480717928 240026893 53724818 507089881 15816474 619947061 515269958 162823034 428984866 295115270 667902204 13430201 493828070 833045623 114016312 771807912 207550219 171890619 890333119 491690142 277860469 897228360 435099286 230620208 381381451 468136147 120764930 560141362 550606575 915495505 778038152 787387833 603148041 308856311 898996974 291653658 368338300 38003001 530021432 342212843 570500205 936161742 905306539 99787777 965223490 967757737 28510667 988437360 195935136 408040193 527492448 488410509 274427244 363165257 133786988 846186221 930263754 566147127 452029749 993645158 164357408 635083200 168576577 833049869 456795666 102743065 540435539 925098549 840813958 170666679 97247602 566425973 710774689 707813710 569310178 727102626 653323464 194770389 425330728 170329552 297153439 206236799 588845321 705341780 893724939 217079235 337249675 566801348 410343475 462874708 975350001 268250100 500244090 481583912 825193154 672063737 770295685 10983284 999038658 387398185 11047738 663023789 375178998 478042393 226693054 138890376 649661347 369210268 334166902 987241722 507951438 258345929 822210310 702244919 678154940 370617333 309460820 594669238 874219251 213946035 774069636 325598506 286859062 89928411 135972604 419396233 11539212 442666879 846725473 74404361 966142009 669371894 269391511 734668061 173675714 268009941 548510404 555131771 399429356 364673263 870339661 779217687 785198909 699322203 734135254 351505448 86137976 622703982 761881669 800512802 74128292 406481852 612713663 651953337 779512837 884582682 206170792 935342052 78935327 766309534 498647462 320399318 515355834 838267804 193649565 532605957 149542104 877124522 937208499 369421350 989684671 952634523 171798861 801599534 681708020 785013383 943248912 342427730 585436221 974549440 414607328 553568519 702054302 657389277 661749218 777766657 366036316 740426931 523368317 355063095 717991676 206061142 815808596 372989660 454049859 428163355 480481356 318955879 123615030 29570200 844172171 461734027 940691995 295115425 436662902 635884094 783623029 727595339 995742130 414903477 677409803 514498796 409666083 427703397 842617057 746480664 673464047 786488834 825006908 328934821 506909050 238959235 311576737 478145191 101417322 220390684 80341205 556395635 920857764 591254337 987325918 206746783 144696141 231420584 529075199 509354751 316510665 993400135 610286527 615282088 300047549 939753297 625710050 51290864 478347023 323923772 49788781 25785708 853540836 972148156 483334053 89377775 842903201 319488968 347517967 948124048 115227370 240954516 320389233 928969636 765738661 983806868 379463886 367530943 282633719 17786495 92325741 55786422 486475588 687846728 108987602 259466655 745816369 912756773 559575490 441134030 675469477 757945228 885204290 955672792 133397187 947920432 894989975 503188371 557574385 550237958 730877766 754333459 480221907 942501701 427328789 921600686 146966607 376457313 331081736 845904376 772134794 539626510 538489443 468520646 144708840 184784963 746391213 587510574 868328207 884193587 935714731 769620868 827063011 398473557 19167840 835559518 676191115 74109788 677601298 59759760 558258281 183171646 268993095 357174575 710518053 321109808 81551554 585382801 90797986 575307686 576170890 832847690 85351942 837833559 247022307 271449135 805425845 897229367 607149906 133458518 619966549 649287290 996220316 655185427 489834955 518603927 770991815 550515196 753782843 494277441 817602070 82162405 649953035 406633838 333755664 269627876 502444512 66679891 869169017 299378252 58770590 512879461 304113494 258245557 929328491 364501593 909358316 753078257 653212331 638813475 245235904 165445399 121892100 832026618 818147735 845993852 338984283 657737553 702212727 603069364 316065493 431429599 890028707 168095380 38341334 164090007 339283874 184296753 798264579 483855023 755387192 584197345 227905859 69082012 760545642 250346297 417628089 820410131 525333117 809454093 142074570 450462985 573308663 620952946 49931037 407192499 717396891 45133245 274347925 313443717 58401136 176671108 360270679 443377462 958404026 690554267 377525193 570174905 264381949 540419864 484282512 452479045 539945984 219619663 579281297 495848013 945270216 184832470 201764080 425614727 115944856 230574721 210928915 22409704 763131382 258631013 440558238 12273573 950416808 989858520 480544375 821582642 765716402 644479854 282089411 974716230 225741145 250023420 34236390 950530261 842645026 191551384 716157574 392999699 391327186 718691222 640677768 2552694 623495790 126265228 627338512 442860979 158868028 241919310 152732548 81045440 56927679 910969585 776673672 822146511 973092286 702602443 727545858 914580056 438405437 627847536 703977495 501587471 794609537 612651446 673520940 791945193 519673871 117664945 198015205 476174618 372955308 679143862 203495208 437953817 209242462 397780571 369550361 281849241 643027048 802462836 568909854 435060880 391735377 396893206 701928412 175952947 775106013 804815255 883906615 290166519 459336721 265175436 642038357 489650577 92725810 610928328 490117530 272643318 7933893 77410402 682175917 803105883 505795728 357772207 378610289 990362420 541460630 414964291 932494859 825737528 291798558 158879731 483128545 6922842 914873772 783650005 912916376 346853584 100173317 210161981 537583892 456129807 957847086 69411264 101100667 401976268 607884652 596883764 594968370 440918012 861528388 124568749 384508125 200926932 554991484 310179713 395424098 687138761 174122520 638119236 843789030 557935247 231503196 48788427 956176333 939829021 338841039 616228652 850045629 193562534 310131254 975770555 588381851 899259040 899142548 746658318 564031627 2109120 690979119 458636025 835068915 8196347 993051277 337168273 875219063 420111494 95611761 922960172 140208125 931078870 191847906 622518110 575519914 807431072 984598052 855468540 800550115 530890968 452433084 589821212 880113484 743407285 808088687 870443795 529451722 636630442 995721283 796429940 450273412 127830125 447660411 674667030 682604508 906967028 20129182 716312334 114354810 76786034 731783280 737820848 576322625 58075741 222350838 625351825 887572311 632867945 516321909 773313159 211086881 775789965 463969394 895342758 720745283 335693309 976979634 565720899 46838179 389791277 545831483 159554804 161089125 817378004 579417168 24756365 205861615 718825189 132242552 308119332 703306982 847649686 624390775 972807693 357869614 821488220 497701970 128052957 220321517 479533804 317914702 146489706 470525320 884363067 323294961 45937608 120947363 61304190 241075454 213404748 93023012 505513001 219348348 188029836 920209456 420112883 405529006 415103069 687611691 642960335 553897755 250925010 998687163 559966963 324883335 607861570 318508484 504960724 709204216 781030978 378765676 12918568 302003121 867533478 860944152 311753186 655535160 694933123 991402348 589076791 14825299 568896559 947463503 88179102 227245574 426909246 809551843 560121803 691171734 144993669 311780496 429878962 443390856 187178266 36839161 665766282 534815137 89850961 505494275 30498246 740590566 374218432 877185748 656784156 170141341 154654267 735476945 436312449 758970953 341875415 653301151 785256746 448597425 296072938 43036194 144151180 49819097 771448072 620614528 584110684 850398214 748669447 828034333 228779918 130121661 139377403 174309023 612626265 264933059 584176953 955961835 607905072 567978270 175684695 900101925 491299530 508277009 454655017 751670963 692086810 675631907 53979845 178408250 894376278 571285016 971172479 732940190 181217011 364937461 373547500 828369669 511973798 788303615 963716066 890507988 130612324 677612987 641599861 925279407 660076641 823671023 983473146 324045948 393911572 1260190 122977031 442124383 174984752 369021711 452476528 571159743 650420140 223273158 355170891 154549822 943730107 820626568 223507692 151737796 686034643 747735386 297801448 210750068 83537321 459675777 110582549 771061684 141672242 127796098 803254919 242232104 954300067 762412579 56673428 390630070 693160816 560635496 273059536 83711619 970023760 591227541 668729104 304819955 605077046 924319025 927075178 225838764 504662105 938112256 608318514 803393170 68997164 794742536 526804990 646561227 743461989 88889996 797120930 398160828 878086137 779017491 646742579 214583306 494521373 635261024 180218631 905084057 311787590 329932922 700744626 233989007 893558312 536335269 469007882 269294416 723666362 267058790 921561123 885262466 319750960 192932738 491069010 714195466 658400510 769213951 444497708 375951628 339945434 535993632 206747528 629382894 227592889 309047404 779980408 602548565 806445264 281035687 853622099 117840421 575433620 736705238 515739565 480946564 39191738 481496126 334745436 625548758 121219127 419908708 33788020 1077185 511559231 410505741 382282058 198100522 120427337 660897855 585120884 432840246 805574664 354958909 821025990 203614025 806351731 380262286 281062230 656593160 485232317 412169206 186260344 606670682 269267804 596217210 901162689 671678050 73073925 914537567 937349895 911418501 803635116 277381931 146236510 512232042 717212040 923545249 699801372 800969972 685978893 416985032 387847637 695835976 838080239 865065443 865468254 729777356 992714789 298441849 364687053 922513189 439685602 28562766 287873398 250249272 230543772 844682856 900543726 979923497 15000840 674344458 396714251 142974302 65437211 50386618 560912865 851603579 6594314 132669758 181212614 464736358 469624394 258569370 225837390 531703364 32589967 723215891 372758351 12871033 901349584 807730478 330272476 12677035 819102272 224956336 531522381 861204159 455437398 601318814 209009204 762196185 731381957 188600637 426506088 781688415 203275139 591405843 809273086 137632757 27478725 423401956 389716297 577460865 116515072 750632629 857805537 840213800 181607657 525478091 122675864 546046287 496753012 504163243 936468357 325331610 724486104 384185626 79294204 434079982 823792520 150742302 550644883 928420466 115561018 274995706 690503710 246937481 126017508 142597685 600009139 336301273 337676473 473544851 542896550 961891654 123527471 286196249 189983884 974500854 49205243 643809292 649265467 780622413 872430097 131884529 237022919 897281010 450327208 835683213 156766341 781373639 843396916 120798438 280562187 354813172 939075945 186664512 252641070 343817948 758257981 195136544 36892673 449783589 584894694 486177099 642253019 209332915 125594327 405798086 149602897 259200684 185233350 418684374 476615478 977613941 375217832 403326976 703150242 849918386 68768433 270883082 947420647 462512201 117175128 617040120 877144732 162305631 242754129 84524558 19875478 520171096 447197072 289560275 274380776 335689946 115904843 598497803 572458730 994983626 289995256 407653564 642861614 636213068 873303626 200898089 893068427 524718534 162210103 486939609 858114837 272659932 895331316 921724815 262286626 704144244 780924406 692078930 600599622 198057139 745554161 53097318 697486423 507351549 977476316 871600720 770220393 220865528 248882666 905148629 377108945 205115273 443994770 877775867 502282789 728455636 993259911 264649477 124300089 438039615 123502015 607196026 991083042 44278383 416739439 896513822 516982838 851970120 861906700 759967734 301530377 7863792 860359499 187057223 255229041 352548812 653706016 878295702 528103554 57661056 797494466 322201512 400669073 803088114 593790629 717880451 953443892 453384262 372268413 377703018 928960319 933412834 756630080 178149092 169302984 945624427 375505955 873053109 150813475 177784517 997741723 438398690 590739685 737166358 379805021 953233072 992488164 409027523 26264158 179747237 728825140 819720816 227334099 273796740 219410475 909931779 917639217 938746964 211011165 848199329 623504940 856651352 381861535 728594606 906906810 645563415 913384967 799809744 754241297 33258837 718952937 950231787 279345828 523666456 989168602 812905765 505734441 895444131 751906736 56921059 230751381 554565500 228560768 158492617 811529501 802458473 430999453 797539261 849619253 859720558 637991070 556784356 244571540 543066320 519034712 979145890 95652654 721904404 462406367 622508701 21588279 514461183 201342088 262009530 670523173 984455062 640823272 369677085 753961646 852640798 909892821 905679916 38738373 606909981 558799204 155926668 590842528 44923991 229136361 235948321 395895731 649151953 164235513 349209873 518650805 914622416 436225385 613862848 648509338 407007705 561615439 78767316 534867606 656938417 655108864 31002674 756084768 329656157 768330511 816605694 133635051 547375907 667678292 279445662 725876205 666180487 786788577 123028151 708965467 22587726 232518925 634382637 755854762 998475133 247524204 708441382 581805199 767581529 200714452 883243527 817475071 434402919 906105945 875398004 142276911 299575404 81192785 943354195 988190099 464397678 502065487 222076360 96946914 671017905 82325547 120547130 628750607 371133370 755106295 906858059 781959248 426356301 954258698 573169635 862017818 781139058 635694073 98572581 100217378 996984171 389038488 24518518 163048029 302466750 241060604 165373053 976564480 698062897 385792890 653198877 492417920 343303623 323922600 984467067 302482833 170757575 891089499 592175102 381536042 932644021 816540327 21697353 560330366 926665046 875755489 426572609 828986883 516584624 926378654 300948748 423280238 100712454 854882740 183194127 192884916 512624863 771091000 220618223 176808970 214237950 562415485 994097808 296062949 724116586 862752539 193095703 384482810 257601383 263919332 145254123 236230717 298034298 122266351 90398127 871277797 42856552 668482960 904750921 600194661 12116023 99551581 531339997 715651956 707402538 907621162 926065105 829485317 689969864 584411148 162130377 535546958 665524949 749429081 982154412 418953924 933549397 323166886 864065693 542201883 26223760 906852806 711596545 86211146 540848904 196208848 20328830 201459589 988986243 143834137 616758777 437825088 864230151 562903604 689616022 987008306 879753431 369656313 247839932 355966286 739596922 980438650 633924109 985398218 115348404 108789518 228946033 186830875 430899338 940896074 65761803 781968886 276364609 715177729 19046208 478410064 373520478 200389194 967050423 483462750 730194599 856950650 69214546 467325844 402425120 966844197 725604409 243281833 95406861 901485088 174643919 578495376 703568373 791597953 799124666 342584959 489834908 69746332 929969631 819980268 777735687 846777095 442133090 134425482 920552316 925481109 880198312 773131599 561192062 252078942 722126680 990284143 374819796 86185908 531389781 600219745 251891842 473361966 562794949 525663449 747449804 71749025 529950732 99997131 698019129 317241121 280682448 775145070 350619278 622327811 367369461 390875701 356894158 340129245 889571234 637150422 22375231 506727043 822702650 274953286 433361767 737937418 322561378 454349498 846334218 993495752 892144640 811189415 170143533 360810321 744362297 668949186 856814869 763125371 522130034 610339840 413888583 196899162 540036943 545262485 922207880 448886083 97754549 383684856 550583261 274539468 245115339 384472540 879586956 674372809 796452340 948470327 927001881 637905487 612232405 934534206 772517449 475024564 985072981 130942054 813653793 408936077 745311383 619160420 275886822 509593261 644169216 881126957 574224157 104898091 529702710 160692213 990709643 851460188 203075102 849420851 572661814 215698644 608698077 413806746 215169378 453174632 157169623 823598881 421666707 520657454 533403058 352908795 472681872 671631226 847342418 203837854 406863454 597647329 357173213 403690175 289348416 6344761 954365624 90451027 965167548 533318038 455395207 691253647 257744280 809958222 569537072 657774567 665782487 38159605 420694744 383869714 762684864 886629472 422515171 991288067 4499159 693538725 207070199 27616241 880551137 605483288 834707961 110672975 342826724 833208655 553428237 179632339 311318051 903723806 499941529 426754162 161886244 66292634 195788865 732041825 755090093 336329241 753880555 134453269 745457090 946533935 419991484 438255427 648388520 435105713 787194904 906680799 68520676 574360245 480425893 49572896 753605691 130432911 984337224 127065721 386686643 267455701 848291877 942799264 215277455 469534555 626597282 141969034 301546582 879375927 914074468 447714924 588036299 83538620 539643215 74647739 703280885 920795266 727585161 617856812 458359064 152318811 607754871 684709812 312663994 220217182 387126973 768204423 120440734 759228128 736638272 599754780 260996043 115153013 812004135 63978790 541764484 802605810 455296981 116005020 310307920 493178220 626322672 879165873 883232755 744124217 325104732 348114395 486411890 740624878 860972607 269379791 339915794 414775135 941635838 22840450 48709976 312637857 350028093 667580200 366447882 47308553 65157090 759739704 881728556 921256493 906037265 655216997 813501442 595377121 342619441 133867174 216634387 890987323 825619173 257328686 801564195 873227663 81255186 610059123 561678903 66650739 941248990 784840234 79265941 138728379 570183086 151908424 378799040 77298044 339229990 395440130 264334463 315221516 315528492 93580237 119051734 325297151 528670949 13163614 665930505 862451754 591642037 170238121 479823263 52809635 593914178 577884644 947157341 334985150 335744369 347238277 472933958 275313681 79323750 233595711 507795616 133048432 817505415 432250632 242688753 645034736 563860601 298490133 146978301 482633191 395088160 523412443 801599177 500142057 281460642 888325135 972500634 166899148 439660899 477083301 556419317 533754020 656364553 211687124 414719391 621707718 742674297 292044815 942860957 749860552 469837271 678065165 250564661 829111678 699706249 688082625 764045547 771150845 527125812 533955169 393802628 515984539 874076092 111458658 644490501 906225133 135265351 778270841 550934195 758080710 681190458 593771162 190137875 538464830 211187001 600313596 537029866 148255655 507825962 756587795 182269758 547386520 812530737 773454483 191273299 789954789 103089844 556529522 209438637 533772964 139708248 150226918 92015891 282329641 873521922 127401570 974504074 895543305 831494358 201007004 113762133 170073882 914606137 273791625 658162938 281510000 400475346 61939805 65699135 919046497 348890244 539503247 977498663 668863873 46353268 624310995 94999033 402269861 811128329 86412061 813527353 628060387 649155302 465448356 940518060 579528847 440713456 369877211 791573848 2239551 21661005 5127544 236020864 583739079 380253026 916561008 192466858 743686972 920856276 6860536 947950748 468190452 867225991 369804421 436656474 392613251 909994400 257929419 25264681 326586558 285723014 785550785 882124174 617082555 200842204 134858138 791661134 794241487 507397511 24575181 639551855 304440461 679278510 590081549 458313780 949992396 964369844 689358928 996095524 331960993 86351166 166743243 576806146 168748640 194905139 745060595 216613077 754269342 78751413 852533373 396123105 55248689 209669932 140636510 513250476 908562989 53194811 28212682 985919993 246851047 608458952 185066040 227523790 462741237 630474743 326358875 749292145 940373035 938849582 37142569 950425702 921248415 326489618 951948247 878391922 926985637 358053000 906358747 818663066 902651602 143928500 852288999 537039651 153979900 166676219 796820467 394894994 89289527 807604739 779719219 414693293 429372120 974089905 29638940 706254199 723685237 674181162 83584866 691523895 994119651 723068882 966207996 960156273 533684021 742028111 519602205 551640810 427842242 723401349 446106939 474909863 34411039 672287643 316961035 883625966 848390432 818408179 942348162 253055810 865299930 883514165 430205141 281059690 195293347 244826948 532845433 395022697 972505615 871283781 920798754 596855430 877544691 311637919 963278791 162519109 745837157 8100085 794331547 609921132 746065337 731391020 181021972 739325694 105868421 328940395 297529832 404038721 300567197 742670101 425977354 326843 662365718 40742351 463838128 94405424 545685318 639885439 532466511 609696420 434779841 406335562 612489115 620170334 211967325 443344532 206578571 248849891 326608942 821001476 130802771 986989302 766822537 632883580 362607463 377086365 600979460 108496932 811235453 989905950 788699763 533354847 860389258 103536893 779838956 624891346 61397700 194975998 983375555 813432932 3217566 820516648 272562061 273979448 325935565 231578816 19885856 611274419 744433480 867992393 55844496 867238779 846828099 374181001 196151602 356213365 359128114 854955142 167597724 928842182 344834252 514643844 485786274 841942994 519009796 106537991 63775066 55403327 854469648 730189014 744225560 971086577 582620005 185713909 62487153 893526542 131055801 504756650 484418619 715297275 362012414 858897016 103427466 671147612 376784236 771364646 407146420 780087575 338807 959106487 216035405 212303441 725394131 392370802 957550378 736884846 411151223 805657563 108427873 625169940 511825302 892904631 906263622 619563048 20751270 182204427 966642031 3862990 89741405 320651549 203264688 939933292 918062254 986641264 431250718 525652390 842902991 613755595 519699983 471497570 577349940 797780274 235554583 729281989 566156436 68818666 822820876 170563891 595721699 657538680 928400642 273173074 892309845 255274145 575948366 410375687 292755808 374969962 210505862 652211062 8159930 85883161 763211902 279890949 994112598 219447346 92996939 148509529 233301354 624270201 173639747 319996246 440378219 645506293 928944378 152420898 203674126 702250730 924076870 274986529 293073223 598526430 696956731 400643066 567267149 424374932 139840814 317004943 439395475 209742354 146206645 408843528 29905360 509867934 17748900 80706760 863193079 462475964 900059153 671659893 744316478 238123825 254100560 649725171 181007898 66475266 514217974 668861800 987340096 772962932 157462745 704222009 56139685 937681932 913278733 946660106 97129854 196930704 290511592 165513153 63296831 377857283 862023934 956425346 844845983 115062956 332470820 316025012 215502737 712908559 397524336 5027833 290389068 914580977 902137910 91231801 977528131 5354839 438211083 199505815 614950444 301953415 706096837 516534905 36079356 236607236 220211832 204017539 509323752 923470997 116174714 245543323 767515492 68860733 327745631 727898598 290697255 761450051 919455229 244107720 864773412 928187179 894799207 950990055 197259154 798306747 129537013 523190568 432830692 973923318 459704633 694246063 222171344 40734242 433984266 832889314 999849291 568945349 874550653 592223077 462401674 614808227 800377573 264600607 985966338 359709888 312207322 673156402 532182888 280284259 400152366 179009030 840921265 631066897 55858680 311164990 951617553 530711693 982514572 641831872 777486079 182889181 579670912 62974128 657662254 715336263 959888296 297267060 708108948 478613839 442809882 871063217 261039462 716608697 716181290 897949515 44389401 310515084 880068461 554606696 813307746 531481869 986574265 125953901 778944566 404246719 720691490 932711934 346033610 343800936 89986813 930186753 912765842 218563598 535728352 714946458 958936389 217256436 519637664 212843823 893152982 207738017 97163856 417786213 581539963 102354137 951930951 192779553 503315625 742080417 705391386 97570183 502270997 981937215 131525020 918405116 867187124 311151158 935448805 372305447 719780027 704304973 421774407 361801195 230191263 112097671 402722137 472845677 848200980 823315243 563480560 368398100 200165393 300235453 646384159 121646978 114167753 172663042 157937726 368371615 786506930 844282623 873768671 808632462 468038017 971863034 281971417 456297909 431290667 32302966 967902016 305144504 580579045 878891322 343406954 471823742 873421860 74432330 493471467 247387177 33437853 618034155 358662553 613677857 817489988 243966370 500782984 602150665 598880080 291862836 282561805 830569670 303630900 287029670 505158846 118114175 930993574 480194622 961805167 786789015 884335260 227457152 608347189 631033267 700034121 292162096 3373158 44286649 181664802 744291157 925247894 840156622 246974430 601314355 917231003 579165015 442922865 38766416 9801353 57546744 662254352 414806895 926156469 257886871 393894703 814400406 379341493 402834520 494029444 517678859 406789469 340264609 499252229 268538194 878886339 1517847 45198053 284493872 714623291 133976478 406852762 377332138 488049498 214612572 196792537 601822213 541126646 172162486 990904727 449844166 847501603 714451024 437400840 159056307 971202359 364798224 74505635 394649807 315241158 82235675 271878684 645852257 523123365 311430613 369677671 696116717 36710378 295239908 313899706 343746872 148565481 928858668 905910154 651489351 663672375 660234195 934630796 299684192 901790378 379748926 285651125 498001158 165752151 132290578 442689338 693060096 667028113 763508275 299049360 771856721 232589551 172322758 845972588 25730624 813699910 526414898 607526594 11585617 724300970 675423002 715579849 747039561 519865968 668487267 81665780 601129774 102096941 462512692 466850809 35607619 298541495 534026479 462828237 566302479 719888675 218335548 761075621 869268566 832492741 332822526 810104566 805937436 430804274 688770139 766656373 654462632 461670207 478237623 678491158 191094911 80026626 392895928 172574224 301708900 352580304 674811459 589325526 202567261 614716220 111945085 673263647 925363888 563902750 608573898 946361822 738380257 215948936 97028047 462411849 898557108 854353873 288609395 136821205 370340912 356622733 795164888 359604535 86151578 425878162 298905190 16650084 788682357 213594612 951688384 192768912 7557767 201784585 995119052 512372530 83515862 967842660 795738543 732060157 267168421 158275293 33613517 570587624 737676667 932220806 36848588 513914662 675471644 84542902 40027024 92963885 612451981 684172802 889357631 314685362 173182228 623466814 940899390 649265322 825313332 542881407 26966577 964442186 257640372 654364954 83318014 176514054 286005143 60045477 294809290 203771285 920970276 135276277 164965881 846705898 851430367 73283102 927481137 687056444 558502285 302904949 262307158 550812158 223671859 649943183 892678543 308597990 316107543 524859202 419861822 519867881 459316668 185125795 900776459 37906492 743357929 139407109 899487193 566487380 947234210 594081024 168486094 894466277 833960236 625709926 667677006 342615270 960720140 948640846 612639743 584463754 676887559 969775628 248439750 867257672 214747426 223029046 820769223 593340627 813208483 26232480 825637736 977785121 690495246 600728927 214511182 675247463 559384871 679013065 385955421 618291994 67137013 838051443 622484411 298433007 304386492 430485552 515292876 471330267 290019586 657484823 554225718 450472210 999311498 255136893 235655390 17412107 83691866 874677237 145683945 378288505 4796088 107494743 279191227 19160146 466105384 994236853 730611450 672545228 25033583 393108582 940540554 124464474 985991826 283542271 76115345 842120370 637995990 890688851 433035892 389977544 699212224 435974521 462067671 56718035 862738198 57227206 400644768 849505863 427100379 117966542 701049331 767956184 943416406 484803942 73545014 172877693 762329867 292912804 15937550 758649193 372276415 293577180 46339168 199639570 447943031 805568164 376538192 508171565 964125561 775946447 481759300 94336687 93360456 614646389 135097056 5729485 716246443 791730664 885930762 530818556 957405605 325958079 684918247 768639728 843092093 647585999 701784795 904531616 90681783 957157932 981237644 644986431 81442072 128223019 378484703 373098308 122865830 587214690 929629688 572172130 398811812 522215589 867145789 102711951 374607257 250628361 378410322 61480192 749382216 364780772 174082590 4881194 288854456 959053002 983660483 186441153 114859821 515507089 755181993 6756796 279893036 338936397 639137139 39440463 619326587 568519763 879273223 43860718 892136989 405212473 94459017 774112079 503722329 133881043 615386207 487971688 820038322 664369462 632349998 518096748 25570031 938497208 961759706 365166033 828033812 849675758 879256457 529115468 186337894 717548971 56484768 211913425 256090219 270836486 18875843 621759383 824814822 766335828 318775256 179441426 639391198 147810857 757363203 898996470 822741910 538206042 19470506 10709817 450651797 421527805 561962098 374310928 639549855 569876838 404523071 660130289 733206969 904090922 728317752 866580367 524355113 595555615 569020607 708345312 443544690 606248537 38338684 461795352 943444571 564314158 509454930 775587246 224610279 686513714 211332198 346307158 78423389 66123322 498709790 796505092 659436353 375624796 734172447 282772718 910503000 705755372 781862734 994255754 917000615 814738048 279686863 941349003 213465716 546372076 659554056 120139495 670955586 486195269 362571677 610594259 761357528 633830113 723238004 838627011 563669562 909472084 23160754 872024430 642822317 732268915 886763452 725135816 786834102 678627156 996042038 424294405 466340122 901339979 811436805 226289308 487654622 255777774 644306000 398507072 253472584 943026705 129605242 860244967 236538331 901561546 7249192 222628550 980140638 807406445 453210176 771291218 59874517 667289487 39942631 224131648 375789445 983412997 455491714 781932164 117429491 639941605 914496693 517769045 135760357 319048324 466856806 404688166 901713758 218029430 869430201 257916078 184946341 842581904 409560340 370239200 511886654 811191271 816514332 573614834 291129582 471636945 546563509 165295193 562890170 921760483 53241605 625438410 895016935 525593329 325924209 593866298 429963770 134615568 985936285 604056798 342936761 15546517 167499375 623055658 401434407 309279510 854896396 77387221 807594123 926729831 546641624 648853970 985257065 398235550 83291513 10291800 108475526 445511695 633681619 795589338 307441383 235987280 194933004 454427918 593558993 689775413 215784585 739451625 286006218 398379475 447326191 847783072 610788246 714953088 620473378 196847783 860232761 42672336 157411911 132538805 353453818 719329432 833839045 106449598 252782941 18005486 781126719 763527926 176191783 263075366 17641882 784274387 314427998 413500630 799740412 464491786 267710277 659143122 365352394 228000401 57448547 881481519 241028009 588253339 595690107 695621443 139438205 868610461 948445844 335252642 728996716 675369038 896168434 361436194 297310682 166160802 58543130 425902295 796324205 42731213 143187666 535592470 809419274 523267910 953251357 645313909 873185237 735667904 440258626 915427016 394165557 493922097 617870788 967201317 540617932 852827854 799333226 673643999 495222657 592060428 153868344 583865486 403706489 957810592 372710259 173368068 696941337 399331455 188712097 475480153 421808389 696593886 466040709 783673311 835010595 892446513 493102118 690044205 494168728 554518575 992315591 554470935 542503624 9978571 900898287 21002931 235481944 373801275 337587298 299495765 542057263 917346292 943361829 365145746 730222448 933449131 814230398 433511232 80084353 812257621 664320752 605977715 76988678 913492519 547990849 74500481 33332197 164839830 685590647 81932798 369865283 64637782 902587094 889192383 857588868 603797854 524124899 353280730 243406670 392260577 442391907 149382563 264464773 426063189 787036507 73251504 647624784 36363375 730049553 114242261 238106897 530485284 783486216 562676007 107434352 274956713 932857351 26837244 346382160 199194739 330424082 194040808 600240343 380725815 658998894 878500800 109920873 944151273 115395744 911934618 762608812 265921216 828833901 705133259 424820357 678709295 702445274 849074406 55619352 943252460 460478765 258727362 229273547 349237997 13037289 795692148 900974147 798095461 554396629 314844240 172440164 577106378 968140277 318156011 551992916 10439376 879144846 141061147 634519671 876285806 980457765 817252340 254527859 140998616 153717632 500858059 822186541 471168130 510788514 195605814 342034890 789782563 451282642 942076937 963475886 211948462 714381972 477266010 855854974 56972377 710791341 820903805 15535905 550474649 363816738 922243847 335999674 823600419 583990328 498484942 573908142 79982316 291139700 954368742 510694820 525215017 630934684 772352932 953028735 118235726 254063027 741729182 501779556 754242834 151078144 52376489 923712185 773855336 291156487 131387608 412583203 662076294 816127117 889216131 413537671 809564130 369936535 116011580 86757385 208648495 58250858 590665178 880139023 869938531 268502668 303224689 504622909 937302194 779991489 882526039 640062329 840362387 311790349 319901728 473471720 235984058 343187383 176512161 178334446 192150811 869912387 88956912 236139313 303275501 796563318 468472161 242531222 423896227 569067606 528342666 455910465 845364467 729511974 134057791 941371800 561774290 105472365 643599765 157147711 488911477 548078830 133416418 569364764 730954833 697371568 134702266 988367700 903810331 455163127 59666675 297582668 209348039 685407304 989899681 980690856 744576396 659532649 422346265 455031118 399668701 536773725 152808945 564357474 112034929 510400363 575629565 825958474 452139323 619803926 327523667 779339947 115547761 146137637 56480071 991797609 487907464 197013916 113394030 515867562 753930293 273147072 481554078 251590354 755379821 523750167 764002283 171331720 725837924 109936228 720659114 119389359 321823633 708171950 53938801 346564972 369062311 274397752 877175060 399139109 238796957 246712713 295825065 611446399 908127398 682407781 624093572 729977950 618942520 649569489 790087226 372646888 133017096 190291730 656906145 249452674 565260555 501174190 433795790 69043664 340630646 379779176 356884244 602304952 898342845 135906631 892327434 717763679 461628055 913001103 71378308 62176809 875431159 126019269 813259160 360345020 195044628 154103470 296723610 607379453 930227553 448059727 976142112 210219024 243012756 726005230 88648702 720699227 824679842 606900238 319663689 826798978 914727360 170615670 872663383 460419691 977853027 532312106 300205244 738774075 911085376 713942127 682131022 891318615 94369355 648058058 574886945 923120227 386594235 518633984 914260618 257072708 98428931 465966358 65749535 608911393 929164249 679929170 426729396 702399324 413547058 265661495 934717534 449789853 647350339 566999948 486075251 754652359 471415169 546297685 331287687 551722752 583745441 49178071 338382192 115998381 901907608 345933719 957313090 62343794 671152794 436183387 235518290 620990261 578689566 615916070 817657654 626955802 689139159 985852735 226784450 656156295 330626748 680438314 760357132 996182561 632037376 122937004 942302568 838070988 630961945 206756554 116444523 948042414 489284028 459214025 851557611 635954732 177922526 335352110 182669820 643124714 672741811 958835903 401388276 936428238 931442098 589244543 744879719 992228861 711248526 261337013 671833898 513289435 782705470 220632037 373217363 396998414 141818101 772084948 157730102 291134074 167887657 516540551 358268264 540101445 984592783 115878723 682025663 81669588 675838492 307681678 244528975 744791755 379609349 820517419 550304622 124222225 482426559 333175329 539953584 538357192 482248702 580090548 573303531 33716312 87958969 345441641 307441202 953155171 649916195 111071749 274040541 172007889 576349107 346115214 720668286 55743685 992105756 931766087 340145388 682478501 826750804 954258103 112580156 775810326 243816592 147217825 134973121 677523452 37679429 644068620 642216211 207636861 945572392 654480444 623731204 636748029 582214701 170638518 490259115 511713826 720111243 255636032 60167773 134827217 546610869 481687773 204682413 925322542 882247265 780325076 1569138 847637919 172978565 50475688 342096065 18919113 699442260 599022880 834497262 794483088 62925636 883695936 213590670 303145242 756458250 887681101 262388343 762858188 82518682 759679949 733064125 203922506 635651371 205678979 408712629 385274746 702396465 126271350 408042485 578302080 577418592 296899561 165810258 719241667 325108910 862870883 498734815 41011173 998419025 600203944 578663411 828234702 298056892 73055421 690858019 83242657 934767781 961006311 118223938 311883716 829925121 887861932 110701416 737319131 392581380 365100495 558883559 641074124 327252005 182339671 545381974 904366268 434478616 537448072 538840970 642891791 376614097 676191975 309631126 850229355 852108422 459887673 337357778 839631540 549175213 605168515 821822416 914693648 964570361 42872331 448461671 861563364 395810656 587028308 999546283 180222933 435132951 488165157 490588658 524746695 335585427 659881346 322836944 491472352 856288904 755007151 546498331 911512708 28306413 588394804 498936295 926159449 828441845 633958867 388802697 714912324 888819735 946798482 172536727 676205417 728364038 985565623 278517733 599104302 522721208 909757893 849121416 506245432 984021602 894119811 110059734 136257899 944798073 633363189 166113379 165584365 922920114 426525792 894820101 70998818 784957442 989284937 993880784 712622000 340401053 80552310 768698393 564953724 386446330 108757738 768087926 755508395 29662156 978730476 598551483 986044321 354185225 122619904 117140990 272028419 87704550 295429866 590196627 758346424 662644952 593135794 300821519 195248355 941900436 320526746 96819528 754717161 6904079 509923368 468559698 478130289 748290174 392817954 456854659 991212894 816939862 101067659 915457903 91551701 642558539 384040106 676665067 59518268 229540947 138306563 944562189 100126008 414920356 232600411 570497577 192761774 923139249 238230199 422153428 789559490 365422128 679200860 578268132 595738330 872337174 849308368 934856558 441866906 749905304 370495702 942762949 732477672 495096363 773491573 162158464 882486505 233268611 275268593 120743284 919458817 495461527 276031951 535996597 644640214 642433690 579113172 458653336 827136077 424109826 793021702 573638834 143321994 160537989 565939880 66333401 799745011 110237206 687798849 32269602 767418924 979453675 926245012 636702689 836035867 620269176 585293992 253470635 122955749 821588340 694314433 573202261 325750767 414130899 110930788 818641909 80069341 277999561 79014231 691379424 751314580 185385421 650662813 917200809 602039611 46206610 650717309 540956200 894419765 270916622 920039034 466836591 312033064 562382966 326569563 421154517 114449912 327993407 119141156 948077038 145061579 806999582 886748186 523467920 858754309 314570504 460790979 786069967 709523533 265050674 220163810 942705409 959972997 852051728 235293822 657516473 139356629 274295129 677611994 813496783 43382432 321526528 522146173 537942357 632416652 666103867 996235307 479236770 839547261 667188095 119046377 832798283 381647769 388757377 509439740 666601252 724152133 925793590 505038314 22316098 113330213 580956627 949785462 139894523 872422431 707291341 972406183 41227491 960955736 640092632 593781953 439129551 409725492 735257835 282981705 853438933 723245401 255113273 391390724 857100617 451768748 699843128 851677175 782219968 133268561 681496478 372150888 993519888 193869998 32870750 95959258 148896078 262512231 208229549 11892500 635009229 462208866 227609346 681980186 707733797 966542788 13224465 610200880 68296744 988520945 872381903 360776158 319459821 769039503 198278256 322324966 216066760 62056579 305671274 443288654 53565775 885445361 660230259 5299292 697825878 943041343 354629502 82657171 538871026 502638866 433464513 841634746 134120057 840176206 282036657 477562069 991115392 203503897 676905987 695156521 715470554 977425368 132380587 222358331 919423902 276515631 491840224 796470737 121429793 580302340 182566933 553668590 500357110 471804795 183407617 57728729 973516021 847883002 166753687 93604374 950923568 743634470 72949261 88350569 617102334 776394979 133384408 649406681 934803700 856457559 181449645 848550059 125899237 38599655 672315009 113233250 482375912 759823671 751860105 378777029 202534994 745326637 817253689 628516055 49857207 216917486 408187976 592929247 386346732 870898654 325434281 212695137 343995911 233771939 175504530 867680290 63929692 286935841 394795641 949189927 402505857 972593278 395820817 281256885 759885641 668080159 21102672 573971538 479595468 810235048 48255594 237660097 442273884 113804031 643711958 688829193 194047888 975441481 32334664 684511086 161928253 91482602 253674932 545416821 912019319 809201032 217206353 572776419 861261459 973157640 595155090 909852605 949858087 771224718 509088813 494735433 618533127 636268160 462256919 105867787 286797896 696328579 962457989 204506055 10661184 160772219 222407148 191152772 572789379 998205582 745715969 693915014 227556583 834074400 428177337 134195282 455508352 974016983 481699144 129634478 627860899 412930200 73669925 819060893 153033446 745404807 464026371 93014118 737774365 158999306 706743000 664138892 712754781 307657158 353345241 606060502 199451900 505801887 409563003 391275848 305941903 735770811 691925875 45743143 96212201 240866175 802461622 564318201 60219425 31264399 402996088 163576449 929418892 814524881 601812528 705707973 514924990 633954153 365016977 725002251 427114380 73279934 101728658 823854039 452625420 319550834 728705126 593186286 806208402 687454061 407023235 127984981 545439411 523619026 210237086 305042769 218143301 348927238 277534124 503533928 783083868 909772208 8490210 761712477 545813326 362494643 133266868 986533687 878208431 877280820 632639449 369504058 305381972 159631514 579306309 999131627 879503699 990238856 266662956 56885775 473677568 900598499 242148100 348536491 738117617 100603601 583766658 787648260 976662266 131803575 297924507 315806368 221108016 765166906 328855940 156014915 923748841 423636798 698707378 767090929 840582841 609979880 51866074 58363377 110195573 177873311 40845808 614540999 401080371 847534854 920935467 337997369 989268807 417029891 911113470 509540682 344279367 843478202 661206815 665355585 821918983 636848529 624555907 657939873 610813341 388881196 72042335 760602161 56797277 971464562 314615848 938974965 402954972 781846150 919510419 704239666 895237871 866858701 81376661 10589805 720409772 75991789 550236771 32719980 399067752 273915851 402069105 940462898 175350455 309015691 704643189 149203974 968677998 974840468 256323941 849246827 145900194 221388680 363595380 480602152 935777961 446353231 352142104 470375233 857309208 366491148 590206214 562823676 461352643 582342692 640984627 973354204 297893055 203357758 427662035 32517799 928750177 388745020 50875229 799533667 105949247 951156806 987138180 887971668 716193070 287971519 539836223 464861951 72911937 927702605 911431361 175865641 403333839 566091989 445558912 957985239 22471789 878064763 585241137 177934670 928498415 351274404 378353609 429026324 541188202 189613303 720392573 838849260 505546548 864862551 397724098 12945117 94952417 582463978 293664077 106230571 588552518 848036372 727189266 789402459 904992889 256763771 490533447 793648946 109808846 216952323 738427490 570122933 614633435 195339731 398903062 929159722 361203572 252224334 534439513 770594836 269252526 924409625 926194272 129517370 481486559 609604122 939426720 419516576 294228379 323868534 876251854 386548619 428300984 735378 252330718 994762624 569439050 171997970 618711303 172771397 835048102 779100379 752068284 720972253 975736418 450191380 647649204 668883599 528369234 374939424 424829410 910686430 995132044 283139748 72361852 384850833 850076515 968571783 788029175 987535788 757492591 840514796 316398344 143440500 833137538 579596856 121556644 196648302 962230964 240232721 867407103 558869088 39387223 840526172 959672208 7030093 502527490 317851454 688469514 512812156 399848841 875078939 441044579 649073777 796920578 60187033 273431761 836854769 5408961 287433116 591238599 387339777 892403035 850093642 100794363 260540902 709326758 930321160 674106978 914565926 532891318 989183354 169142321 492381572 871314913 789356422 647736028 288311047 536850619 516076369 646844442 759226355 755290905 169365311 705614814 898285261 282535697 545590774 525678175 593736282 57354999 27660379 973076496 787312031 956183393 48868242 853526951 289298913 846702883 559526657 21962265 64423590 921214802 529759308 403826331 218912178 738950980 503934809 566799010 522093321 963575437 186894413 645336546 640131314 329065218 445071244 227819602 998697457 358176441 607476156 125750821 779194572 94095879 513824194 813452242 293103750 37113215 228304066 82318348 783686758 492467704 894088738 332500425 442614255 65013895 695521671 749617214 833102568 751606400 667355349 873591520 835521365 264432504 219956786 300072292 846895483 360314693 623032323 589584831 322333151 856234491 111116012 301896741 448824647 401516527 740567506 247999245 970793654 571940791 681292764 740819754 954743667 668624935 153321069 411757938 294675713 116189781 375330603 629649691 398442791 707174293 53035514 936312728 185840617 748926844 810100480 84242591 189444493 390713824 726850722 95091748 816383126 395538645 795265412 10355806 792404938 453485232 338372236 718756801 593023535 31121927 273139934 305601793 430216457 677148079 661663201 659183893 852678621 257795259 371562807 665356592 935898224 641256579 227868360 732266696 934986439 186750617 696015031 561594258 506532135 63042260 666516330 273654147 947577878 871409480 314026373 991052496 86755927 142701131 761080814 894463470 33275121 237059185 405108682 666628497 315756328 400550543 189185661 126647984 42651265 673410491 731571629 665494142 540143297 737367881 112623935 278660721 272373741 494190287 851311959 907102271 30294603 771490849 331647579 208260571 246269534 127149908 907711216 190040955 234416877 59299006 129788410 27084692 217642236 797506291 163599007 447986906 239077328 407604937 71337539 289831492 331455214 757062484 449901708 678454022 274635291 516020201 190366047 455338644 145258845 321720862 951223008 480939684 932462327 50202567 990757749 21440811 501352304 931693818 588978115 165197919 810358668 775691 481662638 165044915 525711952 246606223 459326300 62626012 635791105 657155164 429214002 559193041 687345444 927089542 711204308 605573318 553492607 770624098 262647592 822798639 743485717 704878726 776929618 980968131 360452909 584118214 74134712 382031733 657329995 476021816 36471295 543100795 186669620 536234544 979828748 679164747 363972845 788937795 553272323 176728472 249580219 213795143 257326921 740801879 226489636 759730257 467928453 305268159 355519467 320038580 495973530 559198788 589544215 578854919 396882093 893845658 654610156 244872735 716308005 636706488 927863279 94115599 729678244 691683537 851078885 972624686 299882002 628779867 262809811 723853073 118014610 638195468 132957950 846393228 347207306 75712215 969787628 129933748 342628255 285657074 42156641 326285023 362496437 779206609 873245537 908196513 805690609 864756267 653786163 994326224 803614650 16431860 492181339 351698816 814138035 2798176 793400223 538046726 755811009 342218981 625430018 511753208 288148235 709870905 689856970 941575978 830796020 296317007 864462973 901439921 891978273 914641245 431192031 344999651 387277433 40633304 935031797 94956628 921174558 169219957 210398468 886161370 755332984 881479208 978162065 741082505 38758698 588392488 490582625 904105398 96589338 229842408 90524282 58771703 620347756 909695519 453316384 308180512 449436806 268927424 216262615 22874183 556419341 913669633 469849190 250735296 385369317 78460503 497455825 409495328 443009588 971993207 556484958 584287549 811840863 778781270 470359696 677192491 994877194 615877161 732114733 924223808 359351835 385187940 956340795 218528272 196497847 693142974 451800318 651420784 928450370 353847594 14967547 824904054 768893538 906763743 923205623 630312566 797311227 970137424 602943479 267463941 331241780 633412915 649323840 854984441 518901615 973803389 488149592 557501030 695151700 445523555 279792642 185189794 409273030 389752409 251310917 321890113 443473898 852848150 91862885 471601177 114897703 388792973 452646887 290882877 882534432 422742773 886001296 337220101 945052346 535298753 367233381 970835971 931440412 605507495 563349164 934015246 95697833 111664028 385441000 968861499 593522950 308167381 466461408 902526173 795197977 187034055 178942360 797677708 910484487 759235367 30341205 624897306 333414964 274769898 379063964 7467422 776049223 43565380 368950322 502294893 752049698 481893548 941090077 584139802 290926061 546993621 234873248 783603580 354759179 82392757 987618882 817472936 428844321 91216769 808874951 855221490 161010198 891634862 240496948 348945391 293792781 569464049 607480782 185990517 565014123 944267071 559361818 295237784 837266646 999769293 147447006 200251053 336645939 9176847 703969565 269495114 95776167 485133244 246893086 945391172 45059222 415205063 774946405 977888174 533152422 740758630 737371319 778338271 775255739 903003918 889336345 691883884 311122427 693828980 303708624 657839401 709564875 670248589 621385570 986520107 857586639 767794062 839085202 316288967 672485357 49735660 858983271 996689811 137521738 854070619 662535205 412917092 947877706 477936594 459888977 633654605 286744467 157766532 607720880 461776294 250335753 262034151 669279815 52103425 30792659 555497648 361117275 339796021 112636500 939536340 958123890 741975126 182742321 960848264 538506576 110582970 10363984 781728065 213700601 215115509 91263446 659970740 313087412 92413149 474696231 269384661 189765893 20502662 277479401 253632219 82300082 408461381 377682945 912125497 527550910 80046256 563712915 406468261 513665391 702381723 958847493 537102613 355718475 959009563 508865788 55106236 330298134 710590342 832818268 712974608 651789013 235133808 622112843 379502533 58498765 602511535 147559725 83577554 136471427 108220247 75629993 620862059 978962364 205181373 130843297 487517956 313154686 639288439 255452477 498640723 504969997 961021017 775978720 957235278 740394221 224509561 392697136 853653800 214295525 320824363 443387409 775963991 478929913 432394500 223188393 667839120 663945071 530131162 135692893 926778568 307372746 612998081 897031889 426735667 785502416 119707663 876548587 29104456 430089351 19094616 802372815 339802811 559570227 776341873 99178724 465432448 716212313 93682288 193436620 516699341 583585726 93153449 282479471 850638359 867050343 541927345 506825712 864253204 76518809 707663710 929527221 510349238 618476250 578398661 311859554 551129653 600039917 717698361 501004765 947212549 463940569 967268945 974809675 809798363 400018914 162783714 923552272 482141867 93065613 823653120 593814738 804804012 852254367 635495168 664115830 816841553 889695005 735972215 253546272 761346896 763081549 287043131 418021174 808972190 100801970 219120993 259160412 245943920 791086867 778998589 65065081 643879995 243109492 411074660 479937455 511650228 300911386 557127595 646917222 771435471 955442826 33316392 609869377 310375875 764314761 854048560 527311142 852731651 98312989 135147606 447905593 326238534 649759881 23539570 52461280 53483135 284833108 59122326 789107392 338410212 913504834 602960409 199145917 382049002 511609432 555090575 175431933 581024582 219525851 633370318 657531365 489978093 588125008 119320554 916799513 966034707 894934397 602269497 49054079 985734447 727530853 494756430 677729851 32086260 266905935 454708481 785362099 144888409 949179839 368762724 584925580 887534993 679033722 74718670 736873899 753303826 749736325 326579924 744023604 578386833 71934245 487322954 725301388 58777603 800939488 977777221 572836954 483043741 476118393 617874715 946704769 628766163 117725175 457378656 748049958 983437404 891274654 174869225 365631663 155628843 802862323 209652684 546320833 551838327 544185531 47762013 111191105 659047091 964955643 323176241 829661523 286153365 749237240 920291102 441531485 869256978 731052600 662434617 305825539 165649759 507767934 49320149 331172652 735445233 458772689 736848778 120403706 740659068 660130677 475776810 521970389 474604279 550847215 171596236 815452512 986689941 923111429 56298948 443061632 926379469 848603066 366491048 725368412 842644562 444691284 402763340 671527255 991268378 856237145 953006789 152900118 894092890 74404493 974765161 376132223 782309511 740058101 803753677 586158263 429362774 668115670 751687620 237946147 143071164 425139637 757486437 260842087 135522541 93028183 771672069 257579369 445396064 646249154 629456951 106310477 476140232 730084154 925624531 336058745 785214235 347465283 436314347 810323858 600563855 431686052 907255766 897460092 31510167 77650785 648978217 884199773 810109673 459147199 515614903 463550362 304325497 338366276 743690392 224777431 165615742 871229107 889073438 187814906 436845164 59415315 997241568 901251112 673331191 616195496 300202162 461415109 183517718 819873271 498951082 974723447 59947516 716910021 454643996 440588834 756076831 727307031 413446814 222799596 881993524 872077362 750879236 652723770 350219312 952903580 102682979 821151409 977877576 545907736 824121616 898847029 555899889 341203629 863937442 41244395 176763359 794328223 857163755 720075578 459306761 135867763 577665282 406016453 534362274 270354670 460331067 319968881 814789153 475168533 621083948 807574885 33650489 703266350 146638761 372293891 427330016 318643388 123597767 574630387 38000203 541237126 920885724 852180760 471397103 716087696 595205244 787997592 705297024 966134815 25627773 151894743 706086389 134399160 69203699 246263931 296804994 239437600 584813875 677628521 87490971 86443869 655234771 517331142 667778294 124510130 81922983 287273974 201478281 989721766 582900164 851946142 938424455 664884989 128155008 446063013 944754534 885588924 97178480 739620909 788147675 822918184 413446247 36231582 270595290 847311302 571265404 118350747 258765722 262816860 383266820 41283082 380317071 975120365 797534099 652557072 811835501 581507776 768940542 999186705 945726506 773344601 80910683 391853747 611671804 821582973 541707774 376789722 718452566 8036145 669241980 764668588 816869358 554224314 947915179 272923022 331089849 583005342 116534431 16919844 801612779 712548000 912817838 967672660 625788923 46391495 132849004 218412099 198083997 625708375 667928750 85770837 339757253 107712213 608448650 487375920 246053289 127400454 133953364 278222520 798787263 722087407 143852962 770509076 394386618 682873813 812418120 376118950 893800592 798058814 804103259 456153878 675787126 76392941 760189233 802432071 777590496 458422249 781863518 83021407 927724165 586577270 291999159 362177474 814600281 786465049 998004050 333185814 465688720 943778199 969518467 653567296 939215777 409885686 448241888 656913764 632712767 142492025 180051517 989833960 553888096 120316839 402938544 80001905 262689849 652599876 691693453 315500771 641791039 488065877 54115433 37883236 266155815 635877663 259947801 171419992 133865701 268965927 910139315 499588965 322382256 88569650 445182604 880499824 444381180 229694278 95553080 916968350 414378621 806593446 594980236 459670099 167412265 37541337 956537245 328904756 621229109 781545379 648060865 705128232 24525334 644577545 855771021 874528594 388288385 984648784 712731861 349713687 613107819 734509566 517688750 830332190 832484617 136843990 362153069 921589322 587247567 725430751 237556648 843695552 830267764 450441309 304340532 875043558 83798763 687062484 925267748 81602401 876950891 375823372 886613455 696504086 79540327 257455367 892900810 755984425 623143317 173297419 672751337 379991296 601686762 842488989 281151809 566025791 939526811 692727939 890048296 835034828 89394972 840906177 555977522 228560844 153442596 807928732 564894260 708041379 246545831 942263705 341814084 340269303 165586905 915729789 576838582 701440685 157019952 804308301 198090528 785661417 71855457 703281999 824649046 491653905 583737442 645812230 531428461 550482121 758110822 471242809 468106939 412334584 967899618 513191148 574641876 694020032 712199053 15924068 974373262 943055241 524520539 343650086 252591101 281959670 237578112 240149495 235194742 107766765 199638643 137586653 923241359 776154770 701510375 265905435 499423260 708303691 259644626 452913208 216878899 894545085 413782633 596153336 620384551 700776396 176412705 903137632 806661264 424724382 916897455 287891381 578961472 371648920 328148744 743671932 925040975 347114334 133751905 156321147 936428815 503374038 24376878 190948533 69391127 869427236 911589926 328029297 294707515 164470190 295558204 559353139 1445265 125930009 337539238 70278592 189425773 758526537 990650841 762388765 807210084 373122916 327970442 48958607 720139340 159470799 859306926 374334363 584773945 189868079 818703482 941461511 32570497 830558568 574007395 497433047 629980600 411179167 901349149 100561744 53177523 279530042 732371103 83557622 268308872 502997214 612467484 209882001 92373643 334591344 491279114 431288355 152955986 225358612 305722142 797502450 335719345 800463152 963242061 182795396 882166717 633661800 87623628 244348828 762795468 466205090 472584464 288947009 189143410 820787203 838133198 32218039 410756 578609904 85798906 226216323 306701592 86567181 171056075 856864618 916016003 935490879 248948660 295326322 399073368 548291757 323376236 873801182 131673710 169986234 765532902 934230837 628281562 406339339 403517528 223311931 180753648 75392390 378693687 140723445 901500485 82675792 198414391 642439080 660397231 269981134 354209871 243183833 790718530 675636900 584681651 348652365 215527251 437441976 835068887 755088394 356955256 869637678 18421362 905699923 182880389 167844204 61337463 958073263 859018384 502576407 42069020 825541602 66257389 821609235 488243158 583048945 438394417 872076678 104457306 324311841 619892018 218818261 940367261 759552760 40743172 22494116 245294548 442329401 174389244 354627289 736297843 108757227 420726960 672329113 492025137 977752914 620078069 925977928 187307009 104151538 860262110 938378124 276242201 335753362 311973059 348441161 98377199 404784951 502483254 54197157 969112630 769139236 988271630 272346117 156511204 788724191 335096159 385531918 201286445 317750574 667220351 193632420 758770312 303589141 562830594 578887404 104426153 928779481 584256701 344158797 619221124 351171583 807534022 855871082 730124112 234210380 370737521 106911016 896211584 603145669 288225620 602517677 503807434 668322480 861808963 987173726 278227235 103339920 368936787 994085856 704557248 121773356 207033818 394963735 908782358 880089224 868924268 61366825 925542106 386624745 469574367 989279866 619956481 614809044 446082375 600657328 132662463 935031054 636708857 730451376 656069514 178065053 574577291 831125150 669626136 74044100 275974865 186016480 175239004 864382986 578849505 193856283 241863308 26655539 444239119 398996531 406685981 10086212 160586736 623829838 325797316 712631170 77205594 547385809 451631478 168802674 288953185 465726816 654647655 649189082 388174938 456325601 767116046 630837693 183940827 882509689 499930142 187092066 561833144 547453068 204470926 784253261 499042823 562516415 619372177 572538691 253454620 614987257 697043613 606141257 333831308 49781341 301334887 2000548 951511853 876250705 527162340 620724441 860005396 709439865 109582153 930722222 829714580 47007163 919219466 618366247 882530372 846021948 72135902 189448072 871252217 870480480 428276408 775544664 196732102 754266573 843281615 398477148 221369858 324981863 372328854 8630935 178656066 268017492 753095619 977220175 872272730 584764921 937563723 22593034 416230239 167946235 517392995 565837707 751260327 781953342 883983232 810460377 344342726 439385576 886434135 218311224 994164626 661749853 449249244 308400173 897527583 988322115 432356166 23581053 734775234 267768191 375150600 589545262 664783377 816406581 146640600 596457603 861920992 338040011 744727211 139649795 162042692 89518822 351238326 947556978 122600083 305080426 607395950 782683861 942602849 870970237 363436424 91105905 791986820 235249795 965119993 646107595 27168016 224598050 606520309 44412840 166600794 276940095 203209203 296075022 28009208 571034367 63630502 315597632 731453374 555419846 786401029 333699013 908901314 703493177 290833475 395159649 477844056 217911103 903123926 43928345 456992021 665869819 309146483 330652722 141991375 880986834 336192783 767471154 365498522 54529643 140295390 226050012 413023692 539671977 255953751 668725303 472879609 569101233 521174317 591250566 875457014 136675817 409389399 976301648 124771545 57124342 321377544 747530585 723224054 427748285 461431734 594127783 537919714 296073058 263063830 329973117 182514035 540860747 547732253 939060065 351757757 833806364 763123712 845313049 403895830 953212091 405631028 771018921 905626386 123837517 188076141 742630486 10122631 968177718 567212450 790406821 729254024 100338204 270069510 632449371 712195949 3307492 586598928 443963517 975384008 608706482 817498227 1693777 257987440 795264492 149621797 371848026 934338682 673370422 631702875 804642911 797125433 543784054 774505610 795750500 733907525 388611793 741067879 864575662 967907440 342751660 599208422 190165698 95573713 946600107 834672702 762381413 329960125 749223348 881582818 814660509 26543047 798607083 213634952 387811501 390546374 755107510 576270886 641002524 742521039 13564346 998031087 731819182 533475638 540690651 912791641 367385448 681874320 592825151 474210585 202492815 493994163 212977738 830953507 122769064 961283507 4704675 56080046 295557241 57949157 741808428 780396590 579602181 959135455 829069581 247291991 32243859 412648054 934572457 949845791 957431719 959423165 52670374 552307388 339307270 965074443 893890536 700365729 93430197 283669749 240474517 14212740 275921145 602920527 858182162 216164442 799190615 166437678 192602371 515853911 466668949 248192743 989107278 682489330 876085943 563555600 586431000 956113631 317068289 602580350 72381637 237530386 289423354 87938117 378481915 437827777 935475558 478482874 832653727 953581154 229542731 925854834 687347669 174707880 818390252 646781763 346848003 115112585 113943504 725606722 420943053 210071866 433979834 350906306 567465241 618601008 300179633 489751130 833164812 349644575 537977081 164889311 229388298 435369470 987837719 416473957 890901434 46411520 763273168 446794817 766236670 426193052 688349738 427419657 991676414 719669637 106953064 457969553 462745372 278173361 491629841 151771118 354014464 274400085 825302249 282441846 186710925 478695654 487688949 826397885 592840425 869560601 897950586 836829849 948799865 528296931 933753597 745939998 774481889 23242616 365826627 607727009 422548743 707295311 161219666 101216184 551773199 550038811 513301613 335868727 432752223 767402194 813328411 488558900 187379100 546652329 746189088 735337219 413606314 960634901 567852417 690403897 393173167 461850315 302018435 23174828 175072016 196358848 586337196 652938352 23833457 79617065 817504447 983283163 561343672 51474811 616440259 766168961 362182666 619433834 610312699 516242487 356768459 280496876 612012782 771473683 968324769 692945719 14461024 980348777 348907888 477367742 326910039 724614350 25661278 343947831 470243094 195138328 303994064 445422231 570812195 117442652 963559530 326724371 318005572 86574829 135201554 124815904 499710589 650575202 161758189 712925298 35820563 354500240 475073632 953221888 993203083 33166731 905122830 827980541 205252778 506407848 625355487 439221727 28414837 185823868 411107574 525001564 542379570 641161181 694700729 857412967 69094756 301474272 406124237 880023094 134262738 887357145 72522262 456665150 523496064 840060253 464616890 763034675 354938035 851679809 558101789 388534540 402663920 425571995 968697829 256268796 136352252 103876032 567421431 525186682 355938525 415974723 881646967 288688697 687667926 492080380 29922507 206852399 920102510 262062845 293558424 980534673 9991273 101853597 455488450 256430548 986044876 146017136 447911279 596960941 406418908 243511628 302083332 487310097 787618846 854822981 644669477 432986165 723336791 180476849 444410040 955945357 285532813 183902500 943963361 462208208 224662276 622547059 953608455 924803057 261001793 147762611 245301708 62272294 913875209 562488634 872090136 403923172 757360737 548386717 253702414 242031584 955471758 85631920 891636756 971095823 380072981 248281224 22388430 34831782 910446524 716085627 92569378 88422170 284092039 627942941 284101428 679669023 24124602 809259075 67215723 255237036 593218268 387659267 238345322 567209716 343829425 832430001 710057750 109012845 146668607 135448546 87640213 781696973 650907593 508350316 672364108 155347719 267169238 45119844 637563360 102731344 209985577 104925981 78694197 378090783 459790537 456788015 788332657 227731752 524320762 803036780 853775352 959604832 850344513 238645739 102870640 280021243 609078883 862561024 293994686 367446383 174868326 504934465 733691398 425365106 885715085 513166466 565166510 323346679 775751519 916910808 484738907 524027444 769273248 968778905 867702001 747021726 949860181 774176602 409204374 769464554 371473091 293467374 156935854 226250252 256952431 140026220 953101279 645269307 951781662 548993321 85405966 816745194 596158934 956196536 281272160 870799312 169313242 655254769 968421945 260097760 502349489 323956966 91695934 841468240 535565855 743930862 770630742 488914069 315837481 373388190 895624612 293148260 873884436 561756617 452196749 541864114 907683686 742111879 972930232 329136564 522636770 892666410 261313032 312374750 835602831 630224713 62451874 903070183 24060848 342273208 736624620 291275458 797558220 267296141 695665035 966213029 326585767 157121820 644759908 581797382 782261575 434590459 295573915 285440920 277190895 640588542 902683285 232153681 939802917 993328442 466225913 116693606 268900527 960926724 483447722 906171979 872004241 731499507 436430798 657909431 502471184 957897689 492856009 223047325 191697073 112490701 758184001 968113972 802186297 125462051 46764059 572571631 763185325 983199601 199663739 998406276 739622994 362354827 299860935 422697704 503547310 557585286 788776099 35300688 36891013 330278072 876186613 828907057 726263004 815228085 54689506 226200640 538333432 302939219 687578831 8966258 516053854 530981542 551113056 653273083 737630675 555150595 248568954 46178898 651728477 146640128 505109572 406563114 334823743 879022193 862977825 673830521 680585984 583305579 30360503 964801652 766365796 22855236 792663274 524877200 2538608 924972945 518717920 627772546 696531049 304693797 677437437 816377407 981271508 758564631 420119784 508413947 568399478 148878268 318526595 82591533 819749973 770934696 546503926 719879560 943806389 170433200 137764516 385099523 600157467 137770218 673581107 690234321 742007628 316978858 995449479 148554856 830102349 127949445 875771078 209396605 422828643 455176017 116468309 536068613 650774547 617478690 879386840 41291573 571345955 805279822 623335989 891283074 660369558 675007849 10055313 372303264 250375091 163916616 438275152 895711878 420525054 64347649 874427928 645677415 932038716 367106024 360565454 102010553 26742131 512404371 907128726 850949425 344973030 352052182 838330838 728439748 896552988 118947270 828685618 490371495 830991576 354256569 933300112 247171151 215551265 786090051 911834389 338549617 868842299 926687801 110144549 639680769 67815339 97276593 687753062 750119734 175376694 852241919 615887805 159732867 613423330 142997177 245563470 944315806 494840818 273246643 486974079 645521788 441159661 64243203 357828597 952571219 399882391 427280637 411708052 40252565 920873972 841898038 95522434 530043130 585382476 663325571 593813540 462285942 8889889 388458234 259030046 896970558 271728697 362488560 352753494 370608070 67820442 978604537 300200688 910041796 391905671 605716714 109685842 636609326 828544903 615322328 630006561 879588407 11547998 205277977 554992449 287734613 105770257 25517378 205134040 465548349 645533413 140011303 989214795 797573348 731510624 260930269 624569918 124468606 260108101 835360441 159086999 870269570 677237659 33698641 883602811 554163876 450220453 680129914 680044878 877370072 66141418 306360391 544990902 565945940 111654702 11253519 410408343 476340877 781085302 124589927 287989783 641843512 70227720 51937059 207063707 195822666 386474855 523497048 906193351 834717176 887577178 612668764 881982081 591206071 940479205 53527747 225170926 128713020 574880332 20410722 477410162 769841787 6268439 201918543 340077747 988882347 573717000 888769758 864325526 92729407 487258661 770718885 103876159 279775213 305197235 667270520 835350292 919152298 960052792 317082988 831776954 490688683 45632888 484444375 291905557 806578277 18397048 796774477 786708043 428880013 127326077 532790948 401651392 267577367 807254796 720236784 627635482 537726522 236554218 999815302 581691710 431026793 778426396 253136124 924718928 736136795 508705256 369160230 679007158 72044035 571461074 14749210 161205525 154340247 702595743 283013419 530885713 609792908 216770900 499267569 338284688 398130327 999087414 379226430 637321527 166624173 724791242 437586474 998210026 92387842 588026581 496291335 546205839 627295501 258584157 253337196 243636554 115475585 234822310 24725805 325958785 681825365 515502644 483680864 846895321 779323068 536334286 31005273 562282807 944413740 226969209 130729389 990810303 11113818 881565560 582248242 319048406 750099259 524020817 537449468 998355747 395281156 852640458 965018465 623899017 645339689 355481318 477490933 181625901 371410017 217077996 877658253 48098166 256316831 357159264 988534847 329352711 449021978 166998279 465511007 507192005 647727173 157231847 386384771 644023510 266595030 977773635 858047103 333037983 483694786 363206817 968153192 25988805 983251774 51361223 312130196 661073964 748003263 960582073 330239127 575693305 843114489 27558076 261972038 233221267 250959331 96299349 757608375 975211165 818708400 167232073 310812991 988101885 694812119 387014814 404471153 271470295 904498443 818030999 505975076 291691409 12496450 424298171 593768301 798800079 58176177 22975438 82746272 533881976 123630029 115981524 826086738 694319279 705498443 859188245 392267865 343196633 576846624 645549587 546929865 428452508 140249472 291136404 581350647 232188381 986642146 768801182 178527609 759454912 857345529 774393204 495820067 814513835 588469691 385163421 288913163 918279491 9416030 480014045 512564357 524336237 483581525 439207993 264484134 363598925 733348438 477013238 631519428 435465032 675985237 292576153 507707763 277066756 900499849 177434856 22372232 703512422 244600678 853941735 453704089 474610835 113318816 962598874 203264635 748631791 954127662 417664072 566601025 495270944 674192195 422312693 230896963 273862667 556772693 842953702 18459667 287657684 764147481 677426017 440193416 515547872 697541252 68860905 929042870 719106774 298649035 665077829 764616435 958846873 113838947 578781561 925192659 580557903 349215744 915523273 875048747 811834460 807266457 370706876 417716753 268595046 729269345 870836759 199636953 407472977 286734543 582876637 751988249 102615108 28632982 983279956 478688421 908015778 645222060 6313218 271401874 268853520 874065478 701125035 671855926 459598452 526943961 954067540 657521701 106503155 444847385 111004738 628443957 539270386 27762685 416153338 684870522 594039573 513887417 355905601 216677449 714142273 65384641 413966876 795606328 512662173 480587211 882369745 7309851 361776780 401460173 199541988 47798024 899754675 366739194 752470810 320660051 712516601 363726792 744975480 16351889 510935425 2807531 461604419 137512600 788680880 348009306 786074112 425124732 901826860 23825993 133275508 370265234 935247066 495284012 613012133 950553968 884432351 925981114 978854871 897627114 51361951 537697766 168086414 631325206 957510592 796466150 436741777 245139016 881155622 58233392 726735845 76331798 247795447 860811639 980657869 329485139 414691224 475857072 108183247 232765975 239310253 468856594 968056753 331841204 978057500 582695953 18864502 249086145 96698378 318498657 763151461 483621907 216227035 825407225 31032066 503415997 574062133 734557452 529168402 64154390 54833405 308292625 377088667 596242355 747403863 962390715 89880544 749448552 61316009 143830016 306018663 252262218 973155991 132161813 871061750 488064687 486588167 986304366 929706641 397604139 428884766 443177666 172330109 191032980 30837568 954424069 700972863 72124670 796598803 888994923 40563100 897468094 877597308 600529770 783111322 928113258 811379103 305814712 153665404 889351894 456333538 49593160 403167177 898671895 522740714 181779536 245432132 285738627 901279899 84428613 598706164 333556910 36618011 18878428 171727901 852350318 331474382 973667337 805721157 208788183 416717147 992171523 830842159 693538622 161944228 835918397 878560226 714393401 434364113 799985006 871010721 378144156 731782981 679935625 790061555 344729469 159990182 668755652 782601884 90490928 195711448 97420692 888335265 493659978 83419649 160202926 48912711 780491425 67899526 572874247 36678163 556153417 909356555 530810836 134697675 955193496 817831286 617514121 982682227 370668578 397605867 18866909 795888719 739749820 562863313 935765443 445473254 528478332 26932682 575766130 640834300 755777462 789161150 118851165 181560726 53434623 936054224 353940282 249681914 868057133 989086566 748253438 180018347 616749908 680393764 297449438 36618352 342995146 573958896 613957198 786878541 985283875 951536879 309231877 268610438 582020917 358699909 749571319 498706338 717426195 532824664 350258520 841029222 942193429 367837517 548201886 572958677 277603277 736550024 543424894 647451701 736497682 847388783 389768942 628763148 795317753 15254439 557585440 557536798 657754581 698742036 617948044 831654255 5107774 14074844 603634150 946111303 88472070 422501219 927586339 480145704 10665540 352865103 19658615 309378776 865196109 870656901 745744217 126117468 107060148 34082857 320437628 761728506 450374224 420706209 812975062 477586998 563071030 947693714 251337372 834717652 156761018 18308576 744121411 671047131 795604337 60224689 27619712 543347088 835374641 545667178 721644872 376127094 942339342 555405999 207987920 884702291 462168925 751560038 461886348 637298989 265890996 683376307 670870323 143895880 76934888 717214460 921466808 249376040 134807052 462136038 878928721 590746516 650978423 271380822 542724211 709055376 263038142 18815344 215330259 632798306 655185845 712687769 639632998 614268813 769736817 135421048 124654433 535320280 470795847 429956336 78062137 278364742 768568013 391144486 498317986 456363038 287620568 995208321 645144211 281094372 672481660 339168419 766001215 443250013 68066318 45916020 339430940 794651278 654083619 119182359 653554911 522931645 805063825 353059826 592975229 566560877 259006573 947601066 926883115 844262501 583581962 409842723 526727518 35584937 434146815 376635522 669124555 36490366 925008673 323105326 259625574 414941033 963835012 766392778 185682790 858991407 282643069 392614459 897950014 822777045 481819554 194952360 285660836 575485857 212337351 205603956 875732622 464975639 659575553 880806212 792832047 621421819 867742630 920587519 835308285 687733588 575446602 919306695 820844204 617840230 204654787 716910596 782118195 608325303 279194405 661628505 698373318 550436106 976302533 791029164 800076249 558146661 417621305 995396897 854259491 980039694 519455317 307422238 581508503 958487945 249633327 130566216 26682475 3964571 68493339 827430787 588680980 487781705 565528494 971607029 682522951 680675800 341192382 406025219 145176313 209486029 195293023 945842257 534941279 198041326 812921319 929859013 266227181 53371710 455060714 644561796 758767194 662654212 981019965 172664562 727444633 643529156 20064758 585806773 284200416 97509187 880927849 869160369 705867172 509437830 152294955 219613965 358544283 881768659 188110098 701487147 964893623 421534637 786746675 803554227 543649840 514305243 165658849 313166472 186399610 158117216 61972147 590848463 475721802 153714307 46488446 935991535 895136148 102831048 718706774 452177803 553535631 891012853 594278032 573393288 834573998 552343565 18065345 465011469 248455591 52075862 799188927 864607356 883470703 455346518 514054815 815222909 169094203 965925585 515947701 616117747 707567232 959657163 976039574 224608772 821411059 954645643 976067863 336125460 402693256 613544854 665975630 468467146 851862646 181594031 752774288 124879112 195153456 975054556 759714929 744901622 638688109 774659939 178780870 198925047 390483488 717475784 434247076 442287792 597062271 563714767 194687841 949622280 867243263 486390143 124526225 495670306 514695253 658598173 939740170 557684835 224831350 888135980 841812192 141325937 974437782 182815090 6858857 665646129 71151660 959388661 701170745 352208840 735797483 922937081 222173733 685517722 236471242 608540930 748489794 700885069 496227068 637203671 834240742 806798533 843684087 941791100 413598374 931813928 319548016 160052279 418905174 349577691 59313756 883915403 601593099 58711426 33208816 168842303 754036763 671095555 991420576 281498454 650380570 14842499 465102883 262083095 685428701 406204518 630841964 959862534 162820730 733075794 725499314 4081896 263683909 480570923 442958952 133098690 47900371 653970968 157974340 21104602 319827450 303173755 20709691 194856883 882767311 205015292 974328194 971029012 984401829 378159998 878394254 642839809 4882196 885840423 215142163 353667263 870650350 844049243 495996936 813470163 63866442 417567168 856222881 250428162 613821564 870743611 544944466 133890385 817331994 517261296 495666385 157234182 474931448 911493189 287308307 683530917 356808492 585429727 379292749 523000562 274621705 111410082 930536692 138152692 659996199 735505588 37686717 656921327 916010584 874313849 893893277 987118953 396970931 981171608 150516168 895683365 366086285 172088051 454283701 561891113 63704441 400028594 423474967 154190523 811414863 232833336 132073701 209886559 389279009 756265771 338986066 144069338 499249222 322197871 315951316 150272817 139679827 719530026 918033952 351205545 815114011 334037441 202850346 586460103 29221046 355241176 839182121 514982225 97112950 741150293 934586769 139620938 949137394 297279324 311922710 987727353 214543614 156054356 869867439 465226722 820134832 873513439 947011471 388273098 76557148 601036517 317755180 359722934 210147224 117338249 522235451 180533228 962053176 344184113 463826609 846087407 779541329 1313665 142671043 10798470 414786360 751703135 747238630 632255668 7675524 445880560 318136270 679173568 537806343 886773400 457622130 842638382 803898584 791863549 774712837 859738563 635494475 430924292 93140478 275394693 801348598 105951697 965024272 569208503 701424557 791058122 416681009 243740896 514985861 264991123 526576790 266701252 544683988 443895059 539880884 804905575 282914094 489814124 533031999 196849680 80522345 388481798 389560110 289312324 244115097 165483652 936757685 814189254 145783571 870027468 287192904 26955676 553474925 220682754 31372701 752616204 501029755 54923916 271250602 87723418 180898642 491941135 944485026 472567306 255706952 471959151 361036283 924205411 396205042 73061842 720220010 933777130 281995811 164385437 57631715 717908002 369114354 477240948 386731677 27581137 695769524 902044989 396789004 197039357 572490237 189375260 587690212 112866537 98552738 913648759 36847643 982227228 90131641 589499379 41579751 863483482 219328918 413601397 69451707 583305128 338433230 60434721 556432205 517669964 441677111 198974300 990656146 928067017 369811429 30278349 215551166 882122726 637514798 637886295 919563592 828071590 673232806 273769247 81489892 573464656 347580450 354376843 144469126 3813224 563199416 362598464 539277156 990438579 12119228 221336355 843350772 581944630 471781316 127560792 401972713 552753207 700425124 465728837 812720441 140916025 727737201 489674638 231972377 163988483 357547649 124839194 788070909 941017753 779520616 935369739 410729116 944368960 621141243 751273161 144031210 767157373 92018256 462817271 615800859 141131541 371398331 282894458 562577318 386887181 320173778 237404025 284169022 912410283 70221673 829921879 456313305 430889075 882130326 945209529 685306540 725563177 527407277 719351429 976928044 577874644 938263107 902086112 20397838 829575096 912708653 962013487 396234310 868393051 624948353 280507670 137462027 761294208 873768340 996686459 787662289 837050413 578802682 150179970 988058956 137211816 723604616 605509265 502931570 383241077 823875667 261694029 531891832 819916121 754880177 777341850 313763027 482655577 395474743 965318302 386242872 155307962 648119737 213377470 724864924 72728833 198020684 74062750 369791540 798117364 179791685 122400548 717762421 943213974 845334330 646079349 839382547 472695598 780828928 797715957 983380740 815694400 2397610 62045770 329408382 352142481 426658447 504394840 646047988 655327270 345483076 663725637 100770588 314523461 926565277 990952054 213373419 699378801 661311407 880519056 595971990 315091057 536142800 261592183 731328145 195793992 194515604 741172816 665306003 217044285 881425616 187425410 998697360 760191188 962783130 947721904 504436156 736327890 214150214 151404735 440200589 148732221 332518506 564168406 542234809 72430168 408542170 531604311 551595315 215204522 370262699 375206634 812048177 501662966 701504307 577815666 444518695 592070211 311320070 174248213 706883532 377756117 570383354 172917303 260242964 216599858 130803747 261735806 997060915 439268381 704176086 414536399 105822880 141901468 645911209 268070991 305796110 25161461 554418800 914993762 935802227 107935148 890234689 296782253 357325572 273839493 964415343 65648407 225467702 79266183 228464530 866141122 833806014 84036854 9723516 675125526 349514385 258530648 798214469 1319094 220231652 152332400 304394047 639522952 375275051 476637765 819673089 886310065 854394141 436335898 186564959 233190805 747362477 135247734 787709295 829962714 493889809 417102365 774993029 144499812 37946558 401427988 45041462 755833433 234482793 589384865 530444376 398142750 125291271 437399879 359304447 190041175 980115917 896419789 591504513 776191978 946353200 342916150 366850162 20375548 302729188 200532169 761903783 8273137 217210080 602889226 372191542 810930543 705843031 230359742 432654963 479350362 912727999 281173994 49491700 690418905 788757709 244329684 487493517 957057102 327530870 935189247 954899795 727771745 507549423 117327922 502858140 214895349 954756269 930151537 162093564 153232944 530612325 360143361 817957960 823584374 393703947 851203431 104017046 350529645 588181974 285432168 225809211 212359418 950881337 336130825 596170 535104833 885894123 146925456 29854234 98122408 954899423 517041792 736934464 661700308 499899211 773158816 699808400 126751657 792401828 294302452 834683039 54854477 396921502 114770113 949079619 681728036 222963760 413163916 135086992 517144788 817736846 178816539 306389723 892637250 183113772 426214769 36657850 817639315 737987009 665815253 894748673 306958379 375363648 948067787 875423174 569696687 146003679 319731736 856384861 797153798 571204883 411188161 100842075 976068947 897272465 998177035 840242326 310547963 476461902 61445243 870141474 793675941 530108287 559422167 208441172 202947124 871609240 477585186 151183042 263244749 201161808 503213219 286722881 789214934 819693722 803336414 587950052 32088308 592440236 788923288 68431363 803873292 925470972 792718038 449931056 196333634 146794557 785660126 951781698 504493052 981430117 756803635 344749645 760614366 51003560 511770524 456019111 895642318 661387901 402835996 324145380 624274417 527416728 988584698 484064729 518405291 648226541 132837818 577667740 597654690 262278067 531659297 298204289 832294843 812165469 64050229 173308702 797467674 141169057 635482681 709469255 553471525 596648052 857663668 209353746 953141376 558646283 555302505 635780306 229017618 18109147 949029471 335258910 628539389 992370073 272727002 947142603 468206505 940999994 279537247 399652333 641055417 310120690 589936564 322103513 611020563 567083064 779255260 398926885 409952987 272346303 803368222 500029861 174909047 457814653 791610877 92804463 474602124 859171239 563467072 696183255 411377150 534279346 176243179 3480946 173255155 314882131 457813315 677027094 216226255 504116095 166972622 556862423 19537209 467504490 195792975 344675082 166241300 515963787 54071757 56966725 305715333 960741269 426515851 387959132 683157746 687492479 215515152 286955109 81501696 713205116 161487904 501233076 873041555 983959554 543708864 855390175 147314641 652112326 747253046 432368057 416697631 143709629 496632581 358868570 450790946 997371676 436305907 145698580 566374589 945369943 994547206 903160190 935282968 545692197 771527554 68416365 827223958 519533433 704412908 3883252 196530909 119776138 744975113 851839082 882491346 54396619 922319582 103096932 447900569 680330738 502519729 32122806 362512280 259229684 886209285 585352053 694734195 758534662 915700385 238252791 943361296 605742493 420596361 440036816 560428692 745961070 824837378 521375190 826224740 181459053 44576913 770200349 14493988 393811409 609588219 654134778 585265593 636081933 855169093 761138947 283317066 791520471 148215477 23901452 185676602 730520100 58255566 185102122 244452654 13046313 47996503 623342771 856431884 419020891 627977044 924820283 3835129 283029615 992868362 344534680 640238938 886057050 607866110 892757214 965678803 959105616 105791222 558562402 379611210 184027336 265762549 661940666 72908003 322267253 673724994 451332026 220848644 598473806 361108577 628607352 904944466 332283270 994111767 803828808 458689713 384067987 935837801 540563391 249926727 620001322 135635100 924521395 593804409 85486912 787400245 898165304 493180395 362591497 128493562 888159652 354911619 23972860 101356270 231339147 320703078 843123916 640981080 848459202 600002040 466048112 786676156 927784031 211423711 363952667 986084063 15506870 530656255 293420355 600000454 397071708 398701694 979751325 551385782 314985255 628886465 52778270 923523125 457865515 343219821 104492539 642668807 174349758 601044838 940989097 807616560 621170036 182394321 384895965 933585655 78957347 668804373 255313547 216367840 202623454 274799829 665996777 108434864 782366973 4078326 209002349 670291309 590123538 357495710 579713738 545834586 667860212 536917810 681274870 68813566 551765944 692982359 370596646 862539292 463382193 558418929 888628943 97041595 993454711 42695974 792797606 327625759 783115740 421767514 133484191 818599885 422815223 121296435 205402865 988976523 859712029 277268374 126989839 809217884 920926177 857499559 99538352 248285575 569934106 204137164 889998279 584614031 959711709 982843306 106957962 191344955 1865854 200579877 767898734 523603599 552739218 302903907 682955304 152533968 677026799 650422473 489856172 786297988 378357417 692813307 62307121 627544686 785031957 492385759 534073643 992897429 933873865 967130778 481932366 476526652 800953754 691430544 39252624 426141418 142071195 186381414 786734631 713672803 355622691 820517635 247933318 21058988 672150215 891847050 679456099 545476619 165528923 19782497 67040947 544031491 740658164 759784492 734278826 129725018 5195239 549169105 11750591 403311638 100147914 316838517 575522470 943023227 734013042 502794876 359906387 936328206 598324979 955077260 142385149 130945940 943123618 984994185 938825239 887590418 345161236 347328153 693724503 899573454 442553375 672006945 723719858 621821771 896344024 82062022 570710877 716709712 54312082 930551148 439962829 974118625 59213796 508014393 355056822 275620419 882223523 534621841 454586127 740398075 13479395 349751322 520615435 826163918 253101817 190606009 765695521 389832641 944898939 247151506 647765508 810925082 554251325 559446539 178884266 202014044 250187860 15368137 34706760 784867150 371686678 778724016 529940819 323010548 5133847 440495334 307160704 930830227 951590189 974942415 87265476 838153904 539402860 884651793 867479635 904088593 844013097 492106897 22474148 514121401 303787770 842178676 28302698 448409583 245838260 421020190 792707227 165621559 858790250 288403252 335576172 415339094 576082291 600240541 520150099 523564881 801945955 692052860 364421122 778787437 739973392 881197366 625780081 942093871 260995214 596782450 729910484 663726429 608654899 24091923 919096480 740752634 647405203 221793086 831479177 545491021 605593731 995417433 571517574 905665754 351562009 256922377 855116490 249503334 254319529 972905011 707305931 523005174 706477512 682129147 578609470 268603599 963563852 757383623 981587224 827481207 979496522 607303995 159744910 592212145 838716693 749986877 356503317 600111236 882015812 795218418 501461089 656239924 304958636 796853694 321450089 509289542 953982305 680810311 343405152 358315903 558234040 571949170 620623804 798973157 986928966 246775651 826288179 516017339 964271074 524402304 441249208 38266248 622202782 114236525 717415553 742784527 163213009 980335120 203561731 347920727 148576783 226709646 588593650 22879908 783237165 332012876 974993477 440634747 849300545 204016110 820303663 594161570 467832224 742975066 775357479 105766172 412103134 655394996 576365280 731969584 532027600 706952546 179609936 953839457 554643595 544619273 335443885 626989430 712915301 615369869 723181162 981428083 139593202 339740436 716832828 933440669 413523208 732770306 359445018 467531386 901423547 393367294 376662840 51780301 517158753 470407146 970208522 155751325 207610254 562089198 768992071 639045933 646741527 236813933 66393058 300264452 872662801 811723533 139375889 519422182 306780883 446193074 402117961 748792536 687555055 385139586 351540031 801975071 231451452 972737506 779382248 842950465 897793486 723934326 979699321 889369857 784372987 300074276 50423911 875120742 820384343 568282641 392351078 314334644 439315383 564613025 984063853 277570928 994467633 416133754 858224815 696772191 660967705 509906817 193925026 815841670 231700996 834532314 467695868 330102827 238390472 618676459 889978288 812495313 737077882 433013336 
3716 5455 993
7748 10311 1281
5077 10441 4469
7656 8868 774
3729 5469 675
5441 7630 119
2696 11608 4945
1261 10547 2153
809 11439 8465
6076 9496 2487
475 2231 292
2053 6793 1876
5932 8787 1628
7122 9657 1796
3725 4474 243
4874 5434 385
572 5646 2588
1793 6679 3376
1244 8723 471
3076 8917 1091
4561 5685 39
1251 1271 15
4296 5454 609
2304 6953 2886
4315 10150 5029
2012 5259 2617
1008 4269 2523
2008 7314 282
2758 6939 4003
3351 10958 2442
4732 6947 251
4040 6227 1940
7121 9373 1740
7163 10118 1402
7791 9229 1196
3354 4776 1008
545 2058 942
7905 11601 3483
7453 8492 144
3560 10077 4352
5278 9297 1093
7239 9094 1772
73 411 160
1606 9267 2559
8884 10749 1181
1807 8883 4615
8101 11535 1750
6242 11060 4767
9138 9755 328
6542 11136 470
7087 11487 2244
3657 9271 1055
3483 6649 974
3728 5422 1490
4421 6491 1884
2018 11380 6098
2353 5265 656
4311 7930 3079
831 11089 3002
5100 5321 152
2343 6845 608
3724 4593 756
97 4396 2396
3248 8189 3104
4487 9972 916
1842 6526 304
2834 3162 95
6116 7078 260
2572 8862 4381
5596 6179 241
938 10850 6528
2564 10623 7267
9556 11460 102
7982 10836 1617
10160 11473 74
6232 9486 226
3751 6030 1067
117 2191 1891
7175 10340 2991
2647 2898 193
986 6946 3187
2854 8384 4858
1610 3765 568
2336 7170 4086
863 5477 3761
1619 2242 270
10083 11401 507
6389 10873 4247
2352 11644 804
892 7266 1736
767 2383 1108
6116 9992 1199
2328 10089 903
1195 3229 276
6639 8718 1174
32 5105 2509
5044 11334 1379
3258 4927 1628
5119 11680 5177
341 10503 1051
6324 9663 2220
5054 9105 2347
3080 11368 5145
203 2161 1571
147 3889 511
3441 5071 214
6055 9089 2260
9523 10281 112
1593 9442 1658
4037 6948 2831
1057 6411 4715
6667 11115 1130
4801 10035 2396
3289 11247 3160
4723 8671 1459
4871 8294 3356
5521 6846 245
6791 10006 2100
7327 11426 4066
1537 2374 114
6911 10737 3594
6683 9321 1018
5672 8606 2033
855 10132 6776
10292 10908 548
1851 6555 710
558 7009 4948
2981 9786 3174
301 630 166
4689 10884 5392
4116 11591 116
92 7373 339
2540 3131 282
6902 8890 1518
8007 10471 1309
1447 6879 3667
6430 10676 1693
1391 2544 515
5342 6987 1381
2374 5744 797
8886 9860 457
4122 4997 438
1650 11229 8216
7344 8493 217
8828 10578 1660
6868 7881 975
4893 9043 2581
5555 9799 2796
462 6222 1717
1427 9365 2144
6785 8447 1517
556 2318 815
64 8191 3857
1144 4214 1714
3362 8990 3433
1564 5009 2741
10081 10864 111
9755 10601 96
4286 7701 396
5994 9061 575
5367 7719 2207
2155 10494 3666
1250 3751 474
2073 6286 3188
4736 10876 556
8037 9119 919
6647 9528 756
3222 4877 115
2293 4268 1595
3323 3582 25
5622 7181 137
2805 9636 3294
6656 8292 408
4238 7392 2356
2513 8179 5557
3569 8165 2122
2651 10879 2164
1511 2412 59
1611 9323 2434
10481 10920 311
10302 10963 223
5640 9764 1070
6010 7920 1423
6692 9828 1498
5934 8466 907
2304 5321 610
6655 10509 1036
10930 11103 18
5429 10623 1172
6616 6749 104
6498 6815 112
7329 10896 1660
722 8273 6389
6450 7711 492
2233 6904 2445
672 11176 7322
3893 8422 3305
6212 6253 11
4249 9545 1400
6723 7630 472
1700 3687 787
2095 3294 852
4903 8609 3306
643 1371 691
8102 8634 253
4768 6832 1162
2252 11127 5377
5356 10957 3114
1566 5122 1913
2891 7304 2114
1835 3061 792
3983 9963 5821
1066 9112 6112
870 6284 214
5121 7364 488
4788 10995 4016
9406 11069 809
3605 6536 2081
2097 3001 729
3152 11006 5985
9302 11395 371
3192 9840 6276
3096 9681 966
8629 9792 1061
1932 5231 2157
10196 10230 23
1481 4490 62
195 1911 1464
7599 10462 2518
2772 9757 1461
691 5099 3529
6567 11043 3355
1019 6692 2584
1275 5343 3572
4885 6658 1626
6130 9978 3844
2188 8649 1492
843 3201 118
3885 4294 381
2922 6732 2619
5697 10199 3380
745 5693 2186
3056 4148 907
6831 9318 574
579 11609 5868
3309 9198 3824
3084 7863 3778
3006 3707 490
4841 7807 2179
1754 6370 1954
3043 5902 2727
5504 6551 615
566 6018 4990
1603 5834 1569
2911 6132 977
7920 9483 1476
4652 5008 136
4466 9043 2576
9397 11426 179
5734 7336 1445
358 7378 3441
4638 4644 2
6031 6710 528
2796 9801 4006
567 1254 386
3241 10865 6345
8317 11194 1169
2323 3018 454
1394 8900 3779
6035 9360 2347
794 2829 1974
5648 5749 7
1566 4485 2350
2114 5559 2515
8805 10747 792
4691 9024 3023
5078 9586 1331
830 7927 4849
5067 8464 321
10924 11360 43
773 11009 3704
6116 7000 141
7983 10835 646
3336 5976 1829
3610 10358 3611
1476 7048 64
7800 11415 636
4546 9970 2525
1421 11330 4768
3690 10744 5963
3913 9933 240
4891 5081 88
4887 10607 1419
7125 9145 797
2306 8139 5331
6660 8181 736
5004 6984 1327
2688 3204 151
6369 6889 400
4573 10851 6093
2155 4748 2517
7789 11061 1924
6670 8774 302
1151 9671 7057
2891 3980 74
950 11041 3815
3032 8248 606
7304 10954 3523
715 7388 418
5512 5994 191
8055 10245 232
5932 7270 1093
731 6507 1834
3496 4671 665
4074 10340 4167
7522 9346 1502
515 3440 1677
1391 6014 2113
1672 6317 4473
2089 2468 171
3721 4243 412
3409 10376 2844
16 2350 456
2444 4465 955
2361 3460 818
5284 7367 982
120 10655 1720
8568 9760 532
5579 8642 905
8023 9288 1011
8583 9712 656
1543 2693 357
3342 4518 504
4025 9987 4740
3956 9031 3340
10786 11056 74
9674 10139 204
8671 10441 555
4885 5324 94
3390 6661 2161
5913 7558 1545
8430 9586 719
3986 7229 1035
6664 10913 619
2559 6378 33
7684 11583 712
7538 9866 1774
10093 10125 22
6755 11653 742
2724 6835 1315
2658 11379 8491
2290 11039 2527
1 8178 3614
1993 4842 1586
9876 11140 909
3519 6968 2596
5226 8644 707
8658 9425 600
4222 6638 1978
10221 10603 237
1810 6416 732