20338
700964714 608233271 100079893 457903585 915836376 952641920 61833963 3131 424821685 200857902 761294993 651637382 63917804 310787512 665461316 730166520 190726362 71144936 850448818 888532661 270505762 351979670 748837301 285669549 556811388 489254408 872253632 595718097 513264474 46226047 131654786 214229188 654459318 231734679 672132772 422812045 36892950 586483087 275331528 461714634 787340988 36626520 965868368 703775143 199930383 483846035 433941662 390656745 407507322 136906831 131705757 678013083 488886501 880543057 963682631 45697888 222313816 688452615 493932336 735578290 734678661 625587122 949807477 241654330 857321800 474456600 664466375 746731101 913456038 792314254 60962086 553313377 681457125 26830453 257088519 881387507 510676487 543546532 124560603 918183808 680453363 108782711 448713242 21856215 989325768 412395873 920070454 64155935 100848487 414002789 799734224 688043499 39589910 602058052 929697829 749428061 76514652 446680555 348675513 842487041 238994808 409637599 395800418 920451932 436468051 505405288 654355790 799660890 48951820 631432745 570361049 581921534 740215455 19074291 603777748 582057574 283986515 376364553 646213509 237351353 790367341 445947732 925394851 682473603 48005784 855092679 284418015 977036787 154289585 633093528 672040179 393284392 42731126 67840596 166252675 331715528 425762236 673124817 131376417 474714055 304557561 554253818 56635588 44773015 573328108 512929687 479346941 857314622 889294239 125560449 94665974 532177931 424024532 872577176 67167885 324546667 580186207 204102252 154099805 734475791 837195779 826139984 127760183 732443256 746496931 146529209 916675135 172259166 819654025 900567904 499489572 976727937 454821721 408641511 874017304 880666180 921571197 353364244 590497153 663381787 331441044 537679478 48076070 755465575 410256653 115243954 80012242 990442859 171862557 234112046 577435002 9058335 60252029 557711536 594017942 659265312 704240744 363209429 831524477 376411121 263777332 183530401 205655409 571115404 592171911 79672712 451781583 366259460 285553307 42278735 29641246 616994350 432474564 930233667 372459925 842731216 897993973 304988518 685690427 69856529 539100563 115641780 931431216 451868944 673353315 377965509 111134255 230110410 741174937 795175083 606521530 4952268 978705483 812176939 428584023 423393746 744366002 880365605 789653205 29919309 775160691 671810802 646913658 60151606 602044469 871889934 902882822 352554793 176878451 441089600 422411321 568495366 556731379 206358888 20364309 82601045 584324397 984014915 312711454 325499333 631706349 919232984 182967953 462928184 583926274 611551975 886321929 180808627 344433932 528491485 210727935 972110974 200302286 710157945 32262580 654863106 582047878 787661753 7417898 611442681 81267704 282345571 179938046 637999082 488704458 52818706 720600126 73028854 889349972 33311579 251044539 373572672 805060914 434012491 836500855 241503539 898080817 575339135 422312166 95031100 103830619 485556452 67142074 156649257 195714396 99404653 811512362 630278626 739582757 671446612 241721306 820850460 953792182 274175703 311365893 442496639 326994408 31966018 368041845 68860731 917793948 619086383 442433402 575371214 53098873 131450609 669391104 803696041 706789743 91703269 898727141 663136714 429776073 965869214 672302322 625490468 917790218 336331035 108285445 509889326 7777646 350006750 330739785 961569827 624182452 642105677 256582818 803693211 526588046 624624662 872553941 296898345 96227396 314987343 724785910 1842620 446437951 394177014 805538660 5744045 338396634 704265800 521397110 768172706 522651365 193699431 246179526 292957934 530030466 354464970 802847259 390324463 556988072 986103395 204410642 33686875 480725423 460993459 837380086 7313468 938134472 709934026 156728165 34361867 877437720 881514074 36204486 176392022 128207439 841743145 182136067 319120425 398525297 703533176 87293130 773693013 749748959 185989007 66650947 132295776 392970329 722014557 522620238 949958400 560634304 727030879 983645274 41359726 40540689 821025359 901189546 978675160 383475737 57917710 13037026 113429808 791948135 901757863 289821830 772671926 596017360 471957896 91792350 994542656 28007423 31601831 620752020 777756381 70107190 539919318 910052156 463077518 114450227 285188746 413035917 675084530 12219624 249197542 716444255 52760313 70222901 470150152 31435472 306214989 380584213 896988850 419644796 25048700 651263064 709466625 797720625 247280423 33940872 889512974 94339430 61948295 773631156 715091450 692221027 843738345 107527119 454789535 306815862 221977345 739978280 572368130 897061874 604714255 821565672 466022481 657474567 744304924 936172632 541426391 50519912 316756845 290931592 322681059 341805544 942194655 884664036 139526168 41991430 918604907 881555493 136330859 833069553 507703000 703938660 377806932 351441345 811465779 685112818 510773558 33443123 277607449 83141688 783021349 882321703 904707359 249043829 392312622 501528634 37732812 933739012 404564897 354489656 77186955 727245955 548811551 871897961 464426342 540854070 913889390 235547601 274925914 902736601 68617153 782628914 459191612 298940436 134070258 123173742 984053253 497360167 9133217 114177053 580501854 792154565 996498756 337725564 893714745 388811377 839254197 931447556 175066740 96335445 138453564 104770046 823581400 687265114 976668006 140524093 228119184 743073748 376071693 503045097 498326700 297205198 138190362 957518311 596145633 124776971 933208405 432715238 622137138 942341621 546892290 55155343 587012537 395907397 392880907 333243633 784718773 84651455 264691188 812301864 180986900 403144751 917071909 857084651 90409865 893739915 997608743 171045400 489330014 373680436 526606848 987656713 670885633 664797210 797691375 119547617 789574180 730899779 404779206 411711317 525757751 951671496 466866660 965286639 200095244 712263918 298530271 984814017 796915372 415737811 649632232 830418623 818882561 566704141 687503273 761808777 312960407 537628368 785370528 802290420 911308803 311977376 642463484 434710787 976774585 440154858 406774755 618865116 23570989 811553961 30576433 401845091 615741808 349959444 367131730 815837051 62223361 518178352 653167419 711655084 933916162 302799651 394590059 605315075 722020143 82093331 219640203 34980549 472238050 5010731 689787320 236063204 169504458 184767155 670773990 146279042 624922012 77548745 617660509 501009352 741619057 500753293 902854443 357360864 850712736 122502524 25714266 765452448 640680875 678881685 329623884 574597037 981681335 724213942 32428463 556217829 658823624 252068665 443714729 131061674 257079395 133502048 219641229 426583852 170785554 890415219 425379245 795707565 820480315 43039754 149233269 414615723 396309398 52087711 771976586 99538486 174590234 797690851 864990933 815271108 329088887 47131168 242384496 163286573 623861461 274812958 719504401 135201437 526881623 163219129 118779462 636477369 149237528 338420690 63061221 320023081 81352260 340956817 968246998 901832574 236512922 117480266 168964648 632822320 22084328 940941233 732360805 196674561 591148436 449868089 864462020 920237322 349515609 106846516 83523895 973377069 234175825 655544647 108578505 613573799 818763776 227357966 250051168 820517655 565778656 165628740 140540736 647130915 359101908 961304085 401479841 595614830 78784350 570444488 80953501 100868677 363902073 665830657 150059589 807566860 115698745 14521608 580320533 317730705 973884475 516360779 291107774 60576652 171905426 252202630 674150450 843185553 479560596 776717969 663703207 897855603 942346708 656760294 397502869 153964968 470580730 798982709 749579797 401881431 221943549 683049649 355266459 438361973 348880305 505326047 245928832 317095401 372364007 826249364 634826106 198764833 195126495 778450231 111857836 367031920 30652860 786008286 62733824 362729807 415242606 726437030 260585409 210105666 235713676 658088278 364070633 706294405 309587338 113650429 108175836 384047238 649216429 315958646 822409210 998096733 821284693 68338041 167708485 46165051 747103757 655050942 97446235 942230251 433501172 209304071 161778522 316670384 995312356 224512345 679400190 263071313 803465726 939985599 473176978 39179401 450590228 837247610 597990158 612693917 803414390 558682345 996741155 452630818 874640990 819150364 303243902 548442034 740004757 323468739 447123436 339624865 978519680 544569671 134371467 264537204 753873741 148666340 581207587 601702448 373178684 260607776 864773760 29160761 53109726 337950738 68340162 356216305 27714699 518846671 968910222 831129089 930045367 965651376 136276258 657202708 637318091 439520160 58161094 229839199 762988898 505284529 421980415 594024929 49854199 556351881 858562132 803727939 705018220 439769718 257946738 930713255 552893846 122720498 959874016 606003571 313187587 880730529 962219876 340902285 252093551 783646449 172031373 182138917 601814176 308307631 839341624 91648618 600344142 897502717 321487817 215849391 255303598 743468231 809874319 305157796 152336464 668436451 961402087 709871035 960722520 219348824 640584290 513616365 194585673 452974657 972136288 507773259 333705185 786872515 848675544 585798735 570518963 20706916 620454003 24849490 181530898 312311978 116498107 781875039 62331047 437985923 997724429 317634644 33970506 660115100 622792439 38823321 181067902 436710877 748694355 141790421 656059701 241794996 507923138 850645373 694769652 480059425 210934984 28474836 119448291 59610527 466789922 689967253 932833794 87243924 714816742 114364692 252072254 831314848 748756082 314403300 121817123 598996863 632037943 8303980 111628314 107346733 47127300 292696215 544057610 795821654 434486635 52633662 37616650 942409772 903279034 732386301 274985548 114214017 613377489 394433838 26340895 932683762 936917442 959174689 872444038 504250535 926055732 124516291 188081735 527328165 438919590 309898857 978841379 70957532 318202836 90469692 30820616 365330135 383165906 574878225 13668140 670168893 627511886 51284789 465095016 383307272 636187442 740080564 350037640 102081282 987030753 376378535 34765043 923948195 188069575 907209080 280715081 966641658 884241722 468796815 346486174 175677663 778695671 325327553 99151546 949414858 268313596 129972162 167261344 651479502 704850386 180929484 174164746 332362272 232214272 639259761 715669543 868401713 231856676 65707182 970482994 218887429 294602068 857764389 995351975 335187994 617489820 276067055 301829651 501731542 744863870 648315825 677409204 376075892 826159729 776560750 178007102 94473324 906532911 345268445 598469177 463899648 526197928 772633922 796261919 758412200 411893683 364447813 479330264 643750358 282671347 302329610 715154138 429789766 12610350 710506112 764977760 630100169 839089519 66807410 131831710 436469740 567639586 661757266 812545631 246315666 290834367 990552732 340788990 49883629 188337529 939258166 513783276 714535456 564408440 162561547 325464007 976302122 379525711 804794271 472568831 662197057 959640232 40239321 91986823 972250581 750745432 709480934 602350749 442351302 628804695 586698811 878821041 48960633 100972428 543883024 295276298 244323146 386952107 636065287 294206774 575289635 427839805 660506401 289825091 992248244 823067947 615289097 821066717 55110010 272599719 146151899 717307066 84756302 186391219 661810240 57006882 789653003 223807525 511873983 232004304 852612220 98572793 110825345 901572852 52061572 507224720 196849149 296384717 894176826 685430788 443107842 469466461 113270592 103614242 611807903 958035187 779198541 79613351 631618255 834308550 352213070 630286505 404131967 436969371 816677724 65942207 346492605 458847078 142266083 858366587 690851381 994878302 809455731 654193077 896451153 861517302 13934148 945816654 10418370 908110974 631247441 453526211 230093786 597034384 409656804 841901688 407585922 188855344 921515038 891720528 23163893 126244459 522007032 279812212 563213830 191201107 198270770 909706434 650048184 340536852 620589372 193415917 335415154 430045102 700125345 84382658 144078755 714059493 30199311 7013476 622170466 513963103 460539686 852264251 963513838 870196489 546682290 223616111 911568185 468197327 115336638 787248429 594441786 489860022 67060640 10171967 681061128 265331409 772394752 183625664 605868261 392984123 229557932 793799766 675545576 929683276 878182423 819624330 643742768 760898086 826637805 118429585 127377540 139693842 823210187 90891378 862406682 369892476 167023840 773974866 690606155 282360478 413739647 137564292 772220499 480800286 147736258 305797978 598648047 920131009 341939993 57032659 165631483 571497924 850832424 841177058 501181200 581531198 513317739 997440319 194945635 192471895 115869904 322323175 184682088 791596442 265730904 47088769 14005270 432754743 673579987 704611424 567631572 87319633 842175715 192368422 420636270 989911972 498166400 19284316 762559332 840106392 76316974 780707166 264120668 927149397 474400575 765301867 361196947 987718313 615258537 556142581 32706559 583644792 878465755 217388646 375241234 996713010 116993766 389246503 281984105 790573752 93857926 849615676 877893384 788549992 41984098 151046006 630978315 392666849 170330321 246053998 85289592 99163647 26761163 349410259 26313043 501161737 114712125 240026341 341396401 582487014 796168922 226619311 166131805 527151028 444007956 393889390 523864038 561001721 783135892 805848142 204091825 729510169 507980169 81985208 370576512 549964266 85547565 1554826 942631114 255877886 247608823 27920706 355041532 126886337 229847316 233870926 628048073 197075793 473897267 821960825 779562806 122582540 48580135 945694610 649733567 345104442 192100352 26113956 906106163 975236243 831962097 110197987 557262764 192458618 44699546 927839275 742422883 130247111 781910453 537570349 238641348 29519275 418007406 446199231 8921964 647854721 680070156 636970036 844930513 6483774 311447213 477009670 129066313 360027347 275220632 778799880 705131789 467320983 804913835 463754303 295073577 489392284 426468641 852336340 681850901 323684538 632691967 276790135 306448000 267118771 666876835 397605699 149154397 84884240 843804929 158076360 585255313 376391437 795046396 282702177 382875210 106493608 759711847 364457875 319037306 34932478 143257754 876685446 354769812 800687940 192956100 649843388 142596575 619424740 354696080 676963827 795625630 987388046 953753962 102073629 107023168 473147148 352195680 256177564 410547740 196000608 414253924 995803052 572392044 61816671 131021580 807783606 20826630 743249778 172241480 339863935 630698607 168015585 69065733 985468418 821219876 262021832 635311806 963816451 881446572 990007885 493296629 529588553 829912282 299566942 484178533 936935449 772714090 836374212 45629364 183261829 32374820 459883287 31581232 457283215 521699957 15119163 117583172 542526586 758368941 289824651 882390521 389067547 310356587 951456253 227052317 131576463 65994436 862364122 947909265 947441007 704888358 441205893 329545911 387316991 740772835 813724444 176768791 366003276 650098655 222398154 549265104 534989826 682281441 433362687 844789393 56497749 448481849 962372564 599024335 206850789 104713567 333931207 448434688 415070153 137903811 675487004 546646615 203898246 390367477 347072231 3855605 95255834 788278124 333401515 335089176 381567310 147125958 364374318 747570585 649740965 586772471 149352040 37247142 121570263 582714726 882036534 178068012 31196574 844409098 777092346 90563715 949122664 111023552 538998402 216709168 101443714 67001757 763355783 305341959 457369233 110428013 309197563 405141418 751222488 642599078 740230593 985306149 789725035 104604910 585393085 291982351 543893732 734745124 329229493 517980347 169976201 211266026 696048358 53689127 908191475 325657055 144252841 709830490 289196958 535767594 926539658 390640671 602769350 542411792 695982629 60138582 505356156 5180192 317796351 109094996 500295621 58026943 94401144 142537007 15148204 679794229 434519358 411558287 267055704 763748850 929538633 289548257 975014875 478103342 343237383 735722702 656276748 340006575 445553191 945473705 728290520 224609200 188630727 183576221 767020991 737129708 96231154 272377147 594826251 414027504 381472142 95121871 324570798 328389637 237658877 192235353 8183865 672178234 603793639 127755921 288443435 385848624 417304177 115974662 716468317 613057911 851697363 372745065 953064485 149766905 170735121 533871356 374376105 211882200 717447576 141397095 949011907 813678729 266290593 543838157 227706232 647762734 491476379 552277029 976152371 729135255 744512381 836852587 253829841 200822371 817124859 542273275 439187346 86945387 658247936 155655663 700003297 362461650 380917079 505584133 512228555 551652199 39455488 886604659 763534398 756903063 28001753 565062656 423098143 146808698 108900812 650804374 794571431 452893542 55597754 623240153 34545149 652626486 312609092 288374989 853448857 129733950 683164615 145152554 69195689 193928903 300808216 769198985 556390552 681725294 274783118 68619106 85893845 166754957 955223764 701944594 923658020 835741869 267007250 199272514 982550566 228424413 850076888 629638348 681317955 758190993 105394853 715863103 410817479 270520296 856754443 116782687 252770597 539919057 261935240 321966285 733847959 415259808 91165270 142754863 96985101 218464739 211373968 35395297 385219695 19114084 737339891 161394066 707372304 856863492 360666580 542439221 85287904 63259819 24593920 619122210 821450811 129988772 187501664 84784641 400509067 44256106 201567327 653279664 436691515 316018919 975245948 23055825 731278726 918927569 165810687 680780178 137392307 229701007 716175475 522612002 248815090 306031717 684006067 956187393 15411560 44672646 351142965 100699463 107932464 375736884 572338025 781899627 505725656 612356040 866684267 758751074 509128498 68251594 264547089 945820012 236786864 92309389 821392188 968065589 11236957 987202875 648845766 1145616 69420233 217537592 523757617 318235322 376085660 60280035 126939066 391497219 957469033 478082030 344713034 917917848 853818913 917051058 699817474 212060920 381923449 419018093 970811994 891051946 339786038 87875434 689388309 576572901 180184822 510780497 544638489 191421779 350499723 46000606 192567394 419919955 116054550 568841362 590671628 492140209 629121396 717610693 883637428 439106780 48209074 228350461 357024628 754544338 997917870 909358453 966605258 379841318 328376545 789933603 123409616 668162582 877809036 812797924 97251834 57993858 176094772 641890322 101931988 526594494 540407280 147015733 799030800 656461829 715857094 389702427 148602037 197494841 959829471 32239464 636601621 8038544 113106276 993626248 615099234 111024145 755501052 434220843 343381815 83877597 76670797 466791430 604556530 954479832 132105705 701808364 864990041 308200477 196215037 819438380 834794970 736622316 966454112 486342122 245600496 682311205 876044548 394202533 879806046 688390371 278958348 368924018 548945266 244580976 215066617 164044499 208121472 970567668 598265341 551503286 906961616 674936137 870811067 364034498 481932321 2916772 65842861 199438713 311117248 114574249 18877093 998428569 703712917 837847556 484770690 949313412 372675113 213331590 196032296 104997510 901721960 474990644 473921527 303183577 719571619 688988143 467228076 927693090 659555810 918009768 331712728 419033778 445462257 55040146 783068275 927394577 57956917 701427487 979349641 221590516 816001735 850743085 220019085 372231003 688590641 557306126 321544415 61265753 770637715 517576710 18779614 524876026 845083705 492701140 828059603 417171675 181689282 147804030 197381117 693761443 65813797 529093844 112795220 363792405 584133989 895863494 143703333 494607258 449807332 123052974 716197773 118325419 973796058 936216857 490556421 514903050 346039335 812100835 428685154 116677049 182193897 447464767 494069427 27277601 940165906 174645381 296965628 974371539 174965762 494346744 668132982 93295910 23440587 633444553 457088315 460090927 381824399 600791647 954698184 831631730 723844620 523412309 949957148 550157030 312145517 440513569 917576431 658184851 105130755 198777937 627378252 139841003 646242703 121447678 19634956 438924961 148609410 316600583 265812851 323575171 810947326 933945832 416871080 686904264 419906737 873959394 146995190 801731135 327267393 954209726 633362864 51112012 330138386 435836364 453785393 642283902 876349932 223878176 300468753 833997038 422656112 927847004 973838041 68898814 901811033 993472996 360340126 902936794 310073578 626152977 79028316 121020903 412615160 495899395 660441518 832521896 222375141 659953059 486769382 549642533 466679136 120132246 453270896 796817521 408484961 759572641 439101423 137351244 983450816 592086527 971348281 406106927 372449882 945186321 327522092 126777266 791175668 540378570 29714059 101249245 19047898 108742374 74786499 431663057 457158120 587744368 116701305 679533260 247697427 603470686 81692144 714376562 576119283 387479392 363710435 984604243 147052032 802811857 121955486 130502847 247414735 945820119 389126125 619864616 743522791 569164568 746641881 534698459 109543137 776355939 488464055 128591034 737614664 415766906 412770443 194772783 3511273 529471747 726822395 103725051 985458784 808514538 670617965 414094419 48510281 34328399 251215013 195562312 689656607 225686851 178581510 937071341 171506969 420223986 556935956 915029759 989388554 156094188 302244569 98931690 932450126 643224976 80039076 522581141 58991881 492809518 717353923 915019505 874797616 296692669 871260908 860256399 105207207 541878872 126867169 6233839 428723622 378082182 201796151 118380228 603769032 232894012 55451568 775276000 653117998 464903875 542822110 642506551 620998062 697583031 593954592 405964539 340808006 526510019 928545679 252316238 19319536 498415953 19852094 746633503 795108622 891113001 459406254 752832180 285508224 586273422 759066018 714231845 964355603 813378520 685128424 568124634 46272532 593096343 195916985 699390529 58000217 591255447 194413431 531514630 288838477 640884374 789995520 482162834 167394393 571057550 734479071 39230280 69473503 606847516 785863783 717098476 350476869 97786388 322447007 635985092 684059809 934029376 202733289 648415412 747407896 887861712 69056397 646196779 333474407 117489734 198103659 243990975 708745180 392517089 775505605 997583656 33401462 418017476 332262841 53312206 989075026 66741911 92542486 911064880 526105778 730922620 480679707 876582646 828709007 803126713 365084090 365285167 589672440 567817378 13700578 189596687 308195441 935273327 835793465 641669847 52763060 33897123 885660822 761508239 278930563 513682778 611608246 164848377 931700253 943871086 218160582 773291630 863129348 163219419 684356509 241751477 746658390 17552567 118334123 427883748 820679279 483418212 793168915 262868071 903751941 659385844 452464757 64463733 594659170 288258222 706133580 499938581 174671696 444310753 113963171 453602259 810509882 725571416 618450635 594726486 521958853 836611216 368018116 237604552 852346987 904890976 479356029 599005376 922443543 450206503 26889124 595639173 933624714 672574390 858507243 689893006 331960233 310972000 754356738 779135755 451746573 313006669 279074335 626418268 757317421 393037506 80020526 420343654 971125273 698471160 15070140 345600478 387598728 235604607 583205029 92462066 140495582 915077409 691467441 62939124 365283911 570872916 511094649 151424976 95963657 369601891 841317981 427923890 533090242 448191071 59575996 984836814 761197739 338650330 611255082 371031512 584204187 543791959 791375165 555329460 94779471 806445304 900929937 482378198 42049910 336651317 574840263 35061844 104245078 118824055 950517319 469528988 542213323 461611967 473470316 638176979 683730210 167304648 66100868 216820451 615495718 125676863 54173617 376693457 316843545 665428698 747724968 901047731 61737008 391616484 308893542 156516478 50578140 62339830 638894675 92628049 251507499 66251289 980206244 355752576 37591696 930723563 825281563 579805018 244851881 151268230 217981996 928582090 318572878 136599216 997918893 934068595 114792430 52092509 163278403 284152326 570037558 911003370 37716409 631774565 155136206 346609950 788291043 205714345 261466132 279702069 150858745 512973630 345953358 131064989 868726205 383545053 914304903 546524119 963350070 11673135 697792349 33848417 940255225 16365226 22963984 790690469 950433820 137756414 842782977 113712223 421908739 265336886 877231944 459625147 897111450 32368149 658751449 685402492 90598845 920217580 965104561 241457590 433191209 163574270 372522578 154433765 399635674 139343832 700957883 215502095 151016966 398750231 249350511 91272190 267631808 272314495 734479010 70581980 262587260 429778338 36810554 684495998 695115223 914042497 996637497 592226673 798926998 655388945 130145516 889525842 428122876 947766428 130983431 861314084 111340697 356022360 15747848 363492722 495366191 569222082 578994816 646383157 967972313 828345327 590171698 88120472 953176173 177167060 158702451 215763432 606945397 195513004 752775781 302060620 109555501 749413277 746803644 760998850 257318573 876949159 503041043 685441448 677231939 486540826 399271883 641088987 695079537 267536082 4581709 42962080 836758164 583576524 689345236 657246828 264438202 132033285 745367299 70130726 309200344 904069750 285894157 916145741 99582753 38669938 70722712 61654605 640599566 817526355 675169806 750434491 546991865 30727201 288392290 76740155 369784378 687664173 717829142 64863914 807716606 722410850 107825993 496991121 158503725 649687580 6754300 275458279 781720865 752121599 345589004 943437560 508707700 631483161 712099652 460806804 522669450 782822363 374977761 15785367 452865069 902663918 766219857 852373286 933391118 54612147 929113440 155691847 594792671 646942581 220555761 255025628 221869782 180898105 752016749 232889859 830585685 758771048 508348137 464822901 363408998 853937140 408260460 872116697 337936652 120360112 185439853 860606101 755698826 412933965 728907820 61080247 315597882 347644028 913453532 101505352 254772526 695083323 257197198 849565196 194542256 330269310 104590824 416412037 511167415 709123924 649301895 341753099 467894971 10166383 806575999 831303969 864103523 67352810 555937017 202040174 40229273 593893221 915162627 648444451 6827185 644070446 709524697 174941419 991714473 475494580 276446770 99003351 23094254 386160319 948568546 217636509 716429629 905675721 634048546 227597043 467315996 135866792 421866493 935210967 146033175 80958843 619031287 10136697 148311652 27484655 64693222 41057277 621377876 979855848 689501727 480721412 476442645 251542775 655662830 320673470 727037354 932109599 419676820 750131607 170786270 220761717 967768116 887215898 978953790 454333013 114812940 446269785 442716156 389195784 233997103 588749330 470154626 705544741 451402378 618466277 733029396 368611952 659523553 206923623 200984151 201541631 687645034 677426796 453084405 195824216 850616617 32638110 127933814 122809788 782769717 151236435 343571504 603054184 38452332 175041645 909903548 5781623 621311430 352619703 394977406 707824884 793885385 865132031 413369625 97804114 336114660 998915372 466416065 848154564 58355346 667400216 49696195 746000379 197343363 502780599 941824594 47959979 535418709 922274760 170769766 170704777 73511194 366857621 626275312 964479878 541899266 536178859 970261500 15727047 741314913 217755258 723551930 535200297 935403640 136921554 633004411 124034651 988353277 99420475 972189215 46708622 619337042 21885409 645225353 816680404 377182359 439566298 864640382 765117419 214357409 887926499 935822195 140384955 254784120 414613858 104864832 796683385 950792716 927642683 812410431 544623981 145397940 388478712 79824277 933317932 377916618 565345039 57352582 366269894 517281866 29541796 265494868 136618907 903943556 910720220 805815663 133642267 350286517 522972396 898759685 564643926 410898895 687098232 705028880 518199366 101712089 662410063 167399102 905021157 590052745 979809532 302161489 587967037 220804595 234502117 373801320 598721212 799847156 431153901 964991106 169645373 313212049 83002325 158780631 69671956 993722544 964596293 55830574 196525412 340085041 954590259 761169337 750983935 494204842 318714568 121699652 448433282 981124630 289098753 205970790 423693727 121424636 508132278 864177115 342229230 742634395 237978434 940950442 394997902 521648686 758457899 417159626 834860734 841460223 575940256 757049042 835182766 393052901 812879615 31708177 733137941 619986225 645393866 336638227 114191066 816624785 458337878 415140700 650265767 747436630 473627841 73959493 868861265 981760119 790652959 63606846 576910865 28631392 4557287 824425118 402796429 763015185 241584743 90173515 456991759 670041350 847222556 144690876 63094250 660102170 28915405 648748542 132604747 674309270 837903120 99312164 343450406 148757349 514452863 993716172 896193978 988080704 920192016 617571594 822357174 710844974 681178440 251784390 591992717 538252078 76209507 994789146 153783615 170310601 84962660 610775373 840351950 784701567 755466249 755962552 297320088 784381653 257227445 429924834 311207274 95130565 529236998 654657679 96404265 43689860 648373851 992598243 884286915 421082218 462686188 559160440 131927192 996380979 663461181 576436260 534633057 592187039 423741757 688416671 762497639 361220768 151708395 455365941 145922334 907174643 63844844 295758774 691556295 173588640 725683607 2763568 121235556 254920604 509937599 217639821 151126816 10827801 62754415 887930082 431910018 525440602 299606874 416353561 374337933 963068054 992789821 908970989 555255093 269047929 449904011 170269083 482785049 601612405 478151375 481223734 361303400 541996218 776982507 52859694 715584858 502666114 908139614 836820413 610103069 270593564 54460233 761229884 281421364 117214647 501676318 713331381 495171601 801283191 129684942 869509533 764351244 974991114 630996873 172122688 96555394 933417235 194908123 579340442 387545991 673059497 60564176 748849390 67572067 837546682 654225436 783156924 192729147 414881401 472493688 802832216 685474964 379470273 416578451 966896327 349201271 918254768 680227707 696889223 572054310 662429000 418915107 188921906 637420113 49911979 361044593 733975507 835845565 555952715 165832300 223391556 81528564 226396475 972240945 149100630 916459509 478982732 932257553 109188655 893864132 257267592 764537222 579339095 489254216 33632025 398751773 838455487 804403144 78979480 387861061 376457454 593924831 806776168 565379359 83861296 709204498 778940303 817836802 545050063 187409370 983669101 620957970 268937933 62581928 445715266 418038562 979041436 924697998 202812466 940746442 818562129 460080057 557800016 250417576 949334273 443948392 649169348 640306111 248351535 580665179 28167171 477325340 27106362 687459690 42704698 110967657 396664188 674161353 928804458 794230602 861570722 764989910 415188571 130508654 680088189 860903836 548547215 511645976 638118185 751359680 304908770 309196666 63956088 862708785 559614241 865806712 159173528 61299940 358629174 407525062 494481471 239312697 884850402 521587832 926772386 780071451 632555488 175952925 306749155 413876297 970183526 168319876 31382558 237888448 151344881 711470747 98792284 699892095 223116722 589426820 303768126 528025491 898623485 220240566 243250627 310754077 86047277 402424154 372054017 444676451 662465568 866535487 683989147 399832321 240639670 463277884 32420123 873195157 639230809 339169278 287071453 609414334 507489153 318454010 847302782 658834034 29924756 798611417 211242480 105557830 240554588 367526958 486099672 139178073 587767523 729350299 449932149 673814799 984290804 674502517 971007601 646756371 393554355 507513099 46588691 634194024 970790983 79008814 507389180 610021791 270694443 646976984 71952476 778183595 965430994 771771609 289533980 847872101 422899377 353292812 805946282 663453965 720819769 292045954 802632037 308587291 873912604 105080537 834918441 858203407 779583054 805926042 357476130 25653760 165955492 256581172 659847784 136746474 188106337 19753315 599284616 458800779 666730299 671237092 89500726 484677644 295525052 231551057 185066096 718424429 584843868 991012378 381878393 305663636 135574683 37026781 466767278 9487286 142107317 301685719 720207044 774206722 960128112 77683173 799860482 126083603 186780697 312224617 115346429 227403385 331977931 714631044 686204164 998708229 238384487 628221241 483385872 533909539 859772297 668451968 252333967 444616165 511980697 486728711 602796152 647555379 523755491 69563430 657042664 518379159 223765500 229766059 145102233 183893611 159965584 797479066 162493565 346746280 109703682 277839993 574149664 441681612 992471037 112870179 292906193 230855523 741091419 776292064 764765061 453380068 297260383 869615379 897996232 809241079 356344089 353308735 309312809 732615931 422872164 966355472 103511442 646637663 48637883 248613674 683047625 208603466 46092739 845541190 555349745 8312772 123381182 982015760 302510735 115852218 94885939 595416927 199224093 688493709 224225343 816505505 141873776 521485725 686120884 892386359 183243156 894981324 98211446 492555964 627597255 521083609 311427788 731108696 20237624 360065670 832238721 703285248 568669135 730847811 401342789 976535231 739160582 524723971 958550990 41671316 493092540 905953280 489604595 544832984 446963341 713829937 361338489 441353468 87832013 899975724 186256179 271075168 794957047 284467624 616147484 275070653 658067584 927575271 858695700 678305207 140157292 690934420 234106807 561342778 274298582 635449595 537878008 13459163 12689917 348945349 907646831 358298809 107414981 249767777 903131792 406894673 963597713 116986632 848248140 51429725 16962355 887020670 175021245 664435754 24004645 791168728 939506406 682072229 571260350 650718458 212893787 711417641 194169229 447000593 125276770 468467811 934966540 663154777 334443325 947656456 864616477 94606507 158471616 972031457 344374283 61603408 231442481 307971995 178590039 79690621 211918072 48068746 819227642 386939316 712504499 843232287 178108043 504527256 525304515 749368392 155245713 738198301 313302384 349414942 37715246 438579153 817882752 972681785 954250281 4842428 772854592 818866757 99448935 931326208 643414566 443823217 845445967 874857046 751795212 24036005 807064018 963713283 72104750 478808012 203168950 637125600 322040298 381276992 141652856 699861164 983161735 149414920 290575816 148980470 498829861 328291061 587559622 169228964 153489197 394326254 174071392 778860141 65709362 273520326 562702700 709123927 717343542 408148666 436497325 321655105 284701022 96077694 137884739 209322124 574885705 341053688 846447723 749442354 574847031 840616930 449303517 558008765 990031850 739879333 706989234 341378062 920686745 147065207 510607026 74175942 541391460 537194769 705552434 607100822 810715094 268255133 168741100 380574987 528920150 457754776 554746444 813621171 553832470 692631182 875459646 981234526 886201222 574423721 730676880 461048252 415040650 32496748 871573369 257588851 624892432 431078954 598966913 545579177 578144161 109573938 472271470 972051972 499285058 30340255 431669145 162516503 298595387 600410245 543091489 827515536 58165020 97837932 493653058 464513841 642985466 221629056 298264719 381703039 796052776 28941598 842751290 63609777 913954697 566841010 321198628 538847129 997919964 920165540 936942657 428580476 882255829 261730478 400632447 381540886 292070732 832301592 544057388 590666118 285228188 939665228 270698005 195909559 890019512 616867414 512939752 385521329 838496469 811204470 767224367 634549244 692662419 462492008 698159021 606617115 29333018 19357648 997980595 27252981 792039539 934923251 308349808 674295367 49170080 708982254 908352604 341240811 393800197 304926343 931906928 531544736 244591570 55121284 727454295 134611081 671988698 92910398 372648761 363001518 904114867 139873127 997550762 596777285 602365135 548226134 55910751 484214504 420100133 53891346 363983836 64656023 841330948 672333643 738951389 890501028 233832248 499820344 84258190 627632445 804746686 16165118 11693532 49338255 923802753 739147826 36465688 448307802 832058223 261630800 811309320 588689441 401503927 661376433 37983077 856385413 62118918 93893828 340599916 482219050 301525 704583751 546875072 694148824 229433745 138342812 437166203 463265992 638163155 521424393 90898436 295426192 390105862 102591968 197280798 313908614 694256145 86262837 762216416 378830720 347893637 426042087 967520160 749397563 87418519 5503237 458299327 149537436 951913416 798899242 484272837 952214940 355999344 31147908 498880115 585433088 22007071 936046318 48699079 512686577 457470710 992113867 808112768 847576571 947222186 5393565 14001536 493994682 91656402 628734303 725341753 439550038 54776389 545378265 41463952 142194907 403397853 499763278 144248694 355311268 151178871 628521530 160042559 359694566 512185789 658922673 945127653 386709211 447485342 846343083 899395787 904956051 690973301 707508554 605048973 490711838 565418471 471566861 837222872 657074872 100301163 562564624 949141261 7593904 107942888 990605212 2305162 363857092 342884841 146553856 719168359 346580063 627591737 731727269 706274628 139777526 243166294 503918632 379003088 690651635 202778066 278398875 448124038 893751367 838423780 53173010 236979556 403842250 377256222 74202427 913433473 477557385 489283403 862574733 485151288 449742642 705696296 487456449 813599734 901097488 486526656 385284444 247677550 114118393 117011713 953952177 106412270 212694358 310387160 485415357 903345992 513165226 616330583 351470029 259432944 454754363 257159391 496412499 711112964 634415612 423131278 624546437 964489348 764931032 339637521 302156987 67190025 897850169 789613436 880789758 798947656 128656443 118590554 899141558 242774835 88118618 705610086 201703456 300812975 15997246 687118813 56675318 529162471 155965747 408145347 788595414 610720109 517821089 137524264 174349425 4753052 413171893 798895861 969242400 178102924 991049733 271399386 245292949 888899901 913529173 978599058 540363909 42185616 97189611 292021818 137476802 37824580 997631903 339180258 191153906 13629148 26299070 247829224 395307970 34781168 655974570 36419735 645501277 26312010 26460351 819850701 31065061 439632243 471262913 307460 617735167 314828997 124223198 715544467 56245250 37752370 694143524 596609158 79937985 643849487 888630975 69931139 534190418 738779229 409111396 725344324 604924729 287926817 973173547 232698 322707984 481664468 889168785 968209260 507976477 915629135 640576312 539041537 355261377 964355576 539348997 825512895 279184573 663572194 541057361 335429822 553840915 87717237 784555331 486295252 584083075 525702657 556226390 118273492 264481885 965337785 843617815 869406613 253264601 669307713 722155663 575972584 150972180 463840799 396698196 658948656 379469933 889790859 50506545 587247661 854146435 589855541 412760556 985847359 105944086 806334268 173793532 659785000 894051504 958348862 146080251 330650930 484051518 554822992 448924422 601049754 520160776 145058588 322972719 625941728 814366301 45128381 54430664 817854832 361485531 451128859 329319840 740955463 193436069 379826384 180719475 47582503 969681924 593480030 885946213 928142361 252330650 59739744 440443712 146382153 18088605 439040315 329549435 354656474 993863306 778473856 955706228 366540434 776048795 131195298 992482161 442931447 28840030 46912824 260786279 390325560 350558034 590106118 131281022 543994103 969932501 164516848 444092957 792130776 757996878 330039170 572789488 10327527 242295265 13233199 9226031 112900222 452273513 191291817 467556695 298653171 969765672 275779274 665193604 598330819 406974571 657675764 41262265 435814600 557104940 154564895 826140159 907662973 744671012 809937532 451657075 567119864 974454380 895750032 211766991 584967609 78305553 784556478 447811487 320600817 650306029 309553869 433501038 102579541 500845686 753574085 253749063 323127709 29353358 918942666 921458527 288844281 429134782 815237144 577175232 986239721 969802038 255831743 893902693 566989402 65769274 198076120 134109265 892740005 946342503 198392608 330223965 24648055 835465437 630551803 197765223 485771465 940105672 483782613 440867358 293467709 237356697 694616420 469111769 119226406 466075438 243086648 260587038 895210219 58323791 837762270 881449939 28125828 93594012 627868983 447631581 11879637 678461454 434257198 757135994 624803956 632649805 87359958 501968362 320631593 570428113 552249937 806403058 363050136 36032549 99786767 656517844 125905597 646919538 125629612 245132002 112994975 221232611 505719040 8205193 279556401 195997661 742171483 160198581 289591672 222556818 607830161 153987660 901018271 42087358 911123653 378338579 527253514 850999963 732823292 847885107 421428075 285073228 506804516 784478210 173622128 459107634 293512405 299527724 106027171 271658368 544659726 71538498 492890979 902895117 79743690 624963731 98892777 674431525 785162311 241000800 749504694 245508824 394988459 503039316 140112533 306112112 881377894 519882399 9628426 466717538 220283857 431056500 751790765 727088372 68051061 925412893 38712357 214079817 77456968 144739527 485738184 622116693 216278024 831145514 377528161 148538066 456109245 476420937 675485942 93787907 717421736 424990635 191813082 112410195 928029950 331925615 271038658 661924196 851808013 280667083 128641733 72091869 564239934 732948849 651696592 632290994 510878093 690408948 846370810 588335061 687664826 184625345 62968105 903942850 15770859 440496266 904997267 324396455 769433554 580483208 270700713 339371642 857990194 462513795 304298188 638536495 794439409 575336845 152977042 498763773 708520279 134135126 423371993 272760212 867083975 927584936 757567557 230478419 470510235 456454718 671329831 158175060 641080062 734297936 914634261 509367272 27310553 819631527 686280078 796744106 252631086 956980791 136115747 110621279 419494585 292930286 601674126 66450345 868267130 754651167 417730469 429303760 888786293 841102461 702063971 608386619 621203748 312147879 838865037 91713982 768602596 362711220 102405393 262199010 97009155 17039654 771566281 976836059 689187532 310362711 626096516 941818618 267343501 614728615 904956248 539354437 907658900 359146725 605804781 628442382 113797892 23535249 57746141 2584184 717154061 612326464 463487154 190874160 924474342 154868542 282588141 693076938 517579761 384993533 955275947 467105267 254549538 579358579 443941325 943737070 889721289 70037841 738072039 9581141 537282807 495544638 548935577 444941706 854691363 7256709 73384087 968489254 883308309 983646580 823589789 452978721 595973043 139593294 643852880 372963736 294461835 926441020 66040673 812041596 163950905 873832971 279146862 418500442 305707902 575604539 214753863 47945542 498158731 952825901 57526683 35441537 448370539 458978611 332899594 155578253 318751672 258800033 124067506 202059980 242446612 800173646 655038701 690936006 939766939 151407932 63899741 86745125 77848952 982456766 898786720 94316208 708806088 30449934 365333001 14513989 606054472 580086864 914975883 104213202 532912764 825018917 139654738 833799654 136513879 325070683 989377906 455265550 583870715 965961763 657325530 826317326 618651760 164880582 369769683 410935050 316288513 433669424 497680175 246653816 268642541 396466894 193486375 977448628 426916827 558819376 844478969 32971298 138906239 759454851 989700851 524335354 436990119 981871940 358135008 573503997 306942623 200029265 28769547 890813337 165991028 538611428 569647015 784642787 703492009 939416697 48094189 872296873 225602472 545774363 118950689 494245012 942241256 164953415 324209992 221674435 723772790 168688960 107162084 862679028 780660162 96862935 239530734 217650280 931251226 597665741 791154276 90710200 797695005 672440174 981523537 816202384 211051601 403686903 453361523 767059961 195619951 501455711 639356834 273738775 47230073 610823874 767983786 841987680 775777288 92193777 63662114 352066430 113399088 23340550 67261809 894059249 972719836 306792542 964225880 903971061 904458282 607896508 994681261 554669639 280336681 828721149 223388374 343904634 84924403 676749896 110964594 133060705 178205606 602837779 406799479 77952030 66178004 27299617 919939710 841955292 119493393 836118175 46538073 85408833 859458724 113799881 831984433 684694911 420592423 796210313 441182324 177567056 256623172 288379936 732236694 536959852 117101084 955625068 880864485 54541838 484891315 844345431 187602542 663096921 447183209 594402021 741048950 513361213 621701637 513505011 207832856 593711381 349623186 254370928 531636565 61598261 368170808 363620998 746293172 788763230 12347662 39991847 966330286 268970833 328371782 551083331 658447036 297989217 359224750 391827873 352531054 844116065 236173303 392649947 359729337 535872863 987051967 953294638 49234075 461269955 466799649 109583282 907497688 668939186 216470561 439134252 730537446 584641369 655271601 329346969 225920950 667619262 369338815 44767587 789106446 697710596 448367270 447553482 995699812 807592019 839381354 200747217 504224435 928071008 593397164 716470123 463943870 432965482 669764761 365694297 746751789 989080761 327793930 654249476 658019946 544264491 945900079 241073743 128905859 601171680 422937064 207343160 121307293 792275878 104627099 910413739 342502826 552994368 210483572 190718989 213102738 902381277 243982558 717327173 830452284 837379721 286313647 146912505 122861554 956078407 365123153 869613342 797675519 692917083 376379169 308211816 237181573 174795600 549285559 218603783 775967279 972222622 278463294 749790923 617014851 383090392 512721013 812034028 936084759 723204584 2753017 149187497 478102212 99251926 719031021 161070847 936631646 5344667 307983352 912009551 813939426 673106504 634139245 611614944 218539938 10518413 919826760 455721510 37830364 321628670 526841644 813797642 146367643 805304938 416104917 615898845 188395329 928825929 427932873 124480088 504546865 283202241 126183936 982649076 382454166 845214956 143719923 171602163 703075974 304219626 83611713 517015399 977326129 570267309 981146695 48382419 433302074 753489806 504103928 471132437 75118475 30945572 137446431 74002469 688766861 553551347 689901313 877162189 482377275 970350537 854158628 986924139 106069129 832858915 822089567 488523294 530590222 965809489 512641808 233666196 122545466 448769873 603197946 99871594 19037181 584344640 770364 452339254 190350797 504874292 923471691 117985623 388336215 60918121 191988091 77103075 466985819 734405756 806781615 949363093 704756292 513456595 788803584 810825421 198831861 463409502 151865066 729422083 281735342 664506874 963088278 404280807 113276746 418802575 356668752 984830278 3147215 357439116 289685884 46014363 862313407 65673926 163999986 103165973 126592046 355988076 32785399 446094216 90393831 692083365 247973660 647666475 58056311 36777243 311008247 256888172 352703096 315389664 986310254 634438437 979896537 801914883 38719243 945689634 220717457 395387995 783036264 76381023 752827110 72722147 122395386 467656868 138396072 286395371 423339192 117504469 494899798 456124590 563598684 437809981 724306 811572343 85476455 58780617 700865938 249001053 315668788 53569033 564390716 301979041 540523822 396803605 103893923 579243064 195009590 177127731 827147410 978045853 106025106 432490871 903284351 228420491 900147738 41680422 367332213 176003281 11701242 862232010 632127870 427816277 300041990 632852176 91904972 238034796 691632792 792770909 339552200 7301579 698856293 903942916 161796971 91896466 153262872 118207245 671139530 200788813 147851327 350803291 31351018 253876432 783294162 934635368 482296922 535958251 828832142 849629134 711961532 840533383 564377496 196605753 120866012 864419485 829457928 212770983 954970633 373607071 5541891 294522832 233425001 556914535 50982099 247738323 648811001 56761322 365945567 172466882 257550135 513796894 523270172 288901152 767673325 159080685 223536519 102486599 695038936 52368660 804632084 407000467 745418395 369009579 603606219 866284406 85945416 285580499 79055388 40916048 511703921 937113630 187955231 745128922 346544516 91453682 992867244 847871868 148215003 211329163 20338749 405765137 577642408 396125273 694666288 197832084 555205957 918202807 300318682 102761244 823087818 104950766 509761710 421022564 326476696 965884281 139823321 264938463 103981131 71395060 158370862 615685051 861025041 346326093 213330324 60085909 437779774 58713920 907957776 585994776 270043082 780812877 991759913 847685489 29454501 538942552 45517572 584660457 309661710 198352606 687421701 132749528 155819723 49699762 406288443 334812770 15584042 398628116 599751233 119565172 470023175 758122094 587766575 183564568 104448186 801096898 243650476 394744311 859810817 151608251 833255439 129853898 932421127 677531703 830055738 961875627 216474254 728089662 399052436 526135964 778958619 938990488 511401843 934778341 988690249 770206637 122107462 856790643 168834752 721858694 828872166 491374279 479980788 269155092 674938846 436945325 70251990 918589321 684205988 930062806 70197571 517461426 912433056 855135050 47509480 595005145 669527028 263983733 175611158 921095815 642636048 954569776 860086302 6554242 741864468 701292903 776760879 863971930 410599897 945595630 438346975 91988414 289486260 918327762 361143506 964425105 207789439 283911847 883014425 891995426 66491004 805728348 261973203 978924059 513379749 309482682 426445556 35423128 425982766 454573065 956518943 68618814 261659193 669121596 75173055 3523660 222930850 851933933 720011941 486047098 650045915 10875268 578035512 939532174 929203029 791695369 756473631 989508819 75607215 492004407 734020596 142098218 150249106 995993798 973538629 663628854 157992831 252500536 551568334 583975597 707073600 360603628 505110762 968732792 29725223 580283816 824772804 105172425 284734101 397301096 591219522 787296367 408176363 21771385 579344892 189895744 813466753 335818522 179404562 741590319 827822929 913425158 883688537 978072034 761935307 709743517 494217240 772444490 962244052 45785573 208936438 669317651 258905552 714047199 490566795 141147126 146847366 315339598 246319550 431581466 712640693 690055424 71394184 120817056 711826808 650739076 163229151 377809913 986557597 342633712 119400231 666896877 108575221 855605119 497485263 723026880 417864987 844218854 495471369 380109038 742520778 704407806 901943041 1426329 270971356 392509835 142573454 417818721 560365784 241409356 849400187 125522828 931464779 920794370 98856235 495807938 424049797 262085385 873617850 263123746 604719097 845534433 930020622 565810669 553655903 280022236 288837548 971520890 124241089 636825268 204146279 719278218 193749425 106089319 720704546 464720780 351115505 715794352 882539501 911481288 957203707 584456039 37004116 888668485 357766760 135860350 236992774 781816557 250462087 110610624 44940302 855181183 808661408 827477275 273508203 214833662 107499511 562345751 38870903 84256951 51687370 95533534 656051521 245436795 54139204 229272418 710157574 405254709 945066769 592697074 169252348 902270475 29669464 58772815 643455311 387436224 47149517 880448085 169252780 297611603 843575060 66709433 5309137 504752819 894186707 278817339 572102832 854202569 693679441 610973735 790975872 745366811 706507268 447027392 990803605 760646471 676299809 700961178 18417531 473882930 146174604 40186231 228669756 175844067 98959045 872125067 563280290 146108561 605089503 585049421 296236515 301180914 651758853 154062003 658450084 545945560 432879342 230552915 252664480 126558782 694043001 43640351 724441944 253066620 343184094 715245548 13713091 19483903 268723078 884646973 345883184 267414033 924833203 574552939 443258099 23792248 299194357 859054741 22417160 904283859 444104161 171170027 57981124 95863014 325232029 716431207 494324925 610627722 799500474 746989404 589702856 493543474 643146107 314144799 746610094 986330200 881906699 612839536 858330454 3146128 350002860 204213637 270560160 274836063 778766576 713818258 151144662 77960932 425389350 26078173 834761143 869493511 49764551 745258618 817872876 374996580 314206177 164714152 985624301 113706650 764219907 427843508 459766475 407366013 741988307 58892920 246212565 476411357 671732455 104543018 479557484 21735315 161273007 750117643 149087729 940039582 316452252 152748742 870516865 741841602 178826914 557794359 463851464 228591465 155569329 134240691 456104396 469775505 298954842 294245048 583482154 63174748 722088556 43248628 323057113 316593214 102141548 569269677 793004570 626390354 526329046 272562053 500642020 687602052 22679695 502246100 480157985 191648298 654994841 203191202 933489899 833821755 760985560 397341362 914929571 916554888 531582052 371033966 238846744 683053245 665279013 822328897 598744345 239883920 718093877 921801457 556477133 672751776 343587485 349481702 151658481 869916530 474560106 504816853 410034934 349756152 7062952 890192918 541404450 662057793 93384119 474894348 348395899 706886031 724752062 115841821 475957270 108850465 486875786 714804014 791903710 4671150 389649262 390648054 244555070 107743138 164965862 801032202 633011265 361069698 3030256 637186098 83502579 477590361 142002950 493537512 827346513 1582253 383730430 221267314 663640045 329630900 696161661 864552295 36516930 273430074 980394115 512474200 382280539 319786252 79794565 174184248 324457402 469443826 417348653 421528823 429703316 582314514 75077376 62714580 943384211 78107631 552417029 26886789 408214344 694419978 372940653 88077208 696002231 756671082 309344521 212158627 86301981 5506181 76710922 975335263 131452607 909621388 340325814 513733145 229407640 420120378 687917392 406381393 889564203 105266044 827910215 319267518 540096909 902987590 234498450 335997471 981095221 786915478 215400611 241825916 333851808 588341263 329903123 882370390 197528696 639247643 94529016 136347029 497270175 23756289 111682291 628722781 785894029 304524456 142455925 15301668 724644833 682889668 274199412 614209035 640672063 102109626 785992905 33285323 5097215 20491354 369282793 838708787 659923183 437199756 80534702 846291342 25541018 262954176 728661731 75586066 902201818 675707099 64449446 399471993 551979739 28648088 28194773 190390119 333172543 23167050 58208138 57817375 706056717 332407549 524542761 199245132 434517174 310535665 232530454 292130741 183543370 601813247 983355879 695982905 39013002 916406933 542274246 917070371 179361108 123452329 845172788 81562926 651675779 909622233 333551270 56171869 938270320 214262394 246561988 271442862 89945795 304770125 181776588 796002512 637177674 706319349 995247643 71694847 16855013 80294448 216341939 52914735 682107694 52214170 748897639 573637047 968621102 143688236 343223770 498561 119656916 40912909 82061486 771332694 950535142 268129107 827504563 888805461 334907853 74066550 12764675 424853647 378836674 194541262 73372510 16014347 900860610 68620152 940225546 770231975 1430952 9083836 675663061 683538645 61298005 277077051 109692044 29919106 420765286 305432165 30417667 540422202 346345073 964995504 164271247 296880214 85640963 991775809 38202027 420548815 65842358 50966701 845402461 297195384 98024314 918774971 165726082 851401276 839911474 958467979 474149602 841342425 967551815 149812662 377397422 881366171 426889712 339605817 763801629 700171349 645037981 646735647 93109902 991383053 464247502 257381149 140779619 549888464 249156957 178981645 822953630 167515667 82464697 520872443 317227402 33005362 292163765 482953483 884406637 132075238 293937814 358556238 825934015 114005980 360885251 55847788 995372150 787774962 395453604 759173778 340462663 40491584 258425776 433572564 884390988 722673278 690953712 25170606 125078093 940110669 56668602 948031723 960142687 139133298 468904165 277370088 172138660 761067929 612839922 56545296 745659518 906777735 267617886 424109884 20783714 628503136 332474023 16155864 268794450 727927626 627845993 609257112 620935561 886271769 42829675 357842901 461461398 586299739 383013506 586539490 378926759 439682108 534571212 339069445 431331757 855991728 468955884 603470416 469576008 81795805 512532064 67751878 988573540 632666301 491861761 861873605 113685788 824335784 730545820 382480237 404779761 210908165 844253700 878231674 97179933 739599727 236074574 411157682 325899465 471604431 997697171 704826223 911286538 384784735 896412019 195134647 240776462 365367902 798605062 710352470 299680058 163653477 778104347 140769949 796319777 122482459 2643554 910005565 799334594 733189373 145002153 56630707 944097537 989255853 934862380 893793821 581371931 23453305 157467854 907271395 495057735 155165025 464613969 258860625 539949759 213542339 453995271 633242572 578910240 105116684 196111393 878590297 268770161 974215739 19360246 917606289 949214550 874520151 680128205 748549143 460225875 825130358 805179849 256839764 666902562 592558580 3149936 100790844 616011884 160617790 8062238 111069619 315782814 325192558 369930243 708248924 538734896 823925513 341491495 970161487 929042196 537602888 701268135 50328708 364334978 573144732 967934997 166065879 447664882 500579553 914615022 907890757 178226262 572311222 17246872 845128823 17386154 20396807 945919666 633398037 181014596 806498255 744467655 496797409 984207164 966914249 57562684 375458411 643356113 399054179 345619897 424914661 789173418 46888032 475243368 6024747 472549115 295694716 172090626 920213997 796274269 86705647 680621105 974500530 511533220 697867976 672145705 528919373 718264782 470581722 14833762 899279378 129596329 759301416 248593138 113803492 578732017 306155822 341778255 222088129 557726352 687398151 647002789 346899769 586802534 974762509 352924515 59351649 122973576 525015140 832081997 919247844 464237138 365219453 746264726 828286710 915603780 270926782 209722434 486384913 594024855 224556195 238180642 723621183 983857611 486773780 689941027 415105979 645445953 31719281 637194107 203172304 571633783 136713248 402588424 10952669 111475756 755512938 922820669 86965683 133044430 607419017 6213527 449797919 972638469 604994604 278084628 740758600 728437737 487807062 227143512 322462591 712363256 465324154 898600126 548737218 804614285 441057504 963843196 450060237 325293136 453553655 505748892 896926918 442783254 908337315 760395938 406775361 516366604 683216606 493741043 649411033 143151974 352470921 99208952 115790442 957465524 229809931 709065393 538419612 570133344 936208905 860882203 135012952 254049410 611998680 683750169 58663694 53056183 500109717 361240282 378349318 806179723 866989173 127792587 248962976 627842839 888188525 655738336 144209442 423921482 1995730 646136827 567073456 354466651 597862130 535380249 164448526 827672060 96961994 702868138 250321756 33170898 416266692 385334707 139736659 28265371 69084875 50916704 81321553 421710943 264673337 312187222 80407017 131662509 292496160 329369992 612021699 33201036 837624679 756231140 457122518 839620409 254884318 876712325 194087059 852746447 264608925 358535584 532934859 361570918 61403721 783256614 247258167 330186764 168591320 386994825 358452134 90192546 290427880 292290038 364419841 555101216 456993611 444826857 539280076 749489771 774196849 151301774 782690806 464337879 760049266 92329675 303958287 14933583 969041999 350561697 867680030 233650924 709097281 253131240 595221841 623017353 36387853 842480008 953204117 57495524 81991184 164172602 147688069 372419064 308978992 512107909 927520279 765972602 956934766 319316707 515462372 583647966 470618480 150669530 47985844 83184097 242999204 204460483 98117680 212041203 555022179 818314061 298208478 116635811 71445300 893430318 592169516 107833152 588426677 397889984 17845027 522934213 562062585 165533095 895353276 871041576 530157356 675389906 489530530 339608473 994706612 4992901 923256438 317841444 8178782 823758633 401025540 251177986 880735467 351659571 463219188 288273998 169973631 761427665 404909808 93935282 507374334 997079323 54284785 948317363 247485658 72129811 471251575 809548243 237662906 219121202 533106170 767820261 747027459 22636699 107428733 594250423 880145952 883201522 912091866 888324733 559476506 165633757 139502718 292728325 517293328 455238257 581002322 539783310 69182273 985912129 633718592 429072959 835507804 688003376 377390321 82993461 760133187 701158247 745058055 997796092 920279448 130680577 618132704 519823258 5833627 578077788 114073680 738495930 313795661 878681897 479337015 725788518 44315654 471356084 18516842 414125333 926594341 599519163 953908642 848292965 437947644 440143585 277365923 125971799 128146961 507272595 61481611 888280147 208430841 659056018 738592590 981226640 789736594 209241645 501049898 648086572 639835784 467639929 386582502 953631444 346321826 865919516 531936313 243153831 189791951 550453155 509795515 116386291 2488669 316220508 817195608 292952664 756364093 94561530 418924462 884511053 454350477 332922425 625307551 662781317 991978442 216416492 496524309 634231387 278174488 997574206 282317958 918010271 317730486 521416811 724158066 664052311 239852678 256094378 759722493 429644629 659063884 269518007 398547271 661552553 585738515 215742878 954505216 194618959 162820760 225946030 79130011 617171236 558868454 556953913 132468904 403363247 625886756 628993212 37594633 904061243 479083769 172428942 822071513 796814255 693845753 398745930 313382917 933698430 654840307 73105410 363343058 166420543 195139768 761890329 827973095 633394634 830149558 634994662 828013592 992970317 713457043 759659954 462657904 124841848 169130218 447643160 528205094 795016973 76636371 565799726 699078215 408236492 738228668 373666079 57567098 284590772 772412008 223466366 218289201 279768667 149088127 434148611 446189209 344227895 48555291 126678655 977622528 878704848 614189668 658152472 724191517 327646711 417812425 39365772 452488558 586942643 487008931 980693652 234475967 416161654 399009729 933554182 824398145 989754748 159736612 734481594 274345519 784664972 957947959 345151072 64433638 107036086 779299682 363139198 303780332 827854972 342334204 133919211 706559819 956523871 792071682 283267687 136686933 62400459 322633459 589175491 649343101 809642389 422385494 883819067 225804042 673911574 669889600 902718538 663666322 682142564 637200131 790528192 466807535 447664442 135679263 383757524 554700527 914978944 599413073 858480858 595350267 941747276 992400068 154426438 898271146 636988102 437694124 34958079 699388560 760327582 476649921 201248012 569969971 751551766 85067078 648290364 425463339 607473030 551008902 941646012 142131945 40725384 732174204 608939479 488389825 720369818 845213354 895606703 487865114 444626426 606603912 83215380 238890053 451520332 237641817 137161198 88508433 675335941 24635628 787896992 288179874 353801900 989145003 858149844 105353665 926728432 358956560 383333356 386717813 909965461 177495719 528849757 803207196 909669922 990305587 144113373 482556092 835518940 39720075 970421205 132661717 646323987 53636584 371551769 97844318 143794753 361229319 38869102 671647045 238381298 679282445 959826918 444699550 520943799 670493114 402569566 300188582 29449673 785902921 686906395 791931485 963398640 68272503 595138680 725584913 58578090 739252052 60657356 746613381 631488479 31078560 731791450 130328817 937231496 103343218 80689486 81026248 317088888 119558587 605189644 407986538 798841031 565016561 852686087 172301181 88026026 255255652 472489762 117475698 893674925 11912508 909407182 709589916 80185011 357062214 287691180 991279452 948830617 348348536 590409184 580319095 379427095 322200633 710647911 169174942 278060203 791337396 102717541 447665442 763412334 707907184 855651979 414769716 125440097 708338065 587070896 213466122 816110069 59560658 330941820 709784993 71473165 92865353 271891260 4174527 302443918 559582439 995453978 251274535 907930974 585863162 684109981 139874421 760580146 247274244 309049362 38640348 38611639 411766903 338822142 654540325 119674086 194474120 69310040 245114182 755328537 656380936 458580304 571438605 568457945 642038475 133739949 639931109 734903827 405631208 644105636 37347745 965213646 492075965 141138631 725660972 77939126 825248611 865535392 691035624 72522854 174584753 582192323 963650845 586351655 921014464 470707521 558542093 115488584 540017560 803656274 723333472 48914847 114752929 147288428 617372791 756791403 281028376 109820252 344211582 539175935 606442239 234075678 356905932 98518203 227730660 82566903 28973681 52979270 948102294 720009304 978018476 975203399 154717978 794185672 414071405 75732442 117409544 972613497 43737377 657427103 628786123 767070848 558858302 743539051 914359275 28747444 352846806 47904002 138567695 549574739 587079936 745009933 783650416 943985867 696044488 11381075 879069122 725018168 916876696 679687767 297543823 747411523 654891165 452261800 394113546 68962570 380510593 511523089 894092418 424247969 21466544 522878540 43835168 580324845 118933943 810710794 609072288 324297100 858614795 600156335 873871838 298211082 197682619 510038605 94713301 893727106 373936031 973782422 471261625 143329078 505986540 768805447 890740601 13394057 73583599 137370498 82356626 454094191 501409939 828965395 730858512 522876482 204360287 774693679 955717678 323294229 437920825 417306317 647591328 149051971 17462651 373979517 447263053 215145270 884018121 394492705 108872375 257954151 220791478 432650352 401283228 726778017 53972150 144540180 740172073 127555748 134427030 675045050 434166291 635836968 504010445 165024802 11229801 708370731 792234832 966947478 884181311 230155656 384253794 384288990 379207627 254232797 758268506 678987031 469378066 642286626 73479735 430766792 752757128 294271212 863417143 6556707 21049228 917389293 151096887 613737653 897461392 285523916 288782702 331627682 921360883 645309498 349168835 932590683 206196580 141403667 752054512 90377890 224075674 136308305 474666879 603283300 243057453 85451736 134786682 712435518 727738361 208266416 995718662 333011840 355053979 711652156 339568547 228619559 481557800 490665433 842357211 379019192 628705700 131139912 563163225 402582934 628965762 912332060 187689968 835162341 53735726 939744479 925540231 130327751 928569135 252723461 733611051 171626588 338175197 868397732 736578457 918429909 929180500 732297118 251441749 284234478 296465626 591010295 512854036 778023425 934192079 207727598 9558968 562897778 191383862 572722193 965480711 820349623 485054252 5687030 655511963 391306329 945431508 433568545 521634079 874000642 538808358 107761481 898143581 876983554 828675565 634722038 647929814 757856064 219535507 899371562 894606893 516001132 342898208 259977281 146540909 129606638 467704878 156099876 692504415 659088739 728822068 510501477 479438361 66392671 516188506 987466676 457698999 314136365 273551572 831849430 40653359 812359929 939610910 938796939 541859834 620802826 426035328 189789648 231175241 645570835 941677561 125782134 14088318 137092121 385759414 160629226 266698758 853464291 316729102 959203173 365069382 45551169 322221001 844507742 111943840 690925859 684490769 422159190 5062223 958042341 106524971 45715581 770402269 46135881 984512520 164778455 519455058 263064199 354568102 750630299 908635033 148762014 876412432 775239703 285854134 114688197 935868928 552552892 820668839 105114381 364272416 185738220 3181902 686493416 882762314 967642093 229935626 567253082 242317634 234997849 377811774 348842605 133229781 730395 247494837 117742300 165508849 766949894 233322851 520076950 517580192 141957883 668838963 246508975 769713937 954693097 213713523 558099217 359762340 34382362 663213597 724034755 72636933 518911850 263044522 955399246 486553942 492980148 375168680 728871576 727977996 752980453 77714180 861207776 753710847 177725368 831466428 919219695 944675261 64789278 291812996 314771805 59263512 960651959 561280779 681493801 767861407 774994302 239593017 127623746 661893015 755322965 704174852 734529947 274234815 967219373 689929193 613305108 460199520 65097872 194693035 40693867 670594676 124923566 754417995 424305523 302648933 438400774 196041569 247324194 355706403 487854565 562095998 267486266 301022875 975893128 948980066 68884281 603403781 41089434 49024378 265296795 796412399 605715581 999826742 70647213 572934953 542272286 536468672 885650825 459886509 731161707 926344691 130481184 856085272 533279037 407303058 158734205 971679810 603344627 258574750 327386212 91199191 820670747 594872478 244738417 649080226 396368895 166139049 252484007 437458329 67679778 370297153 233870727 673395358 222640246 157034291 98846662 764912531 693502962 984497486 77315391 277181020 763358529 60312927 133266292 296637565 320132336 144516848 120833727 923476962 403091597 448219938 867192504 76278695 895608767 111930920 725358920 291977662 130586320 977842926 729435990 198266097 200656431 815823068 871661454 423296676 972857358 970508116 40725559 518876671 955005601 118040949 796057691 570880481 30870227 781840334 867518046 351002563 926357181 988351772 126995876 329448777 289088061 994188380 405727471 37213180 958635651 131086390 329190841 89221971 961445668 911143182 140004419 14618450 726966249 11665873 437915125 552339958 982173988 478640683 923732980 789695940 596681632 572307022 213092773 627551858 354147355 80610818 978554420 133020887 921478941 105550296 462469663 63083353 952255027 720713485 100296532 763407029 704316227 282003724 705145351 518278246 193146905 845149770 532896695 772629505 709331994 970811819 177485814 544022333 449452502 101218794 186234624 898650485 673525815 399327396 378718694 880189522 332454565 209789466 13210408 106449857 167856113 328196423 169533210 120111139 48909907 122346093 736034519 753226133 404349817 293696222 124020730 597496721 991362343 656917424 222642578 700694336 627729243 400128391 97233020 929698096 501347184 283467643 828348580 27389351 682795039 59583625 907578872 15249603 269373090 773305631 121699460 437229202 101502053 143749021 409856692 2928312 266095113 145891211 756154444 670444929 292103784 880175174 120458002 135982478 389608949 343100579 836676813 17338191 743228969 933909832 799552638 97092505 69893826 480417569 124481855 752688864 540001194 884577078 767938467 809374283 657882708 742154278 246603485 611901113 885903298 656460176 614829424 151998410 654867738 223500219 822443339 799487873 103675392 942901340 935470350 345800693 138518270 624663514 215655235 881747238 411089697 15207873 978839742 480983523 495625441 103321596 233672386 35626634 840415025 854127204 697517269 350814085 596281481 944120753 962715197 334701130 453097280 577544620 486699540 960481370 801044838 161659230 759969242 757236582 957076921 547955944 103037274 95595190 172619457 171208860 977342427 583709154 186416732 808698521 64692676 534558525 764536468 150881413 422701510 604951493 5008617 120218778 955765577 453806449 916855882 770997125 788507579 222469514 201058096 127723470 182950883 2102933 141899051 795436476 611855866 98975971 343392419 567409491 47087512 368528228 738618351 24429938 952237381 777551434 685644810 869446408 312109958 450181278 872844172 734811468 907649122 730369140 707546597 715931050 36691941 624402479 486928174 825199519 846871992 687986269 805439340 882339226 542605553 947338390 677775701 6977771 46314360 873684472 426903613 93401871 242212699 18038315 970348160 46966431 795589749 508509322 768929190 107699706 958690599 641773361 695027525 718856072 224658853 255090474 434787121 261350793 879492952 774231646 86550311 578881295 314734266 744506002 313736872 857339818 691844391 991512572 716833940 590675102 717713395 143737553 536593324 959926093 161775867 359457835 859408875 957365615 867967156 628338064 917581673 679174106 122627777 465125549 250546529 347286629 720216022 685333649 608637421 452225325 312081646 547704083 883622971 626815911 144726436 197359842 336672081 836570826 41388766 53506020 279762279 759102160 49759924 668871954 571544605 211535791 28329788 283469831 21417757 748813296 911807895 791515781 280503753 886952023 109157682 531050282 86755003 829373703 68900282 695392423 134115380 380981928 95612857 17738350 7797838 240339292 67614544 196986270 929426469 109003309 250492290 61705099 720621820 300252213 730577052 144682776 364304355 611423191 428152607 385722112 212752838 192476853 29754244 493256591 79428875 138911925 876823224 18700229 968285628 945723505 714092651 954917359 179221784 662221859 825172060 39535974 902561150 892786603 236522243 684503970 854306263 339530884 746209068 427444435 639783097 476786119 424643562 4087451 88209309 852796168 242325914 153478499 897789372 272080158 646735089 829734598 410992082 376074664 848434826 231794061 174314520 415043828 39227771 353536304 77265686 864399831 245588629 832343187 609702785 482110871 516847156 316525400 821641755 115572575 743969834 313941203 592358693 21129747 170545005 533084354 873925915 265387271 686562852 624231638 537467428 185814292 453966236 800975861 561888955 154917413 32769922 736203474 569961241 71997692 942256129 647226926 788913874 187844757 332086465 398616659 522471980 848933620 715142058 196630086 964506195 311628243 510571288 409381239 332757989 533632644 794981944 59200255 799019914 334061147 683431893 189003693 519875438 989914480 989979554 934280744 144831892 875265827 523000570 714793132 799779870 465256698 214536410 588693744 505617807 546622874 839826754 28089786 248072845 407485163 224719871 65095391 719113405 587807510 326992982 904387745 121440153 121974925 963588000 920460067 456036072 499536244 109463759 828427861 341967075 951959664 762708605 486798966 827225490 138225526 54108450 479521712 603482223 121161211 68215455 109100029 667784084 760558560 989706166 768373280 168043722 66942388 833468671 739673478 654749897 12978004 644061222 776190050 134952928 460165573 549166468 443505351 812218168 511146578 271933212 154185242 315622594 887158168 493500560 142848083 25383693 547609009 474886146 481382267 668770219 395617952 442998648 189070654 156176511 432704813 957443933 176736584 499647201 643428955 916410061 6913449 656406958 412987635 783103498 643876238 873153207 184786317 87381588 537887727 548449247 211831151 692072968 864071840 98989318 38089879 859436274 124373010 585698887 334322420 458271629 106985457 729940371 901270276 148572462 738633234 186491440 106016395 915369817 686138640 601961701 831779878 693052089 110885011 97283864 328671938 754761248 970437070 365974607 694659187 360841148 914423853 906490338 52914116 778495692 5479655 91003994 490448317 982369017 529219233 824770736 293156997 488721041 407227459 194427272 637293503 145860692 380918711 595826249 913746860 919573703 50304301 598043089 465142143 161189311 695326952 793814080 768466910 518280374 12305038 463126097 879121521 926728890 222132786 784551988 557740933 80128792 728072334 48189250 62497808 109807918 725476337 208171156 598528958 132703795 402598427 235822460 131080838 636033490 831648708 897344050 555607192 881953009 495387138 20749334 895658671 43230442 667079765 664125581 561510815 679384803 979768029 440632335 458630044 201900814 77700675 16370977 282029605 805773008 64560226 197043765 915580925 642552914 405214920 514109882 627773061 660329699 602448694 611370250 296363188 286613753 508714299 704486731 21083113 856617789 577752416 916741784 899848230 97348532 433383716 461359044 776733334 413151744 754507730 87879730 467568909 832208404 104250706 749598513 637981411 21327283 799158629 406078687 663880196 56889901 920188569 144169608 717219599 375153614 755539858 13582786 661767366 116770508 570585868 682850479 973388296 148338283 599592262 873236525 245686814 32975977 187111920 874936500 298644072 941619650 962816229 766212980 626344405 67066934 368327844 116842168 940910568 20002825 522920854 457307115 76892725 295625774 601476723 794112323 670779387 357016580 660211460 332546753 473787087 230797327 15397231 299691735 231651961 467505844 25444611 477338774 352998172 212556531 204791625 504158595 6692532 167607853 122887926 633036936 87191138 491215769 749879103 28101705 511218593 125316309 337925172 588111317 420942082 939401894 234739991 91721469 148934825 894951450 276784573 622721911 125748776 144698155 922413645 209917088 612203998 947858256 687255862 817718521 12931138 892047486 321877115 19623669 912171691 444765040 505176956 999362828 788497160 107572411 879980885 152232105 232888719 70422408 740343421 653830800 9824301 975083412 598068620 158759125 722551213 874853192 633997387 700816341 19551346 408927384 910733428 484271695 209301991 450505641 301990215 222233128 195069479 476383681 94373148 107241169 921148720 452066455 959120348 562162232 559638865 691617584 714394336 645043935 762039991 307254108 151391087 771864291 134853871 749459706 783139767 857405084 624312898 417137154 558221424 496380595 826064537 321471203 980652290 35366527 771976844 135158856 110116006 967046322 611542537 57005505 74287490 385207608 509071959 885924189 947369839 68710824 577541773 661764174 566271110 192098115 969018282 717662196 963962406 103872152 467121902 599618524 813793587 943951151 16755677 224531362 440331745 695336565 546002565 273500386 583219443 317979408 408659242 545851800 137542081 20201778 602857304 64345922 405409385 111929263 950270110 205295576 33156438 380328234 867059749 599427547 572426349 688594382 169606095 388905106 644982886 636727996 988523629 311292824 433195498 857795658 535824186 873527242 405648574 81826750 147027628 988868017 252322509 408203221 387236168 389864589 428404998 990093472 454210510 686330734 102022734 404480619 891626309 987695523 784808853 611202410 439639421 209751553 152313143 609245515 598656658 797296028 98489862 587180286 108588852 531685359 297492295 496929389 257728953 703140869 578756138 257272932 544525237 831078646 665476152 931761404 73459586 93881149 921854875 527670095 632728234 876393960 932150713 524354543 716605834 569475917 135556952 156245255 779227469 140386446 765490769 230400478 937682474 863980631 817580764 898787677 248182341 115073058 248233417 505911293 670730278 826989554 763184224 215255514 510584551 428660375 147016918 584044136 375057875 921388144 111714230 7786109 650298456 896381294 384657003 219420641 318373563 372730306 375665895 950117383 513116751 993673016 180517861 303315576 710169998 850614976 54619604 958352338 818204385 302853020 464263631 488934663 982358925 79964206 556706528 345459827 508624581 556239797 929503962 736198807 330144293 893734543 596501267 980442748 642632189 981158269 52379740 813522103 206404926 428045635 763639485 572038029 274235002 796673697 875353604 984404999 647288672 782489560 942757336 318009409 85342579 259537318 806944071 920217856 339501524 216166950 265677682 700642456 772406747 47697996 436841262 102551039 793948890 33342529 935510138 289097430 867017149 987889877 102619532 925938427 268451863 718775369 497976455 542686864 515449065 225846410 527091862 15254089 8335969 322365550 333263497 946194900 434419219 992723919 718929107 773920742 208890868 984606788 327079549 981297614 884821135 763920811 936365004 678770025 649779691 871875141 967867454 369313191 712281370 923003338 147767969 980733232 641778706 645744423 523420096 9744122 724107185 903028309 24998210 584959505 77910210 210778058 383670756 512329429 56018328 102599862 138766522 264909196 939723002 465846071 98723161 824544136 82283233 35088165 355830512 732062923 759479657 176214318 953892465 324277378 99217655 101660434 305010610 593512712 599921208 680947057 455773185 324028392 583975365 333287747 908987897 661885575 544065804 145175004 26731355 600084132 247774866 165497876 717509679 40014219 631343946 816232839 864558354 713627178 703837355 72905218 298206452 315833364 101635887 252098917 640110741 53369893 206275702 797637702 646882604 806196909 478584758 102655788 130225301 915076475 288459886 891729549 429478401 832525690 36904552 456209755 285126173 137195769 621707630 2635851 177209987 253051576 671385041 894284693 966678753 227738748 967189910 117401557 396088463 68825796 369500473 36199203 122195688 575776174 686353257 621594643 234489434 17454366 576766782 217231086 932530840 865226668 108960634 362009240 550268709 998381538 818218994 687911233 988093658 292442976 543063435 17819997 545494551 66964827 912104689 364689655 294703574 731810950 482091211 690792036 653153097 704108035 579507591 627865136 132400560 118377199 101976130 366889994 135831564 678742911 584121079 68362404 396485930 545598065 282887995 799270990 396495954 101106989 487182222 384589611 246066316 30245656 402409607 791560866 97210483 167030647 8766872 244430408 898841596 343374435 787738796 551994692 47482469 219762738 32376179 179883029 338139936 134352308 546773022 473971499 813095219 130894100 542333902 62097500 529008516 825221897 861368490 925504469 778845237 201067063 162610432 24911552 83829071 565020038 668988769 33555905 732050685 530271992 130502664 483408632 873646426 918241459 35403324 921128895 138004196 67779502 953528275 476144131 54648162 352817648 950115630 867743380 336228099 344965883 782357231 865236615 22704131 496242072 790741083 654065719 697309135 953351514 531493622 633654557 370887904 52998742 667210461 955454940 583270734 797713124 438863571 456917159 568470935 326783246 230562405 706475130 247079100 36607031 35135613 301727261 389424678 837767594 21986992 725652777 35249828 804344222 590889391 57953959 153102646 234146825 712019677 850411780 40014691 96029651 336582688 263418946 149028392 3793148 218873885 732299125 654022623 510253807 41732636 75009909 837037053 272295040 781485039 936632504 308902071 669137003 90876116 698326748 506904596 112863107 276495876 542154423 769723680 867385266 452624733 922826325 954048443 17160762 625754456 994063133 113190412 962337143 109998430 262218803 818646642 328872314 994517928 325185617 839126120 36250563 400195525 528679524 161061954 34196915 317828379 469964024 703333917 408704494 20807124 62754864 521567600 297302999 604909287 143807632 17204617 57534019 66633956 971253059 74694780 692388412 817832543 40401543 507241906 927830972 302620346 325888548 109219637 297138273 651074164 800862108 185905187 51269688 182057984 346967140 85466603 499886362 816931164 641316871 908590856 690254639 704071735 282674807 987557637 161497373 426482438 857278605 71547743 493116394 681048015 146242523 38021157 351396909 39160417 545263062 131744232 341780762 723667961 240963868 638919034 227258476 41825976 824824220 131044516 76400311 24307712 69027470 576286672 841238875 710344340 484877527 384009865 414416074 767552334 224083853 575913446 46551123 81362458 647461189 539667516 762410472 646220063 430205024 113807381 685380479 975468086 98067964 27161241 551652398 339031832 518596626 778910874 233374159 195937198 909955389 309774469 220244909 978982858 886061140 914000135 689327197 223455019 298009999 956259623 843523704 522093851 384689420 890074826 455972660 32150608 282258694 70899484 530887022 712463717 37223216 68783853 540448154 135291179 948461445 92100552 474323010 319574422 871011425 560213520 515511619 633483165 869987988 588272879 612466022 608565480 502273013 154309570 684536850 652799363 110569192 528060553 27409566 347774964 270651730 483382225 232441923 552910423 554281708 763328945 265374140 591504923 684629149 805822293 726796102 633090593 750439196 53635463 952665014 473966972 613848983 320692985 107450136 336353322 908965863 572432509 944918801 263755228 726742079 481972002 916554590 689827622 10032554 943964155 37602585 133200636 279862732 122560860 686111058 834144439 885889804 951485197 425649362 423035304 609823842 4961815 56125896 212779389 58597277 861307261 686746361 672446259 34516597 794196496 8799581 795998812 219145357 806234733 59754039 945887435 288206735 828824980 488231408 150755640 625305487 378350345 283956275 905168218 500911204 970067333 591829008 239317359 774068881 17478369 662352662 236409074 22440183 570994909 449188463 81037460 284818521 135934823 606000070 171851470 782647670 614799650 967850281 1793026 273550735 880120671 800196812 561757469 561462002 140944572 565029460 39283840 371811268 848985735 944452057 872722471 671569419 388797417 964556181 298154651 258792137 479425194 387080077 133748672 50420102 836268539 67302483 187754974 824719713 673302552 359606443 459883734 140618554 179973075 314193112 414169288 60093745 966906275 975926756 621555747 107850846 393472567 660839586 332178465 94974653 457807995 57417287 766544071 846605411 21973467 917215074 105397547 501398660 304295150 91662570 404335113 993080040 158965052 444606439 670316104 832267604 804212881 130199837 972886157 984185956 296909300 387055444 896796052 116331927 215498551 370868150 76699124 608971117 31707736 408877589 703945770 342032082 466294875 323006192 41153844 488268342 92737617 999067742 842183353 397032766 90730312 99034818 242629157 249695363 543641256 912945260 81962966 200370488 895661449 907365474 37072795 45087100 146937269 933868847 161419026 362435819 304736996 238118150 823923288 188961083 646995738 380385409 383509516 113290612 703391600 424663359 454075305 796129217 276247453 296258658 45678334 366977764 395293475 288307491 469189478 938934730 53769102 403668796 139305217 949430550 311034269 28894364 994517650 457971538 962763210 155936675 672923708 120016557 394054824 496846995 308977640 41050561 877232403 692487155 6857525 433140355 969666866 460932829 81785923 245914318 609707838 127464256 465408433 5001312 268288098 934597910 796452393 322057200 338266705 788273962 124004101 501817326 817168325 118521750 959788863 632447886 126974777 485228922 752464442 521029600 982075917 61442081 414596513 711824671 606445588 273970389 997481377 428628805 734903217 79267299 674543122 197127407 59247907 139951554 54645070 180052356 927065815 851097463 354625907 117848872 491887776 478630008 619666197 161572452 597151757 431971411 794020337 724126533 917200332 399001130 97672485 751792600 312959563 364785349 316133623 919405150 638755737 313614999 200550306 226175305 245398650 875093427 423302711 157162908 867561332 477947781 189731615 647143498 181561595 544357522 764992369 673449370 22987529 384658565 687538173 472655637 816629975 334074861 49298522 586346659 733075990 146971006 338139258 46035552 511756354 654272880 817957053 3028442 820404231 18507358 229203746 65802880 746117136 652506457 75482139 466194819 130454237 265213753 113338317 312015831 809571274 878330685 837981552 685075154 115505602 525519724 157730791 784651928 859594584 207029312 370998586 445186925 206516669 561654196 491222477 718273022 68443427 161695881 721301463 888847657 180203239 950505208 807166888 926320374 455528016 882649026 245031545 585982252 379131 358369861 750514434 662466756 89216897 588495985 347541910 57238850 966532060 357789052 841890778 678642995 564818363 65405715 123829920 771335031 627059910 467568748 342124404 695503337 629264628 915942218 584350993 809467866 718963777 244034233 588304592 174491793 126683258 833336136 612990396 979578740 44222348 363504830 642045496 133439244 804517166 842103757 43194446 771049226 199892808 885085223 302208572 617227522 950490937 426038491 241078904 577550847 893607238 583203307 125570535 375388218 351661876 709921527 37372435 70625652 953955759 625677026 97633796 933155369 311529513 710624192 765250460 208268212 74129021 259812307 194223808 731162538 101916063 237418253 354728115 154325222 122503475 656936687 771552743 72994411 82975177 12631646 503061609 829098767 448351304 628632143 57003336 800013179 191070022 94375770 870638831 997542132 720052796 968272626 783213852 884098660 531413169 548464312 92366872 458058541 808276618 286590679 189221079 762709033 524008931 543949193 917034254 499028757 53402231 688586997 424539519 136377408 553734994 927601128 817992526 2086298 408749622 874995861 802099476 452335995 969371630 525254658 449878127 541940777 346043636 85608330 278555789 877456804 634072641 370922660 188031697 294865611 510029690 377252775 57574643 34038620 773718319 827125248 385583728 827120550 368228596 810123246 816014309 921963590 590240725 486523186 924049887 998990347 214035398 578665714 303842693 35923379 956436724 753720819 577864156 154996711 839329149 856419944 32453514 325918141 79858955 73001562 473300103 589888644 450254336 383391097 476443615 76489007 210516345 862027342 903609556 578744940 524666939 719623864 353224881 114907664 58663401 129791119 966414362 272698798 708456833 270257054 308622176 517409908 876494225 886486331 672406618 568339725 595422626 557376483 894257865 527797932 630378045 220074320 117686575 80632380 603465416 446646541 9637738 813981760 161190234 913247293 245243052 685857173 485387508 598467932 653281188 544050908 728259051 619695549 816749705 289232235 742468954 125371881 806642142 618963178 864374563 331565111 39819254 312313541 888941593 934077119 840111472 519319637 6667790 810314399 452468369 610133205 109477291 462106106 276631317 270667525 227869751 521874368 809041049 713257258 972858651 462322236 257308166 553634053 934534136 74057870 842866287 677003089 51946102 502024780 148482619 916320665 833589890 188301872 81150557 575047835 974895342 921262028 94367471 981563131 731576426 399352191 591696336 841053717 713974649 868327652 964237593 941844399 242718371 773278641 655101656 68093373 88117228 764926173 621727426 22651363 691500395 317110064 552170803 743446496 819134844 553169773 512283512 505241085 741471645 593434068 80288919 568883338 367212448 27172742 550446469 98788873 279041284 994659156 792358941 993015932 715503159 609112885 787376682 958221529 234907877 294994690 26314901 323025104 59920862 500558678 198192818 751421256 817668742 602879973 347384104 489319937 156049745 712183967 994561021 750037741 158134387 927366292 318921079 525346834 807055385 721883899 476652058 938613020 716543054 121527351 784145304 284562564 730640235 571521985 95300444 965548112 866516674 121615344 141089567 778953888 474690374 339282385 382891495 292359115 942162357 730275598 781679051 950728453 294975917 628756423 700766194 453110303 408639066 872203624 978457136 68210802 594087522 455109193 6823822 163146927 576636543 643485477 447709490 159793130 67523813 543009933 125341241 934040487 517141628 266430807 565510726 991832001 458229543 948402220 136707467 252908251 531194170 770902869 203636704 826170086 252175644 756919249 279280388 660814709 629122872 110253875 581541863 75726745 565363067 440882036 91390023 994515962 84367512 539099512 154309091 151891324 934625796 132166683 938448162 304283775 398597489 503958887 148632128 856827032 304877459 285339594 109735282 836071628 56242463 165888337 662241713 160934458 922807585 794038452 821749166 404446808 904292326 255807380 332689904 322171744 696689415 424079926 316687705 781056926 963179437 323513147 785464602 750321584 455679829 723912763 54605359 854277318 80388002 203237486 563620701 385265460 341093431 525872334 73853439 249852245 544277023 736095151 410786702 319600959 382649954 85052220 724047767 286942279 340859599 56737670 609114022 37549014 333333948 778318079 671122291 149029736 101831225 456586892 899351320 557511054 33016007 953956678 264304723 113404008 9710515 680441775 351185819 350803945 58830460 425039257 600656190 603107482 13650759 11442891 922708441 396300712 96495110 499272559 535759342 289871061 408526580 144873363 327420074 741860527 775707793 998542364 890890263 877539018 307645608 790241582 287566423 193177966 596714611 404387497 159098325 458941477 84829271 510284143 809745421 143659730 787839751 262917962 746767212 801490509 126877205 521992004 50307572 75888666 21264562 586066913 365759726 429791141 583456627 545696151 24168020 211680772 396754867 915058282 89219789 704400474 557816215 229302563 897578439 7047177 633690059 56676763 465988653 571035681 419477257 128250425 714695410 59833359 391168387 313978973 861323867 370561943 835970976 764147790 446450608 709751889 202731054 664726686 139543030 786187680 210422836 16227401 997868451 607177702 931285682 939604591 164094527 489101896 21423505 914189317 496149072 507629915 823382431 962137724 78665595 95376039 90388148 645877357 155209397 334072886 959856329 16533263 704634828 648343657 633197404 3601788 210611897 835928457 668328473 202671278 474632489 731267660 218898678 325017291 190961714 150184359 117138234 355056240 491802606 138561738 121761909 987951677 646191653 945144339 802605752 577373599 40520378 745510252 223250955 195729774 932099489 35623636 64779389 489250669 536483644 697976792 492852456 747095540 386421601 13697280 949766818 861054089 744964939 168665495 186071379 935926652 171366206 303209612 143499244 663168811 294287702 265261152 503636840 940479354 62921842 158758943 370369304 103442219 904269194 593620259 151688345 688885035 481760246 216467733 178135703 18243889 766960876 523504510 765339428 153382476 537201789 567622597 14436564 134683079 736288092 53024295 923126083 907654297 208750258 66625326 423339459 503037959 184402829 926976298 296033664 247324670 85735241 666402968 203283241 842520786 112539578 354971585 531405820 594299823 571439317 562057874 612543711 190916544 85562383 230399490 344299020 475280523 798022087 211251935 609963602 386826530 116792581 385606036 146997178 325542839 304747713 570336636 828580797 489150541 349829286 124614461 588991562 435564526 791017428 792274802 130601663 903557005 147246386 662007483 350373179 571202054 76581708 962916889 762118598 162144091 45832730 106417617 637424613 696371168 170185903 99904566 83197697 286978484 485510601 82711226 612521322 790258313 505564214 293618470 131925205 855393499 418232930 720916767 143474376 61766709 365707920 274076038 817840065 512954306 936083520 168213243 84156359 12665228 983646483 698791308 27325670 29479213 657725276 517266634 578366732 827911179 617171200 514080781 967406014 955198152 596792006 432443687 597972817 102356219 726062156 729898021 810266069 144295086 303331139 953740444 58578146 669039059 227816482 876418211 34509716 16416353 897147805 971182426 881597932 880794288 669973734 908923601 762789852 180215361 278706587 193672935 8126539 895877786 707753715 828048904 703592289 157062073 260492590 301565105 111934643 986554746 883979478 922200712 983366183 39826968 875941155 894460680 708866026 956273988 623395242 595892093 972690341 520543047 567074519 706804624 253853686 89564604 468244577 869159889 269779964 746951163 62832823 130422855 495345300 770586538 958471758 198937588 927648610 71480700 353019045 39583252 910551797 236998522 814300315 746434331 276825489 542757822 640895010 838207867 499031809 116806604 434099959 324238501 637349650 853690829 31043125 743719687 943255432 351804053 612879575 65551748 98755215 528228749 48490954 594100514 151331638 6962711 645554453 78980247 930959762 998573497 971079851 841511558 88088370 637896517 440462240 364913859 180654338 81357250 55638077 532202499 50680205 489738035 856440999 688029854 195945216 740000475 284265892 139200647 91804527 897145466 57268746 43076093 277890566 105759699 489692958 429222204 965238762 135247411 360718802 896198523 133820907 184315004 590226433 74425629 822211521 30688672 439339487 2865858 964562273 494977563 387584708 15242477 837231949 96542059 555788682 33177164 836542533 840054573 24894163 780863412 589716390 82162908 676455856 867606956 40438959 166148814 149345511 5677720 153912576 510064312 754392594 140249834 694379316 197135378 214675462 516590836 80340402 654014948 371973045 897419026 1508862 759557753 765177855 838740811 856099811 173482888 724434326 545158695 13537461 749328488 178538458 455770202 684007748 854994314 175893509 576963058 873659479 325239019 435157129 27572054 835303331 42066074 167821887 382198998 239201452 382497349 898789833 172058205 889028648 123279229 69477230 890537510 735353333 834655084 581794672 443969495 8137972 158745349 989128190 874191784 908073837 20182999 182478337 444597936 727693664 210888198 21560993 601353142 536127216 309234473 481441547 223946898 351300546 649263434 606145895 590501997 884277134 357452079 762560201 773305781 333247660 684553783 516359642 68600992 371725218 950670665 512570487 232379541 109416014 354215028 106571324 870006202 226914378 141566013 167120489 954608042 352454210 41197833 408477535 741097777 350432305 889919082 965044675 701732850 391698867 423706921 144751199 275976000 633675352 907311399 901798132 966923011 444381533 270674126 35524002 816106751 221344790 400610840 48486291 183277155 607342219 7573967 53283356 834256597 1656331 220403844 788864638 354110540 261601676 49858524 95208316 612033980 939777605 912769342 166283182 331476471 188992615 311034380 459968822 822667966 70862130 361766954 642107328 515243663 632441079 530147681 331350413 706302220 930758521 232353055 889579375 390617091 239927021 942862730 224873687 241583351 15782926 866254676 448210242 129900953 916113200 395934910 741934933 855890804 161220603 908218114 39883627 350213217 71768845 499852448 25397534 142630974 714135753 667504861 657874636 199093183 50168894 989225048 905395403 980927414 74094455 794974777 224060856 314021475 590353858 448934543 408121178 458653135 167705570 856331419 588554088 83818769 252266328 183005372 792225925 413486931 91223485 832109551 616216499 15508681 184478350 641614033 158139654 898614103 161635245 816014290 97707285 211804138 657755689 855619039 45247903 731850143 503110167 269308759 45871618 93464025 570759653 306509147 404633511 738465222 162840565 993187598 822283991 267623245 176192969 467026267 681110175 119932805 151652169 149843025 135441485 336130518 791457057 293581139 87260972 805608654 109595428 37484609 17412791 619867468 893103647 915177046 351717611 248730166 37002156 250105580 194710542 607761808 556614726 599344052 346227029 571971642 592531650 21027371 839594886 621240970 488053637 373221412 741173775 639705805 523064437 729131611 828352675 167037845 22712749 915613646 972646498 984824528 805614606 842575641 457208348 551234605 757752686 808925958 799964770 794754841 911547889 994675311 255033000 320678966 594019362 601260028 892650607 39067363 474803751 732245493 660308333 962857387 105466904 253998459 455079544 481047692 983130069 135948570 648085537 858359170 51562215 620732034 695700049 709693173 315824026 5424748 260927777 73576711 814350705 60892546 720847903 578414945 908084208 975880902 899093910 354619921 429657282 791744517 393687284 904461032 376506361 906511968 719834770 334489616 13026778 27430665 815537308 996156846 163379234 316139196 707032367 67457801 936871229 255248768 777150973 105211607 260673515 890595101 31304669 927540572 804003998 752152572 505955516 712088205 580549825 257565778 66708125 862723458 49310294 312911760 619700841 278333006 71940079 192051963 465338973 84966856 219482627 133392632 81123702 235378213 449531827 640672420 302836013 238919408 748437539 932503337 344131014 9111054 823098437 375435682 789167977 479618786 127588253 147639844 44223342 560654430 405205621 110931466 275894239 307032266 276359578 895595080 585365271 348299656 87647042 50704244 433266512 159646020 36613227 366906565 395024232 486145054 860095336 697860244 725064461 608532875 482879932 69195474 470160280 158494720 444631155 111844608 638113505 424735760 259484451 682336846 837906541 664690072 645784664 113800779 971722337 922144241 9395858 409603960 122960248 949559251 312824555 408743111 109205271 349437781 775649675 504229502 835582834 488261363 54606098 560647294 96794237 537486029 482359119 419470868 695980749 926990274 531315475 186610605 204242385 790799925 868947451 42148925 308006348 514732114 8466055 279728685 289392706 870378265 689332644 264869305 819937515 2157198 673612416 781659137 204111330 301778442 138404991 39694164 790039804 193011088 452857809 739350392 583013468 935216928 11337611 131510568 714723553 542653085 318121173 918965937 185969362 187068623 813631213 493975709 554317088 674613619 626220745 843709793 544991883 168069740 108579097 217445750 22743289 634707864 999104886 226854619 936486306 137509876 266548782 726526109 183037315 719406590 318392853 766050783 507139869 329730463 897561350 221863421 872383548 68198874 993345709 910869261 255267496 659493273 257361321 809584583 334106892 883582066 505810727 731615126 51651805 466906176 949060875 74395094 101614039 800682113 301249712 890616696 790708340 420314845 469659157 826262007 139721434 788052009 444829141 499377655 117782471 194906842 721241075 842682370 263105716 567103136 753551630 518373211 226596408 10912951 180474146 413219651 747011368 538801224 144834777 798663172 5707399 946412003 725574617 959837790 599610467 26824328 702970837 242835159 299655524 172629993 69097165 291893310 960682001 513926305 791270964 930980824 708833146 365028390 773663193 971938861 932131525 379731175 342828424 11244285 243160477 375818921 424463935 990171844 914620144 569298711 641351367 772843895 368227066 219442336 585198036 967837532 98783015 288168872 210672690 398438539 313315217 132286206 690331848 126513569 646212510 481602811 57494392 207562008 846631200 683673937 32017220 631279077 63405111 227361995 642523361 159081939 603180915 66987295 1770134 517801059 488802358 495637852 143161305 857029423 715080187 728359340 824866954 813863202 16528211 888055996 212301740 182359779 20342201 902633587 308873348 519071063 236752749 366367739 726633070 935900300 50041675 611166641 567179376 965963137 838528636 62219088 977561427 441709550 129206383 979331560 812026960 618008740 327485764 955188264 327554514 42565950 683547603 4937819 856429151 552592166 892993814 921247242 734951944 913336015 676397180 43825291 284923429 913149928 262709382 11556498 701566580 165267408 475239490 121262307 983746897 313768125 183481395 961308323 607994027 312687777 793156235 420020986 783212868 120641998 227725602 110767381 15724299 911273204 115705199 724669802 316381721 8699013 645917043 903850017 774551379 174830575 800191659 59474807 87980502 62901040 923547656 642063433 80684800 251303497 763325740 64431696 565071622 946807134 878256370 25582000 112011262 523928956 445602985 895224129 497087305 673328586 5991509 365327956 437118142 974213059 89997757 606016214 835428423 588431151 509866230 462496153 763261725 162574241 374487311 703758579 77991632 150551318 345822011 158676431 401854815 109147750 75624478 966926436 908471235 806397200 992508435 20482496 182842507 290627771 915706624 679929812 816472709 774214484 45257767 106107202 600943895 987771875 712123415 436372317 576203025 74505997 898868470 191981102 237080237 125872132 895739680 315071868 276423450 94078042 473748299 678278264 55742144 401889128 497721051 964213378 208286327 342745837 984695874 391128834 633373607 752918849 923574997 302362667 379649685 821349115 408469868 980593579 809120989 120593283 269482247 237840365 195099279 20867068 429821466 432179515 146739200 178077497 747251382 423162649 272155539 73516032 101440912 327897682 475405160 451678314 292111059 536207838 794424150 129323284 927336671 280314108 734758485 703428019 582676775 114408169 524777133 991146642 947518099 186414473 111739924 69516697 276771190 159355554 90383765 706592655 444051420 89639316 884670152 43819154 365318316 9342042 117335185 319275579 337239723 445256696 770953892 629350781 981464534 565378041 611190417 761317556 845692148 345948901 464745575 280885274 312873421 842039059 272031916 112907871 28453532 236288191 34940919 157741073 248160097 125324683 864333727 692211516 67480350 601520230 736030669 432798665 610862271 853365854 752074243 948101993 151138901 375544486 429969126 132603434 940922526 41159542 893920990 639131026 239624794 211182916 920016299 405014566 53221974 44564566 517922436 934191857 133369109 552863354 91932929 381529205 530704389 808783008 73740720 450701090 262819589 809771389 883499755 726198212 515653594 488090349 526816556 666792494 863634835 956785681 651912280 657073712 850461574 398349621 148721089 942602719 609532536 921253740 347617284 515270861 965818305 718056071 301979070 99187413 123435777 246428350 333232969 654140165 907727709 406973689 104841254 23063650 69261429 840857360 749261861 437431374 181464061 276078416 104223867 897615247 85380449 608652498 407205310 788358374 7002118 555926399 730961093 469051005 329696490 931094728 984321866 148031146 649150799 138817287 99734911 772586575 237761988 432967879 279243091 145489697 839941567 236600696 168553346 761719347 929974408 917815206 199150720 111438468 46409973 155890939 861570066 131790421 764543436 268775375 772665147 624061906 677218125 356142591 93112910 6914614 287237318 929951127 154945760 788904468 68768413 254680670 414007394 159046753 687648548 693250484 304536449 380106467 782367532 325606146 141825813 712341939 95937703 193492885 676296758 142347675 201900175 390383175 126654448 966443610 659158549 899319594 443021867 188893026 107978536 536134777 195807639 395215853 318602255 203269750 36636673 239887020 457950419 450644066 398933772 998115319 143894550 703470220 230738137 778778433 29076365 225080301 343636723 125014067 418573185 19933480 119878093 620473359 262833006 99048892 439433321 921991554 998368485 882455187 110884579 106347020 271106315 159208570 354079225 589708570 362478319 390715897 829595589 672945090 841359962 81045712 671060408 837770863 784515931 901798544 469065647 666108647 126878844 812702369 643639065 397968381 685152200 616033509 870958091 947985205 715082401 162907763 722493111 565967237 45362950 685894041 524830609 168985616 845102610 878909833 611210537 60097281 122142081 293322477 733042370 816018394 374368188 256619129 506305609 11400470 10934024 975371255 677509116 990329219 788073624 173664532 240813951 325742175 789698041 111772042 273727380 357296793 274679804 996220490 923264029 172559105 534630882 448094637 194061073 232249844 179520821 805271609 292347124 154179253 98594086 877905845 970197647 472962273 134524973 476503255 484362743 997975348 304390861 14388210 988304566 92464484 40569094 81634869 270723011 830267134 193406910 544450390 40080278 320603065 393187231 963344306 493162170 927818112 263955295 687223242 12584307 443476115 345011202 304931430 597655368 443605287 35353626 420369366 769083912 22394950 896872620 105963006 20370297 53779832 120351215 861191215 146244316 160920308 942826083 269483678 843703793 136232992 813934067 883784070 309352408 59637649 847128376 802514577 839972112 111083670 342254170 852556419 407076136 687265372 10004200 857247855 983387010 45357826 277617220 752470921 67752775 27006191 858433926 88123072 80786023 831301493 949314286 79546690 992221800 744656720 349030367 688441945 733406063 15480785 572226014 42758470 75118433 271870741 697789399 767606896 235470762 40043568 620163314 495063250 579825291 630167514 352311104 415728653 675525339 482444676 20715925 743278113 509450866 879149851 683917536 442753240 562967695 485748173 522299929 407705846 230404892 723846647 96147790 963810954 739327431 520890156 859085776 666962215 792760896 556875174 287085463 880748010 449435093 907248776 375811259 881776736 389932641 580638714 297505388 917974331 63083389 318221312 513768796 425050607 49887514 197686331 867803846 612855208 683434504 242620127 20561054 766355747 966466773 969225195 582683053 558310556 490115350 441768828 77789122 135392598 851160353 364874584 16140607 153111797 124639712 244468217 34888532 514572352 825106930 184910271 285063035 740706671 503131583 798831830 165757277 405535448 996518160 33561122 18390656 532469015 128697600 891468061 151341114 95164373 713209607 734024166 653474928 55841309 28309345 731264049 191233906 879469697 96138633 59890864 32581493 73294696 156875432 67470025 587867047 981982361 104896647 872930081 575205383 608028229 524278262 740962659 13563677 373312774 627040133 884470684 905781788 755737732 628455096 57122901 703418456 194181054 643663418 209409735 250022362 671972762 940673784 441256267 551442458 889328768 353663482 436540303 962623463 510538913 356526679 403006861 345037626 461423325 128453294 920243008 69451554 652731555 513722019 935531582 26044328 140762151 672518617 784342468 749016234 153490064 693981720 304951042 347671117 190161490 514360776 597693479 862134251 307550911 891466097 266093061 49396030 245129579 702633363 12019492 755668491 59160041 267542705 100706116 520583365 248512350 873465476 442551270 901243904 387187494 230599203 779804584 380465996 755634171 416663403 981998581 909124234 963161474 286949622 109311703 153322963 801310398 559521533 15457214 108861308 450987629 134066626 10773690 548633559 836699988 22793181 156818402 895860028 142852237 110040869 268959744 391364586 983506344 564027366 145124842 223210189 794626568 777445777 603676184 402777091 46625531 438191117 164417676 9787004 725140738 273729378 15626319 378967487 833250910 31083532 340345147 136754891 17666509 351118836 685388449 854366496 226428368 842206850 602742875 221796957 952247719 871702618 613161542 788270414 288246335 610802735 11480603 82872903 388248511 467673138 338166345 434874041 905864254 502584020 297177397 483521344 776313398 312803715 862488830 462080659 196403598 55350328 451351901 214070106 258985515 136740350 68436601 485413883 831463551 671179475 707210839 636227621 395398444 172888732 277014387 683644779 783691467 288494989 619034033 24456329 756168126 957200377 311846722 514548732 312300748 609024118 998070075 88614145 921827832 713075256 403211156 118231429 768425584 854563056 332301534 27411098 843819757 253254486 365341332 527799660 924433960 925068522 16543632 172348755 97957254 293558018 708509885 734165072 434569358 180060269 611137752 43253836 137260645 922984473 557802567 302077745 532008590 555872641 243208241 306352773 121464248 646419396 424584201 889889831 353498804 609402086 769817281 49834912 862656571 987674964 430150923 639606882 912743486 446694555 811955637 863217091 592768924 372981873 449898514 27338282 553042142 61036265 70592117 542819138 836537090 628394683 844896882 221062031 36783675 88105123 527414804 158247922 587040870 951999004 900654105 940539673 413917442 522987737 842890937 276574012 510662700 273041859 916180894 275922537 572252765 580652882 991655979 165021689 953634754 294070844 44876322 359193247 207623461 115468438 902012385 44160550 596379472 746909266 265222580 633163146 687530740 792637383 643927419 274571610 597152739 544581523 67627634 11070180 67569259 910518570 140160543 430748311 36076781 908857788 559187199 608329545 342027021 550843178 625867585 148178127 844914021 670743906 507371373 52537481 786212343 409383757 949214382 235108166 8809375 66953314 868271311 696340114 859590696 364715082 823428075 309259786 909296604 891055709 172846317 829382215 654090630 165523212 112646877 542683762 74380999 671834075 3529659 416408020 75193604 629397243 564586146 772623977 300141149 71957518 677677809 938869843 333857627 626892191 173978009 195183353 693845504 894765671 891523466 405952551 259480752 567467893 567728689 21293708 311039953 740575005 703192274 965130582 906098216 815839150 360330696 832995567 340189576 363860354 101919938 267899532 993257596 666506083 40523508 145915096 590979952 718201316 84784939 777353930 197609858 111279299 972537282 743971713 6044969 716577100 2440616 118042073 284044992 570169304 139335780 595084944 163260660 842528053 412731877 69358876 510883554 773062572 754870794 703589481 136922925 856790731 971489012 982696873 375813165 12012519 128611968 966793116 582730187 65913258 596663398 632856396 177192556 569200679 376828109 183237525 138294130 379268724 301279597 422339121 949438027 293131728 869940416 112698686 135659780 135188645 34573913 499059685 908251216 641961058 55165517 897690493 498751788 26654529 732903717 874564952 891183399 861515684 693874420 326429937 927428942 143054169 959286333 104621497 712254847 188630793 140375373 850548977 567899516 294171321 125404449 369853894 587303048 995344865 335068931 575479179 130533509 222159196 74538863 891301076 864120253 129704380 641507920 215388393 8875260 226927988 942469696 900058658 88443672 488860467 79004947 868388965 631914635 38291279 825526813 196685834 226922071 818418538 47234810 647337938 112589858 25155610 17191831 699892906 873016826 204777113 127888436 856066686 279452660 54943651 599884114 143572913 37164382 93908385 211477657 46039641 320836373 6463704 798614650 261796396 495324171 877619596 130185360 127238805 915910874 808228524 323924638 995349296 479163413 223675799 642687233 591753271 101347761 512395415 144162528 974364586 569688880 272050963 830431272 849141539 326994613 282831737 845230803 364158994 376740121 56708459 262714986 697576493 63172163 61329636 959372888 411012685 938949231 942074599 538251489 707376457 602819475 714692479 555242104 81982887 938368277 50445689 526252509 39716037 562841103 670415036 866596975 132529982 794982351 549544598 834187873 121976963 832376334 679418675 338652309 209116454 588643486 601367294 906692947 504332000 515213281 718582186 915344684 306678864 660656785 306112524 14055320 115992611 20805002 421813775 197975497 811689631 472259463 724228006 703922019 35100566 247159393 423035345 20146899 42141743 972579942 706851123 16635058 804956275 238786150 207803718 866589081 827429635 661687363 625798379 184277986 176900644 344380564 952139021 483579507 857553700 110767896 350151178 973546310 131572898 771964952 24038159 795778880 96740767 748266164 352217250 131841332 847941908 775252595 4504582 742600003 600348888 563872057 611751412 257821515 802658206 819555129 124410595 482604192 333758843 750208973 666882177 510659486 947105888 471537549 846755344 804659588 582305444 49422873 630722249 566394693 821387825 654760407 214689924 918128591 255542922 566907174 902486274 103484830 194676120 759507207 846084832 795025007 175895615 310352595 52846521 978553820 129907723 29773467 461158011 316182917 632498791 980556539 826842403 579604679 452094087 526114098 236780618 34399531 575536971 867502866 453310575 249441147 374779625 668000499 20086089 630322546 87424024 922572362 733807375 282100143 534595920 432408558 929641501 710491535 742761152 835004374 541561706 725185226 864777840 2719717 41368143 349792983 835792607 720726897 929397661 140403046 99357346 18694630 27318928 674894316 738713847 480629502 924335462 113493471 148630000 944421550 743816017 236054023 719510263 330139743 370670517 106622535 615064653 300312018 817114069 210342156 135316391 211192126 935527382 852610582 66428194 829411876 54919916 902220801 402655124 984317576 42623846 502012469 855528557 69942773 29423137 594242404 550572274 953758598 560252226 551718626 898180148 156584594 787772648 470206762 486724337 10959517 576829296 101788989 311271534 246459716 164647496 299104276 457651842 100174877 4231209 524080035 782103104 59151125 426300835 37274579 895985052 321441032 391803400 751513609 391383804 421226536 198272364 794472430 374985133 758524589 346191055 125681632 915109183 986480054 595888394 254349871 997439570 25234041 208655211 161227455 271693757 373302706 460331730 729345598 325993935 317079291 253425632 960613390 376230415 532242819 997887969 124731818 853683850 242207720 876245426 97584006 663434255 927034141 892056435 38419387 538075082 90763841 16617371 305700616 77243894 465022116 560050486 74683464 490256156 621222048 88427270 761949912 994524753 548759000 491295509 173035039 865838290 597237493 133648429 94585056 129480311 984052749 219316873 983164160 78776820 948078651 80748165 742211074 875112791 825320951 633146812 265704224 916084791 649764182 571404839 993328685 114786297 131455324 920528500 457558805 605193723 8955769 219508716 452234828 410231120 563320577 625269866 128585761 160558069 611434646 75687168 142554731 448003746 295004041 125718890 526780565 95599043 58983407 121507990 970711833 736820709 754654802 88932409 652905500 256935335 660337247 498750536 224237984 644308923 271795387 681796788 249502645 133267507 901305503 701737472 396014979 317142431 179523690 524600739 477700499 643474687 600287907 620255229 91478433 747808299 598490471 470775349 843407341 509990229 592283339 666635525 99327289 199454492 755567933 752232788 456389826 415905180 103499675 680627809 60214102 227811413 362424596 162233098 361078920 116246451 716486922 757093898 433388881 896010611 134210988 763605732 392001649 587015246 236377312 335996433 334823544 834867782 806771782 30747236 197374362 251571472 697382761 296701651 451025963 452950693 901450790 907415788 721372224 4950465 440559949 634102677 85278229 802984544 796335775 446357148 771747346 365339048 55967397 57652579 113866010 42694737 821258310 505867658 629709982 57635621 841864091 964533526 745019755 501152224 995280761 942394116 752723695 545179873 91612118 56266009 998130566 993062908 816198148 572019141 850529724 256758096 206121818 935807952 912258992 854973944 234681452 684006337 220312991 143165200 741658915 334179000 185859936 415433576 840046657 815569918 473069197 534427099 632619795 70605303 35579322 480416907 12999418 640819368 25596780 957127888 697085376 876243697 802707147 365799876 448262837 505753222 622557971 506901006 294077525 387333314 361874949 528758976 71339651 434704291 671924176 665514917 768883290 857784111 80948493 461446299 525870380 406534041 995873397 158490174 477139343 883969071 638907081 342655112 524788438 517020212 152299351 74390166 393263908 955006497 440190041 694043096 460759718 915264363 200944102 754837243 302597677 415335402 136112570 226453679 850039693 660553097 744484947 471439334 370853560 677949791 932885632 896723939 84483831 781275381 55214113 414139525 517760803 546637545 609310989 42549240 63657756 761610339 969455757 309438015 716616836 262162149 3481110 29892905 177426512 56941563 637246499 332540540 472276965 773359069 558994218 174833009 286428517 155995516 646272342 657282076 833945307 431674326 554006015 770945489 65466058 461736479 37601366 583226860 860890375 646912354 478292451 777064482 408522692 447748208 86502496 977655879 709910356 942499957 7548784 739853219 851957872 497311634 72393758 176751188 123187054 483904327 351584196 409615571 639899843 997856537 66897646 473845149 429530862 473420012 97306989 494996919 935156490 134908354 78223778 648563216 781820707 409032581 425627697 42859751 856780788 364646544 20515629 419207495 159662853 880580764 11577066 11620724 377892398 83970823 40888263 501079451 567875150 392472458 910695021 60291344 390328994 830109019 534136492 672376208 303529030 631443480 19889478 91201872 766351834 98113256 739765087 400688892 359662188 17909136 443548642 68959327 235072031 464064271 488166821 394734883 197161386 499743886 258871958 575053783 436231061 299760220 928649586 4106210 692232677 691860958 64397553 935078023 521969976 451050396 607454230 678015358 935010227 627343707 769217229 553878412 577973314 361498667 954567304 937635501 231924154 398115945 6594827 466996185 714696567 347278000 861731067 911857953 699538237 973119377 339428087 135769297 125395948 268077672 992391858 817628625 959938630 909305762 605222999 334424957 212872509 65193580 12440314 147882736 692537286 634173894 701761147 123026952 848188913 508844802 913178804 80113066 906960747 772289983 547109250 474173665 119567982 261356669 386031617 671622570 86992397 725459704 807391867 212388344 846053727 652300076 30016968 658508708 561605838 487756318 992933665 774478346 552949897 857890330 774877433 98003535 344580576 329154932 221030486 45285840 837999733 134209289 125398905 597476831 759015623 525024507 71650496 731099956 786381175 310198464 402722526 873373571 35658167 62630744 85761914 734228246 714930819 968295234 392736953 129053008 308567903 238186969 756047706 861517800 948593651 530925138 959521334 145690578 860080069 33068171 190976417 550596154 19793811 316375321 148072984 778809434 841399827 72239831 509909389 480297353 382438295 765148266 206187275 270612813 827779009 144465541 4841058 395226180 965277126 250094363 376795539 273845028 488281331 132843244 135362827 289391333 516284734 947400512 435081910 228881154 980468682 626058326 779477307 262493 942433647 927550291 779071926 636349825 999790121 141497666 969163530 234744767 906645932 27867156 505357580 586941292 172332696 510198637 834683823 137609821 760292999 211479362 263971201 101090682 196838957 251850379 390482014 713123690 51767243 825563924 942004844 32235924 304138601 721482150 32498416 99088599 501548792 664086693 735438424 353855265 658100711 557118305 588600031 417262994 584985460 93957610 4204285 757318156 456672599 691404460 747444328 69481949 902883821 863931880 23088982 99722777 115782259 413570996 665362819 20065853 91651271 607367662 52301776 395789871 181366163 937316544 494878470 535431307 453919588 82833245 889286571 112020298 639951549 330402953 529283291 77453360 276876915 386003928 834771515 586065865 77408387 434732195 655547813 832808559 151180426 678636795 785047687 119479036 944724142 302926857 139544888 36375412 910294518 191846664 284681634 944177033 129163207 632076455 479608339 435599146 714909699 221411261 547619444 207377599 404330565 929419086 284830959 681207479 167939365 972118825 119789695 97864103 259367371 775337508 930672661 410547797 306490654 568236700 530026832 103731147 871163556 669571720 140106558 633974426 861418383 277304543 430667810 843097941 909380998 910276148 131213438 476807048 984203760 678832881 536700999 388534324 460768319 821531957 922258155 628707683 646167133 42047849 726571786 905534504 669901708 509760798 316082300 976392361 77997497 846109131 80123507 801677405 368197202 72746416 288168182 82131936 202567311 718835991 925229876 964464660 481628490 56443314 293788059 318348601 587792546 830489057 706882924 48560864 504537365 481657430 529784899 150704498 523705279 256356684 56239001 46123338 766117481 224837652 22515699 696631330 923463134 955155557 350825086 291660336 880418325 491509619 373792271 935501987 62861961 151538499 899966646 544490450 60498164 46271056 862839050 500807061 876760113 422238325 401884277 381297477 903895755 931669175 384518326 280117385 40542210 293273678 326240722 806659690 518111329 201272772 355807371 294090815 8944681 559148808 585751150 741879357 50658426 812059772 677381343 113520386 963598270 429864340 510527187 876612785 476135395 225882588 377419846 205411859 648120913 779304122 586709336 404533019 563489648 971227661 537166755 604031857 117017691 863407476 263207898 635129019 917196600 619015269 929219833 926141280 30680428 367487334 520536988 81338854 32063458 50434682 47375591 995661727 480299021 557902778 724790864 808950767 783785365 102210709 14362626 284422629 734031182 453588313 688955647 150037181 277332325 78638753 754069037 394350015 942046229 17276934 29479034 711759180 488808554 811215218 490416811 519488982 31218904 10953798 600827835 63282361 61388479 648203425 911460439 394203851 58622554 636251302 203154617 842407919 590978362 70033594 126830547 177525895 523621906 668302546 327563075 800954231 746941298 81632111 195304245 541503878 951425397 77299630 253263057 440233950 741031200 743679867 959722931 772250103 607150016 413067117 688048815 668538494 913786894 599509253 62742344 972409447 88276907 118413313 814817365 531771620 188446906 794164264 709297515 712068812 462466809 889376941 365539394 61924458 823525404 560843638 603428336 774950800 490659620 856691392 67701101 231690819 452887611 879940384 856457273 60037626 145523852 544506087 581092472 59310745 996531691 496351167 31720192 84808597 467280831 699053908 469096569 655727737 345734523 30910435 220312900 808201331 920287375 585852293 870125789 743812778 999212282 326070476 371279929 489871901 35278219 291497382 574079071 488165829 171437765 430536343 400719807 316961616 827558781 834328630 228788713 824090472 183196148 113025256 761415420 650476979 812079163 83028340 158721067 10330038 113938774 379033966 818531368 34226149 817402610 541173508 630555278 816614891 867243983 1835207 159003144 902522202 145848940 733082214 243204382 317286704 16134909 496440540 486764671 843693689 330769169 715553383 520300512 513965317 828578638 134232284 16958647 493174153 217260623 175679713 503504190 331199397 554713678 174551909 217941897 224632639 715725417 848497174 41247529 435485751 702848732 52767024 190524304 848697671 638365590 286245038 18500726 654500498 782685577 505265397 350710538 113454746 220818779 723527402 479936414 49397417 857759685 496895060 395087921 927536659 672574772 898592110 111252407 79804801 73144018 329194303 304437439 641385786 177691477 198201319 76871537 880540208 103484695 119912192 581754231 741850284 406157229 600254956 248867133 41359158 105520352 599577670 7330255 178855483 175621423 487266668 80769251 33381107 836678079 475857171 813434118 361769202 374449280 924686524 441574002 300109649 253880827 598527792 941495435 284088655 796729110 870883323 17145214 900213804 990795514 598899444 494580439 249469095 199154400 743447571 290828252 157191103 195541593 298158506 336046585 371163015 637941525 416815835 257060474 474619603 892673005 70494591 836388804 119638636 995181114 130479157 419748285 101578292 729006948 361243719 385666946 378252409 84643393 402812160 130982565 75438906 1711603 625563003 177424352 53382354 221526926 320768955 210573457 417068518 618927460 546620041 788231532 109385336 963435876 45292005 584004938 708625232 115786595 272910093 828263868 963484061 255905601 248012152 917578704 984912548 461772222 155762002 215681309 546415614 558574161 199180225 474370871 412802115 824743227 651795223 318700821 46270152 972564177 529274277 315855021 444007989 928410669 104086553 553393324 744362896 1894909 989914614 452988128 117681504 115341058 133768347 933681916 371246659 381780498 703776971 208675558 843552719 859538972 424356866 242484684 270629484 623537090 716855554 683431599 300796669 221167128 2132419 199583172 46247657 383923047 515438193 490255645 164850067 472041097 896165320 909212963 473936005 886079933 214717442 444133860 1420991 348485788 230332127 225184001 730266285 934109098 433859558 426335355 793648069 858216424 668820038 64277553 334269865 238191943 600225503 487582885 459359071 454874273 687166057 505606727 691313671 55120601 995862371 856163737 527161697 744544042 765376699 1097701 483140327 980094140 297747913 337077669 181096279 528080039 562261669 911362563 462189136 996121226 190214269 108353557 706854001 711550658 25147461 41123866 949742601 477889315 381223102 409101671 932763587 68389158 914708397 476593609 976026110 763087119 332757345 355704158 360147512 950650396 209318211 843287838 783260887 507066123 180365506 964357166 35146161 742627174 728236080 349851649 591264752 918450349 458205205 298118752 482517358 335869017 191758969 432259958 813758331 572982071 693877980 599038269 493887580 461102728 75631877 322430042 76706198 260905573 678134199 436853710 211555968 887452409 280141547 994816855 394518531 313023405 811690372 282181044 55650578 539926451 632032692 499431681 310893151 90237896 797550433 793410509 278623264 841825753 78186818 92381594 267324175 772064798 691419862 761211755 85683877 619568090 83641796 162390075 880473662 614292346 599243784 92029630 501744755 879385330 939362836 748779637 44925086 603569559 30960680 100575664 143496009 662993371 452523696 306905512 605747618 102590480 952832372 884370881 944416233 31019189 829268826 211740407 655600338 373205039 825468513 741284215 992773128 761626660 903674289 873246790 375919006 355434424 817792771 730180112 87336105 609671958 478959748 132261191 65757868 362436780 85353206 61770228 25430150 537876901 368675739 483694120 640467381 174024462 220581352 584883613 57560003 49850178 649140371 713160340 275571568 474608884 306960906 268344696 88751895 63151546 994107837 464670900 418585969 664416959 47367363 505922074 126605268 526327111 638183264 192363135 888763890 723536469 254133362 766710391 113929721 622809101 102920862 754397101 796833562 176018566 191797065 854393564 78385095 840937436 420070256 353956662 168062671 579547513 622301357 256814565 642699059 468925545 721485465 913801379 133342503 768852827 272239804 259947770 147696289 910423067 452310904 888976530 486475887 706444266 508203273 600405608 181769718 611124134 207319060 831119631 787142699 399116125 538029547 865527793 240053560 958099802 72000807 408116230 390163666 694302163 664930794 32862724 15744060 238932610 799180455 149086562 860301789 71420258 261550684 7998077 834359677 713861587 749490959 173351915 272822204 257694231 773757522 307108273 721334716 981076582 138227904 360993767 232709058 676257450 79037911 472762617 486873603 151038717 733395198 877037268 845340880 250842343 762416344 861084939 489774953 414113150 862687852 202593093 485533407 124238535 63107521 172409435 690616474 812598479 345761350 963438677 70292709 119518871 123063302 644143777 953111804 261291205 5137543 38337213 790065006 84175453 511099829 129454960 235214170 97011378 6492227 933071401 347853721 621424922 646672691 837628673 35538071 509360542 40221765 373587830 486115429 103329285 545997264 176731902 768444116 891758613 992686930 691253176 863793836 115750231 335396952 669421991 229557787 193050846 707759204 19622792 277226299 71375384 149077751 364956820 168386762 8086330 298028220 516240482 482027603 944700910 206385506 370082026 306577803 99123622 743669855 792693231 54969258 142183470 821941484 823413373 886458435 814628414 367182901 602768622 782894996 702579852 124706964 12452783 895630698 832466167 32075574 25373348 756357903 33669677 390330167 924744664 41756006 540874738 293501497 376299960 338091999 352403354 746381985 644669801 451526975 342568191 289879384 359012584 484751661 111820867 34942309 223726447 778965632 402125209 826495068 414376980 104705060 951202031 426829762 852852109 636184550 311421687 730741808 392542452 197607715 121071974 169803467 91880072 514463063 315821315 468180032 852555061 668224668 214562016 349741214 119751642 557130207 639620597 331280577 894398219 603957815 366222885 118124665 235439799 768348093 944619732 649816778 725569505 748338114 929162891 430937965 384522663 93100929 161679773 629581466 290708644 135268098 799384932 382588715 649731161 115206246 850768746 354802573 635947265 65330762 704543786 608215258 474977320 196680734 939495835 221891890 800638549 305718719 340016554 888594699 74066812 137152637 390927828 652152668 885490750 320090718 83090632 122529765 413191646 97286756 752111230 703900289 232554854 404012514 86489004 734802366 371735111 789774101 89604938 7682376 707621214 794148724 468413985 35114885 990829457 407909819 257006774 643984357 566144890 597023327 385095407 492728053 586692315 776023234 144880720 324699417 96113951 80487703 447229181 361821949 177774459 51856762 918238589 410329312 308385627 857243944 145131677 680120738 647018045 87252966 540319465 207155610 733918041 8733449 242270495 577263850 269159620 499277268 73764558 835304509 96300595 458859965 180548913 535509261 234883198 325429632 860208677 183513501 405917334 159954209 397851801 583691792 211810971 316090389 846537455 520196597 25850685 844185483 52833686 672868729 931438449 445669502 880024338 517872841 306919303 122294832 95136690 576078922 474088452 168901248 263899782 422905398 627761212 444448694 958414658 715160761 622394677 818623335 898674261 28312010 978577543 149042413 464520154 42904865 465132802 163573960 415617814 490983486 7759443 468451499 16368566 791714243 914121001 748909255 309587083 73556655 723720439 257240125 649635576 197808890 426141372 766051709 620714287 906418935 63016754 431645296 621579695 685411430 102784982 372770308 566239791 81362525 521812720 30759944 976783741 839461873 46850256 392401554 182961710 54609698 713369405 199330275 846323940 480006757 948239530 8427374 553563411 524476320 265667498 55715338 722285209 544325221 821767046 195515847 450744155 884783799 627161142 924840202 570195228 729946124 150126861 136435018 663825000 671939580 19711314 493125092 363917805 66561569 885526646 546879514 973687618 451412402 746209789 672527909 931419158 546965670 680955282 484982568 71441989 799139132 540697905 646243549 343464352 214981302 694275747 646724859 99765100 173953240 571565060 522476679 903899363 721691920 511428048 420240714 246147851 383655713 913365806 610065655 302733633 651408803 9461521 276421250 102821204 755671309 948949158 886756713 155153330 482420792 224255632 79111670 134076275 764953536 577871570 477540626 979934837 272147316 124265484 932216288 446100555 548346895 454692966 202516270 122555166 966121013 475273335 221219369 202293078 241155492 831285023 505026710 892564294 840746543 781447960 847901849 448934203 582913469 587174913 456603884 917850612 811430544 535715553 51926886 428900431 113587122 381983864 261351619 238250789 358765699 193567906 536867696 907112594 500777223 739383965 882184111 319414588 67173651 103403479 521707665 308329143 787204854 26734374 53409788 480467748 660698685 901311637 929401951 96128506 341002901 238522186 13979117 152433445 774237739 65906003 581333875 740341212 300406218 842685494 831108353 659171916 888769751 367976048 418800861 389546974 959876364 300984972 708961561 27050014 256904802 83185577 335379156 44109655 109919950 388788944 524577403 770618635 142616932 306495705 866747140 483619832 545017890 733242608 488569628 171771980 651664962 69903503 764629544 952071179 765105348 595737896 611243095 506391450 816230295 30043955 895938423 776106658 183545278 457416335 655673023 440450080 540601911 991052179 337076086 503038213 232357474 861653488 126173199 227490757 20665544 992920338 711110588 418199786 578679297 52196568 589971765 230344259 122100070 207117660 34931789 739721769 802855555 646174883 98629570 471602201 528735190 994567993 100225210 564796819 304500679 755898233 5246898 697618942 599466763 194839336 200657154 831824236 56492823 326830352 59314992 929674719 172267041 622941931 347874504 750946337 675138498 790362620 833806947 649754919 997480280 868738736 241993039 652852186 367429970 340622609 124454387 896165159 187706953 224679596 313478330 344723983 980577828 171241579 42342924 432560942 366080914 95516429 116901529 275090089 422346780 28732872 204764807 447130172 651674803 405155662 50592861 179329652 195518281 884399807 681600923 45514912 753138542 923593961 698367098 120568512 116732921 822821484 869250022 156956225 900017431 35244703 501680208 733111611 206486282 544023131 165672552 572567195 639539560 282574081 847657283 914402691 311306952 52422089 361532863 815498106 310094102 412125723 994827758 505612383 149041881 528945032 551127294 902180423 305055344 102010743 875265286 421788265 924832226 597031659 578744489 677366009 632276362 80424696 410477619 838762643 476964179 428666522 263846189 969020090 711240602 111503472 883422780 875063906 16441912 97471994 690562011 326536014 362114068 537906120 684664748 511155949 66851151 88308393 265852723 224422847 190319136 141118008 646211111 115151361 590666018 77471951 645033721 75458731 10412999 55511339 766737725 339893529 336694213 30583914 308913618 47934814 142087385 44852749 775515071 11045648 142324743 318593434 190098013 356955162 856499553 874762760 868111110 775867056 963071153 133963832 289902 153390288 127598191 499017364 121058000 570780561 429005666 766091721 646239291 439418664 674119411 265493368 779312192 10813623 296077281 940742161 911264789 290681017 985594910 539296211 154243016 980436004 857889644 344341029 189907517 566905549 219103788 58018627 195288956 34691292 44498810 48095209 188081579 172097001 547112572 161655931 742877561 976118237 927747651 241633203 268053253 454383413 507126570 899881796 317713388 655720202 840623957 81494528 946401218 678735218 620790738 100644234 511687573 331196734 297501614 701595089 898102282 516605401 612130067 93391237 551296693 656628877 141486445 591894623 828725877 541115368 753550553 424119789 369749956 533814555 518269343 637803208 988197968 25395913 390201356 158427707 533632466 83341664 92438586 332550036 762076881 713229323 285710621 126280805 44426056 583212234 680392245 795044689 99817634 292522312 888435925 503630678 949151188 882438721 95525301 630393416 423554088 701592205 907029556 793304044 235406760 425298898 283623603 76121079 303211162 673824958 87065137 836843628 757166621 179503722 21910015 371759853 892733044 307620635 350557009 789675452 890832868 30949254 437236492 843166853 175987917 178188769 199313883 125139104 60627489 147355535 608048871 336697929 848947739 367594778 130001972 84354498 792893675 266141926 12991928 948621189 792483236 100057064 637981168 402166208 279560785 659891182 773926061 24810181 967511816 124483069 667001984 858344683 7948674 104238475 554027887 183936590 282427243 753341769 161592045 195571084 900697303 622157267 532269012 749645042 989752044 514787335 686515891 635162071 780929260 552024171 583783259 425928847 652081234 74280778 828095055 784158371 734171959 454537467 808968551 701683774 431536887 328486886 412544808 439485561 432725360 966572694 475938502 567668955 572430815 637530547 763240038 473128117 112204165 295509049 75289510 101956209 810296383 614321753 737118279 443741994 166345923 173417889 869670841 670943508 247698666 550282247 455101878 981870624 4819713 116586780 536070749 436356599 445073665 801131908 728358511 730315377 620220953 204297013 297984331 192651767 694343911 61224368 518296236 806548075 209249768 593585745 908504283 872062502 60423849 498138913 168320847 226769771 524073153 37991687 897713279 771771818 440790285 205331508 606158793 445609997 174434640 994745893 734482948 619508304 795877800 462841458 202340032 268615105 519654822 500324362 461266871 213998732 414065081 979563106 20546807 475831200 425665203 781567441 347893701 486089051 132222706 516214548 565375174 656295858 406722586 315604804 280584028 847512871 520936311 739259172 145639219 695370950 734005065 880122166 167395606 382399216 195479976 369735637 651014320 715134797 722576351 964797543 781649881 136641431 796877000 654713039 464988983 75058554 288796831 812882683 561147605 421019536 181613582 126522778 929831746 440852520 294643933 62932125 140881742 815580243 802191296 286520960 363467545 388712712 19159478 383379502 771111928 67155805 753115138 274642599 782290601 328207840 91956493 416456833 317365623 888833493 71169871 782354605 963892046 359966702 447753639 377556002 633502589 629367221 356595131 563334334 70219740 651239063 626266458 63617833 319335658 280974106 350138792 682803202 669686817 221814621 66182703 293315096 288970425 671814192 567957695 71261026 22032 659914187 340234210 169904006 401264031 411404081 952258610 365156077 623887134 400012248 742712078 257389722 881895820 99307209 673240408 804631911 603062623 152023217 868249743 922398280 432997322 70904887 457717833 102684139 292719507 376416887 395999234 581689932 48231079 816473280 505467309 900769462 328903819 845701518 70673467 730167849 109621950 875448428 95323925 733509083 127977027 690552355 990898805 9872847 642375915 516655564 814504757 97954889 668678780 535270852 20353169 101676102 606175738 478071001 56876592 898895244 854487888 452875825 480585175 755235318 121865457 986052483 508521131 450769275 684270353 431710949 180937123 793892302 159675728 128777400 527401385 287652754 671846106 370816541 297525600 166738372 887472104 964546709 264693260 408667235 499817560 285046428 510343336 105993297 615633781 567219927 857404892 322638020 872612104 190506419 77873337 994477560 29075253 438910819 445246834 713345605 723138119 478700308 507237907 882813846 607477707 887155643 170466599 131840164 110488535 320508551 298578535 997960638 285055259 563271795 259144224 637389170 848318222 769487560 595898818 316468354 189223838 453303709 639106373 61835941 643810127 569496061 908829852 672885380 8406879 206593037 238747336 584061349 685293345 745985242 466875194 145287403 485657236 489858145 277127567 596145770 810366695 575706101 446622759 95421953 138977895 705766983 585327474 839812469 327770894 181226291 156280822 516994731 487046351 795387195 431347024 130856478 217399607 192693227 656258209 78322838 399286264 895005544 662384186 84579608 493507138 129259380 229867010 979164373 471633876 506994576 427826495 282000570 82700677 874449253 229938874 74194923 580216235 815266347 914007391 907987128 849008989 922804565 277498211 336055339 570708111 561361586 319428168 788107717 754054812 828202728 866430554 153341075 575724624 528814740 90437034 69231761 510590471 320304044 900912485 982224346 679814971 181255331 116741267 615031999 55704584 199196492 689226922 488437170 14462838 455750664 248940650 715988178 231071580 526438860 52043516 801779690 87800445 223988036 589887407 694371608 52190763 308834312 847712683 480431738 837649051 938149716 402179850 200755873 110970111 155608687 35496570 790785082 336864017 4754188 258333432 392568600 203950679 947560353 881005770 70929868 255827369 129946419 786918045 486898948 508901630 691477913 141194990 449218426 915465948 731082396 143590033 820173062 39916707 843819067 153121152 730082110 634485135 555301001 783354334 597971597 710909687 818850904 241273030 47773704 823605091 499606462 292858655 27555770 299683166 26380776 98485637 555510534 8843546 737920034 894925834 517745175 429397946 36120823 819479952 197380245 619719570 815586337 870069658 512152628 511921755 23190809 94751089 146406889 578491810 878105423 596894838 141917848 549472678 838167867 189691551 225594120 337774328 482550206 105666241 637457494 508930981 56668230 45484379 517774527 794588263 940410212 888036053 76502560 829047386 707516005 273882804 448766955 375618693 143952461 960919583 887540447 19659622 55670671 886463688 450667783 786292445 483358525 592585630 335765122 174042743 782277181 561359242 511817071 117343738 667025482 1790916 478791070 723693711 47275294 996565596 370798325 840201858 737118001 447300884 521765595 297150357 721183687 970532550 672769049 717652500 783968484 560309495 589828473 692155506 299289534 40496255 330964303 782648058 633081884 666729424 956690801 267875416 80605017 321024223 237735505 600146851 175331490 716526575 176356913 75123135 565608522 547155238 915324992 302726522 994456121 289606939 599876878 568156160 112655840 125162278 138325011 896624323 685471773 728153483 441296180 984761306 768649737 772260482 619925716 254247972 291506258 429132868 374639740 224627626 602673442 612375244 824774476 778004931 328901818 1131389 853128065 894510340 548286626 620969409 49753213 395259098 910576347 502146443 963415257 23232186 627308720 101740267 772372860 165296844 829893749 66185391 2574502 451059837 838445873 622500217 557824161 982468482 904149436 932463900 207096107 506822877 544839143 31870583 137344159 726257313 885518323 990472223 473284004 286321300 611441631 523037216 681580397 374534329 25183658 644995654 397766514 505008730 599252272 22655725 670305573 281662373 88841116 672880074 732722209 927286988 147896642 143062721 762271821 52046077 75526620 969367927 411385305 472882115 853754861 548729463 199139427 591789535 539201686 672423430 878110834 3159668 47976997 559691231 377693997 925677007 57203236 627976862 430685736 656455507 650632587 100991308 938117879 739473702 626387734 523356440 519277041 774284375 666419160 281548861 826330452 594462132 103433139 90232108 67344246 809704352 638961571 119000024 401493886 30679608 791423453 132121072 33839275 691916801 691812302 264049623 617593807 601531889 892026485 900795894 110503747 542659071 854303554 48621626 134649124 480691287 424494417 653926164 107492013 943429928 935475024 933822464 537892059 891424514 24054572 457752656 701128865 515532494 576752679 955139103 546212101 220692483 87260174 580051375 912609284 631588827 844100998 382719442 233120715 588643834 283515336 343624461 131302904 137818889 244762438 118468379 471026527 521773206 772394542 578518539 465203134 560385917 364857355 855611544 451810430 241428278 313364200 5455647 756960771 890116878 960594749 155689223 110809361 900371274 735740597 875934996 531960100 432357946 258654437 617597166 21001779 394686124 961221626 4821034 385021364 58500416 123289412 856047890 580273621 748200305 287082781 897993106 308586221 504456487 753604650 612913003 745884764 919485201 618368649 355361886 662118430 431479749 511051108 625444142 184367374 99308056 501379137 716327473 384182354 612549926 186440990 257700484 7236049 178967 115037870 392257413 58679382 90843633 100821654 491469355 839043938 240420786 389462460 146510 744877272 995583461 613059512 343278387 915068661 83944512 698640272 429703443 515424260 62207731 55147584 699791633 14032139 409043073 268635457 398214492 21592998 455076446 655914975 28829046 455255413 770952844 273602810 366451146 861796477 226940816 857920500 700840414 467361601 99899312 700986923 212238873 95482772 166562787 555517259 863067785 250507298 106673883 292771227 765931558 21397965 200435162 318239542 35430103 609478234 439391351 433644594 631071231 894467796 89559569 512416629 202239560 860512412 638535790 568690706 574825240 865476605 279127557 128182005 332838206 379026868 829168928 397593430 474509640 995731714 953110688 190093776 98755363 912300922 482865002 864686920 933698887 683300163 35442814 969128989 145294749 474834164 402773583 776365979 221818311 344849503 141298959 276574223 57878266 779834749 845264928 632703506 497827705 124392484 760885510 830665910 355935704 442570789 80775691 830445343 290818854 33886379 20539118 389574217 798703652 355920471 106777488 732402538 891736985 142220301 554047879 37031733 469570816 956821461 665914064 691389127 154187315 807213022 967963349 212065580 439564122 665744628 844769085 937391827 642653463 605654595 620574088 998589166 48225383 701349779 681550860 191560589 587752509 554606329 581134805 238972512 763043151 687912292 971375050 654780136 830132593 377939280 544328220 152219760 187277092 210242283 843608886 341464406 869971657 664088586 553529985 162052130 182349565 398299070 99443956 677519380 856470016 572534396 528624897 757211750 126400526 62692109 948772338 566669386 617298437 529907142 805641897 232857940 70335786 629533298 887638075 900468378 7472577 284482646 52688137 194749668 494724929 748813375 536214073 217212937 265418312 89744058 379265066 300284229 340559479 331225374 977803608 49545846 903759769 506428504 806757595 882676646 569120612 755529933 449346031 38935401 137953426 107504279 271793340 208289211 737037577 11947766 961273940 744510153 296430411 866478429 791776173 643671691 467808155 180506597 860884627 733226466 122767006 240149693 33510694 463326484 571375066 863830653 512872329 327651186 222775509 172146276 62844183 791896120 927676208 512190213 683347872 918145985 619694491 955141211 126435196 209248419 819605328 940225487 953758572 116035739 806703915 598051096 612223781 127028421 778557692 473108408 860254887 901324698 565774452 746281932 217167533 137149517 462628937 730039862 317317054 685404445 902186137 380161236 329816916 682378696 744867800 13164788 453041032 217078642 820822350 431992579 426327061 640427678 372218066 232601984 608979768 31438332 830653079 73719900 158466753 609210770 546828307 871237991 363051819 112602758 470036274 580219352 102268626 932665210 162775565 272102031 618069654 64961701 504779618 947886570 599856748 249647417 813567709 52897779 466726059 634390058 337406710 893053119 127334087 709624775 125655102 588830206 593579458 808824532 662550106 752046210 270551653 61894764 475800552 633603472 27013874 945836826 213822823 129282499 878502035 376598387 253900882 349088041 294076439 758680499 149490962 746449538 860844268 963058670 651863668 180086678 449965079 989270377 73139796 429815518 551411503 51311249 18645723 144990961 712652132 681195828 749553522 983203784 743090592 225354074 616807255 770104465 23707251 683146429 751903315 902209285 59744815 858320548 103813677 206337605 469517399 105820990 952787142 330361666 68879659 457167162 510448343 371361090 446437538 436104490 801176607 997849041 339932090 672338681 995356353 52584221 206050861 744909874 888304356 949141452 822780299 357627963 571762268 846487549 40774391 176181934 601213186 953035558 34502482 705026862 11889514 356536232 810847852 964676656 686897897 732243862 274360169 49862591 956121303 720797706 338483432 609814261 571163098 678415521 282152942 419035802 583516093 488203802 16462028 324336800 289861605 839242326 681964762 714140224 685729875 722739153 890322157 139459412 528291062 777340990 844486273 540180575 133877221 507850476 357373582 673291469 92610690 631733750 575670411 48731992 205047808 914153842 511062605 776210905 445085714 793215546 47763059 28601806 133935699 64225086 205454958 276313655 903467411 887419719 990453878 441713637 462675223 733292386 581173048 990966284 363149728 278175673 531146859 349543300 786026148 888520440 22834769 731153189 372770542 451021531 632401533 577818349 365175373 143464137 206545605 810261086 789196034 254308663 691379244 923131732 318533748 896834201 51961738 222001159 636770271 42415615 663714795 99445494 775708000 97404195 90411777 138857727 375579867 474074987 340917379 14122366 215111779 216268499 745275555 587882320 667290029 377677087 18217020 32465401 373657575 224762624 695242839 162853608 479071287 239138434 938501691 797605034 988488986 990463428 19606192 625259256 32879042 535837339 577221101 661103393 633241533 520149230 652477472 8821399 994224216 993394850 22943764 61852346 62179700 620735670 502251017 729469728 998412756 520468036 614451481 224586682 745230660 162210671 387440289 224301946 401349104 178458331 21906979 242354441 168921758 894029523 867613696 54317151 282383213 297351149 567936896 768141097 817500378 72930719 629478847 664240945 66325568 504938962 726093291 128505267 125674632 80860659 710491346 976603739 601328695 324942826 201190421 346559354 487153496 441147061 423377651 741018951 619605392 297800981 983373391 788527149 44346855 703503439 695360652 326730067 854587 263297547 94871163 818354964 336228265 576866361 335112260 255070184 81805323 61205550 236091802 59996306 142066209 946583147 36600044 595911255 124042325 90306816 942470608 463712172 531453877 218364610 204731123 151059268 516165590 40620865 792102768 560512445 744124303 487463419 887242511 744978889 603277317 834630026 415850204 939505581 264012738 750962464 47092116 345818060 664684365 135700269 405814365 659266925 82283416 294930761 107694531 58842092 385237576 50165138 522554263 916691452 121046099 579801737 67750719 637211689 620422602 712369839 197724133 364546904 52349609 937482995 962042145 655626926 624629372 230408700 447648858 888642110 981371163 494740974 86976521 498571880 630441242 492790886 10355156 565241009 787721646 118049687 476599452 25475573 20731176 999153715 942167025 141777275 431471803 862434095 778988963 51894404 574803933 829229447 268957660 627153542 766712441 230999804 135296819 243858165 461408503 582945676 132500274 295296018 77686649 219476794 646384249 560644243 564784031 656739404 978401603 205022028 627305442 455001055 230497601 648036618 306671121 172664625 642330244 738142923 35098719 273835558 642553679 462419004 103065004 911511338 942088897 722293796 142511141 77385715 966151960 456435995 660331390 98652233 604248364 590534391 170645379 250632612 3694985 735429409 759888368 982096587 940451437 387193809 289613993 23465389 887746778 448801465 196130013 530077021 39460740 83745083 803912578 682014418 398680438 759493933 593525755 340769334 481787729 588553247 270671400 300456040 897505593 931002790 251624625 501753957 374053532 422270003 604902920 230264868 10215763 364791287 64877806 803183551 604501448 354491799 826648939 492248225 803293263 22778951 874841598 842754002 959040386 531270527 377284771 357720823 290764460 970810525 551006509 625068540 411880123 821677908 925524579 161902068 605197049 177149203 663656024 979250580 451935557 121075295 62031799 462151320 485866582 126909605 117851222 90368029 481401403 944500161 435132605 137211017 819795463 162490554 832481371 778835848 693761081 209766141 989073023 984525540 33093018 540079531 462110431 297489492 214273790 387635009 459391559 819470839 417300564 123047582 651237770 869236120 96639229 713269569 183903791 582505810 840179173 301755013 525390190 174096927 246255173 813039146 311307943 66050635 975529700 143789313 697402835 669290780 206071806 538992209 506332671 91681175 79071739 968443101 389170666 145861880 208594461 848562225 965332718 625895024 824126158 616570488 347647496 920765386 182356408 531551286 355787547 22535580 833306298 881177736 196632506 79561470 546733234 360456800 998128457 522262933 356762465 548047643 44070064 562834270 87039851 402919086 654515444 18627941 223878538 43686109 17006172 432472998 744764685 982338890 910884374 568890843 451425729 258531869 342172580 633782136 790083154 697960127 656317715 475905804 431654214 705466572 407983625 978387447 65923371 258628433 353166731 422685835 806676075 397236794 838036456 746232277 800155879 345068251 617376569 24034416 241270712 634382741 309023766 986035396 469237982 72424491 407442590 920663710 330956359 749615170 554445845 973555864 447575296 63279911 449461667 879229509 768746482 857445292 710133308 687186204 116073724 63300038 109872039 775266151 313053184 800424846 374014779 113209062 145493097 843907700 989759830 386763808 330806792 151299947 225315555 800044773 223724437 632758145 720708482 407197147 382373314 127670678 380753010 682464961 43466940 682731029 414210821 812213421 392692672 124344128 351915976 361282747 40160518 314304366 136548897 353213701 114729212 363080028 318939114 112738660 59504079 161215295 499502467 390310870 312515241 724818021 190355642 388756029 210092517 763580475 795953175 592465830 891251152 29222537 127447142 934718091 711953565 541657963 599447863 104646236 666002090 951363838 465928982 706162607 118184556 454994231 59376307 232913767 670590610 230831773 345652426 730094688 392047067 697671244 120405557 704562308 275005616 163277550 93318336 485098133 926858024 741787863 77563962 670625527 771010399 57527456 457859969 482963963 599185418 57307831 440126550 117703859 861188020 906055531 823866466 979372575 213566113 735759124 64802693 884156722 966590896 262971470 466767761 211154315 960642713 587173317 915716622 235648329 750450866 861551309 720746461 529825241 455855523 650826774 200450767 226865921 708354229 658310735 562346235 160055998 568134917 2472784 277759857 281839289 761044667 101626322 113728215 974610779 689901797 31047260 711283853 509009045 294018729 30567965 720163359 254661442 617741282 488396332 342826122 220708499 202463992 63572582 750533740 658319515 566915707 803500858 737701787 127786288 314327945 300048022 287842285 882462861 155037157 565602141 16818501 916081823 519744814 130546716 743208954 62162963 14110327 307009158 423688359 308129055 337577122 143851717 562790496 955318403 484764400 905616617 28543254 539744743 821705550 631593345 50580609 241137609 435094202 788282396 221440248 749422146 88330417 509282532 484401359 95883925 927401025 353736211 11965748 299662190 336799278 755174701 361825152 350909604 62183858 785513510 659038659 252277331 781881578 74345506 60112086 119162329 979962123 88655339 658907072 654184024 720248683 709487680 747837984 7859236 350286427 969278231 609797734 291133195 331077115 94199092 387017120 258478139 300451654 398982867 558140328 637250932 6673919 772481832 988160535 921374128 410511693 647199193 173651458 44909623 721544699 233763543 164071951 554023173 174935233 675495374 60723548 895183915 237499406 808561532 755559503 587785832 630356114 365357236 878919027 961433228 312072679 265936146 72427718 612524332 517435364 630568046 102291615 524109282 255566229 90452150 297999761 666077921 590167694 471651218 710987543 164228744 557931113 875059494 718251916 732866345 403071219 631491816 480566612 640570624 292569699 236126114 228356456 922925812 453999701 107275482 884359040 766072379 225727979 956786757 231113062 743163342 439871154 333404677 119788975 695437382 276373178 417788735 214031655 866540871 741956304 925019197 30769615 299887416 652595042 601537882 32753761 55666261 233029697 365836724 696236884 525599395 601962837 777109691 301041559 55962537 736901524 37916950 674551267 962629502 994703706 758180680 558309195 287091212 91585356 530614521 835044945 220474885 948403255 49076599 87015756 542875911 974095796 117785370 842763326 479207189 571839603 728033438 534873449 804869300 93870161 83626685 182985046 548349349 860736375 484026604 456828237 450154251 521943553 983895855 265300104 369163611 742076535 823609299 508771174 686178242 206740171 343816118 906653127 7659778 245409069 846185234 550535688 72021216 816486955 245815365 551228404 388326557 973848803 86101853 45712208 920235315 22244889 81213606 321101016 735497615 565240209 630445604 185651865 939700114 614341459 450951969 161380076 208934345 127077619 670151249 747628938 333817789 13967366 506798416 341477566 111892786 352983649 892013253 183914001 21986955 137828618 735142405 410313512 964193772 673760609 308542071 736945438 696005497 389755676 910562805 284019463 954995885 541008409 469671328 747212350 7866219 773139648 908592425 69316915 900217266 578743673 816945852 86551406 445227390 323744268 280545324 557120176 529244268 25074928 741034176 551231223 15419897 328692932 961544734 979613668 2453540 122603156 569075458 550975388 512358832 332154614 834994851 319871068 873163022 157182530 67083417 733545592 930322177 975675841 802862506 683055794 406935865 619808358 769607199 704679606 796068977 50152522 114316133 325313244 75227450 855350309 876544466 90647346 36559592 690605551 922777366 39013132 813208707 344369175 589988519 178083890 676523788 277499721 497954957 402203162 434682250 565038373 135748753 365004426 393230565 791127611 48060219 652682781 263452320 670183770 357362386 59521296 572852643 471678519 237350891 500596444 179545179 113895357 443760142 216104770 657017259 219053859 107634253 322742317 415939385 697622772 500826206 92463172 975122492 998781162 347182685 262321094 416335886 335447790 627325519 662082802 126575400 527902090 314765582 242544071 50602211 524644320 302065366 475971205 996322838 539416256 976567649 28384368 505827964 272844142 97005489 15361575 344414352 204639742 190620243 760353736 902262513 691446449 705333259 729901356 542743962 52515944 992222449 811596200 240480085 472064320 473679001 219571836 852482761 640960935 462115906 903084971 165605254 616697623 231572527 14444443 8630230 60656527 42828810 514458194 333500668 139834298 382336120 677915019 196990391 572956362 290785106 99252903 116919162 996118365 681670611 659663124 901150660 526409411 323775675 141630744 850990082 797454675 213718931 703472842 290931961 528351188 459074164 456537214 145048810 690646691 323498008 153679039 751303217 218843169 520653584 937320237 211193819 902989703 467751607 408184209 475946065 758536713 359953464 592865226 754655077 41624074 105044701 508322088 420549836 428820375 502469183 124056270 78791402 716188113 827529111 369723362 97055652 139119627 678776928 242104461 682282669 2274935 248299851 286102237 221118104 768953435 223422473 432311922 671943137 691174080 840496130 405553 302227144 52965945 445787131 56882220 94590018 550831831 417720659 367656206 832168558 920189841 491712475 910959959 488894305 171757937 133199672 585949956 163393915 811976599 828054416 845676583 666767886 76354266 131778820 887885989 697824052 207717644 172714262 222283541 898891723 865726743 222689093 53635218 918692688 668476223 110517437 865799057 71824406 380754447 85971614 903992963 300944287 577684088 667469273 789838591 601958377 653185296 228304898 765352291 317678247 56359313 611028874 984446132 985229931 595324045 724848472 535570334 803041688 897562733 757853874 554449763 615805827 980542967 608084980 534498514 501535541 571118769 252813923 425876298 951873215 338785536 182385612 105333854 916469624 849854884 895172444 370944352 355556532 123477342 136296642 673234778 32353006 599841867 657680909 870099288 195165911 235045732 258185974 998207599 132608464 16039847 405173713 600930642 849099165 13258692 135429156 203151058 584377460 240759430 629027355 388767027 579544965 811412967 494100880 348530940 513784202 241789675 719475291 869340733 217783368 855771933 542575510 102652726 308130151 52772770 972752013 503296062 287818501 83454338 354020012 272943316 99494185 759193724 873873958 948593349 624968767 861819465 4260758 61862579 102578894 633288113 450629605 534640210 444701079 944730484 883171150 958485280 186520158 602646440 680342365 404303526 310934724 75434226 506956251 619064875 128206996 332224615 974877288 268541848 415678953 181413651 541485164 367689489 940607374 267875473 168799189 418092492 982211289 173059947 479955070 937306534 806348059 930584674 471946743 103565489 875315157 207634244 62050768 914351667 810280684 594909484 171171544 973731759 670343710 678127794 445312985 798550705 862868760 420190272 67092552 131064064 601603922 461094067 498753552 394727647 581485891 667552741 812820139 563697179 840612687 145291560 353520064 646960745 75876234 825466807 750526233 803707742 33101050 665093352 718059408 695898085 112519188 889230951 522146196 782862897 419875096 967459180 433929953 135260208 240165804 353538856 266324271 841769725 814632923 765077823 89013724 248635165 432630563 754350214 812332344 125759601 899641773 18368759 772720345 975518006 843835565 375762929 631742100 729452967 893372632 202317859 277867403 5891819 91548810 800013598 788754715 363940257 619989130 75201019 499200464 860154933 428739875 765524735 554441009 95889149 383118909 643454732 344524313 815749471 250321297 9373008 941509071 149963070 27741767 566745767 977997427 871577331 795025047 609739526 453546649 688397678 812057385 583930404 546805849 756122546 236460353 188076915 972579154 856449482 263277934 324295970 716604414 692017808 89820704 123561775 787906956 325455964 767016506 132431268 141205434 17337803 141804276 935230856 19817224 169546042 354492974 997814650 893639724 2034372 460070528 199702725 690432049 124644264 783633128 89754249 733283161 20093480 277831164 705862314 876542962 541109097 30158283 445663727 233126904 972495338 569225501 21033859 150467653 188758359 5981478 144189438 58612513 302105 79420293 78429736 169848146 286429618 928760737 63487870 288463989 241347616 115706946 831412390 218508231 899340073 921166638 951791391 919433552 198997801 510170057 648492865 740106897 392844691 946672944 825750152 217856381 368414796 699300362 368324033 557173154 705281840 512513471 468302018 705583944 444450115 399248105 727948442 730879733 180525194 643952663 871860073 421872809 759659608 703272462 640381040 658999680 476955452 444688782 430949583 675953252 954858838 931958800 268576501 347703529 878631743 94326652 565559909 99562890 646143366 933883941 656736044 203941557 298913763 125038061 909525500 743363878 376802518 489990293 326759962 557327711 133942955 198620034 979200519 893602562 754408848 472097910 405118593 231364299 916786692 688584528 759833902 724161881 620543327 28410402 71865409 351691421 975253406 489941669 451254310 473913123 276341962 960506705 677854679 575255724 938061118 439896530 171135953 314863635 929886823 497895914 872191345 63829777 696515948 703908215 809948691 303441147 28522477 67583635 534805445 797825520 756168162 147155698 521987400 229227840 28082452 446369161 433435612 3335857 788827181 884689922 329765331 65169142 697712978 7620009 492941218 635774095 447516538 664077170 803154081 229919712 14489436 527861777 146265841 711005383 84286344 956214531 14446529 112808820 876314517 401768325 910634339 484999031 548924022 285138090 714226870 577006473 584023602 178834 432858681 372850783 884868755 762624011 290536276 435098084 622760371 635993845 70872179 70276909 152587367 726542611 152712972 167076802 254404388 298978812 878082184 338690731 107709694 745045064 304015902 984024211 999329740 67166592 469023241 400770113 352304681 35766462 977776586 936328283 35945295 263151618 161695417 773330401 878291981 304748044 208428485 501052351 940741889 131817015 423845611 93329255 858359625 576558583 260406056 965280364 875537394 991004591 156487446 983247088 588566006 460503347 819787650 587895745 527669938 141327242 988665857 879974619 177093703 818958794 668819253 65555350 934626764 683031021 838885750 812918744 987779064 47314234 166487446 928520952 31647600 442849409 874366558 742523577 19407991 134772613 707803940 747461736 978293555 864291386 583225175 566859560 177311084 255529176 7271656 704981022 396856417 848453865 437471992 573950120 519929010 106291244 639505469 454555773 641838616 330907570 119990868 629617679 230738156 138994666 410654983 262385755 581844074 137537892 4909331 453768416 124826857 565229623 53746503 103120411 282037360 636971678 522496323 459348443 892500853 529767978 16845816 141873622 230738194 454317807 715823741 750667204 413125402 207845561 57739328 54964017 538753130 177730196 537098048 769491285 316724861 947753030 884393392 898568934 85290921 741819074 204853701 62634129 159565048 258600203 165754540 441602407 895571880 688250862 753467202 640589085 70535191 770313017 782462706 301273385 224630824 350802798 51940588 637756225 411164710 109679915 545236594 949917839 139926462 82334641 571925476 309167674 882604022 308835219 60252959 820411294 50654292 265106659 883045423 210219340 523706862 48799962 504338098 271795093 589567175 257805299 912384177 512618717 28118316 547363234 813892101 105265491 750682383 718349040 595538067 161847092 680545307 140774660 964281283 672988120 75625652 388723110 982155794 958229673 697558328 42408752 778640967 748212619 307515411 514202741 810948310 831222272 415519054 315286408 103017364 5086228 425608058 867917893 370221296 306242725 267797478 36629749 411508215 18479861 754978788 7046282 32843304 288040446 337293 997124586 961028566 75962945 238364047 795700711 34192617 935922374 838109462 665349935 536651345 998141224 32069027 347599654 681879847 447588080 515402413 637413563 305190659 941010471 357847807 675411955 247253195 625645284 712041703 511277762 496641496 319536842 370840395 382001152 607577288 371177687 231642089 421122205 299656983 470006136 69339267 186365952 405928509 907448728 851715886 942579853 758106304 883784913 142695859 439986150 183889344 658098271 77399712 489080003 451625093 287763870 164491957 698878288 913409154 876533659 62672401 262567001 48586852 433512795 644568152 656164139 804690481 876210241 929802695 104347464 198732728 999141961 143229767 604661236 759107041 994945652 399757441 517213344 731246916 394969651 809715845 915136260 53067921 739631909 256732614 357209366 27395778 421224570 56087653 793321283 150274580 118760053 55888284 198861431 404789199 552972787 707541922 61996031 281699379 637344616 18859846 480432106 489002929 162089612 937609694 248109969 9551616 189883486 617839664 740798531 584853136 427555508 508451142 490437408 19703768 765183755 847646773 47099546 38924676 756250777 840420828 41715607 727527181 748825463 240577038 132316379 154314602 948118959 194312410 288530332 437979926 213172255 768962438 926982854 375261867 559088483 27609174 384813482 748971968 645448837 978128364 333825103 925520697 339095858 824262510 945224464 104279612 524425635 992324009 995720640 280676411 685261189 37436246 8203592 286603003 130529635 993036322 293433956 78648593 39865083 581964288 369144871 253037338 203443077 148644076 480815556 762531559 28769602 865629037 511503526 674218438 696273752 697844980 452255486 35369609 374623841 397479950 992165573 899049475 242320310 987886212 32242238 780097850 877838809 40445829 66700853 8368444 885998502 212651160 939533388 925863585 794615447 161194610 31417274 998058523 309838686 512232829 760590081 338608287 230378217 124609958 865343076 926651968 822454937 317598562 962021577 49595130 567594863 806703501 948644604 809915172 647106064 980886841 442529374 524944872 873849021 361746578 385829667 759847523 574397737 325363055 538227459 369013184 486557664 569644732 219588058 648912701 81877560 980178139 987520987 312255776 957304448 705380415 91424095 632275737 22978976 53445671 681870866 443090190 712665523 630515469 105521713 359771586 463918662 548051086 737232810 337767682 909797663 123062476 950131556 484195400 300941882 488359014 705724935 787499546 58003745 925312992 288928598 992397656 758007482 128965937 157169783 715311930 834346351 248593878 200104018 709841678 154555900 881974883 152931867 867221423 365006703 258453579 79509360 828925364 806504665 816742169 19209398 568818679 939804645 969340953 53014078 93262878 310216319 611255364 880762423 220736415 536568356 22207373 213134071 147092189 151173309 370303853 862404118 985519659 618897730 62508135 695361336 773453630 796999369 700809554 493191404 162006072 959263132 572700763 990931435 618284148 389442932 10140832 39619179 181763928 831998137 92633256 275026805 142214455 556404972 8305580 362950869 92973327 30512952 428601291 92581867 181686260 798905144 954985985 19722270 270319225 870010471 715083605 896289206 519526192 268409510 389480609 681532263 80188993 962181372 524980049 698473141 204140655 387637233 738092319 238420934 72151721 683241926 513447738 214366175 92163249 374269669 429833395 37652927 404782620 858434686 130234794 438985231 509856181 85220778 458707500 780175405 807747600 26307456 528980963 179790143 294716965 918461571 861322405 374905958 733159294 238818806 73379098 789816300 478972390 663987768 28237233 551124110 199746045 394201323 765490284 291909294 768470991 47840030 329562220 25769963 906274715 459797013 464755193 416130895 397534142 923462693 48822652 57798094 949770148 577803614 237588236 244487113 348781536 951426993 619393070 934457182 42762150 545288519 724273481 521734539 61792638 605027066 72858648 114055034 999228388 690865283 405964327 767699378 738705312 588042899 793469340 644980027 47839911 110740885 913627273 297890405 34203577 962449924 208204850 983973724 392769889 445793085 80977188 594067777 249736429 552886609 528524958 292498578 98175127 105314790 814233116 12484116 710341855 887091763 126539150 562086594 430473397 385019828 182302324 169178709 973062726 975771663 666675087 873418989 86512547 580302359 23825745 973232475 395268635 232030594 809722551 640554875 677823678 890699738 234622651 927560107 296102699 615663960 72575036 246794177 720978750 886808152 259278293 283836956 626416266 238333794 845923550 56889663 623353621 28225873 78584723 596416347 856513887 745259809 322351687 795542786 178078519 346177431 621291612 573347153 578208024 431014162 66418380 108548053 174230252 301041030 36108159 470332950 916704990 108683195 717127126 490200091 848007698 828921770 626553398 474423963 67255563 324993299 383829977 690609184 205735523 462414699 139541882 62249410 207674507 461893568 710308547 385753026 808070998 184116510 811616530 238795373 615130672 878034909 347343425 641877275 31592291 235967936 112210224 948297280 197167482 681853701 291013722 45175179 363291823 917567119 372115493 430547385 95076770 755945470 973672920 300812292 218360168 113214801 215578053 278551027 427624720 925886599 664304052 88212069 110003109 328436933 327007441 577650132 206471842 674350866 72043758 238064132 910318801 36770333 38877763 107486282 718624033 182407836 5177812 81915855 99974954 377293304 364979592 47568075 133238773 191168863 348380367 204115293 156900016 563958419 482666319 584524735 342361370 999486722 525253156 304880830 327923654 852260596 882530961 386911847 379127813 954574718 624975978 141962965 991345050 516370092 101965598 562485434 698777927 107143409 496917641 651269233 336953065 714413584 698837307 322708189 905582446 47217673 379339833 62482461 611176092 862006151 499523548 953537461 714009224 24776703 110934642 41932878 729553650 993465602 281361076 108681463 800556671 906337054 103160779 644418072 275223497 57642729 59419857 974001424 17302489 408853849 625270656 354255553 123267432 176624314 529480094 28849878 223841987 908819926 943848690 687534430 623342429 443372237 493588242 337351652 320665291 604522883 231800881 50218941 450504836 513161957 11416755 103577858 272015362 114577533 747995929 547238858 24736613 659932137 373756633 42039102 68785986 999027288 396294654 44569769 28167954 925774747 73419646 252009940 687111025 869784688 939544369 310453453 165673276 285648962 500321456 486338567 890171844 732122337 536557507 340676679 97800645 400490613 444254536 222332358 367584497 44766816 769571215 392321110 704698952 143327848 434360211 626001289 994871487 830654864 670571058 23039440 608945963 596507055 127565731 148573339 466291742 919626451 459026791 631965018 205275412 959348246 118303584 95447255 543986934 507377442 288640285 494303930 907868054 585411172 716636287 127968902 630177987 338723854 520290011 187393291 334568053 954650221 813394579 181955891 637821437 336481988 57511683 99283751 932989043 185077413 247857089 251797136 104703864 706883879 883762153 162495627 518748476 854582088 110459234 915251762 214475881 251615870 409555691 974860286 837027042 126191978 102829188 319721380 317432183 623119198 507114670 652000235 430285771 173025601 833956125 68107207 509507588 891467807 167390957 295012982 76545220 415248045 546810118 33765435 974648275 283088622 48777413 345913102 137670710 11752998 261164863 204662942 263368868 523236906 32039580 100395909 501945235 134868767 420117288 819377417 610504316 779748310 471377651 40790086 952773910 157850127 108897292 314797849 49317934 128804600 609810831 978379505 396568996 9137300 864661291 371217270 292225921 913438703 717130372 282412982 925191701 830811586 487075924 41076920 354048491 519115503 141472828 855993725 506500621 414106467 527887493 117004936 193854776 999265143 10311374 999145037 9631622 119208665 166459238 58949555 100529617 776270068 37329059 497098612 785407367 754506701 720832234 77633287 520461755 290478957 212562621 298169807 121290542 699638544 339246726 327855385 71270398 480719553 36365461 577771018 894826020 564252954 547292305 941197147 416034448 557603678 940342184 425666069 529328695 106801421 484615623 629858311 735587840 374461033 979473274 373511558 128967733 700305507 303661196 501945840 990784463 516223816 800115646 964591357 68378711 139362372 292446741 139649108 472598276 328812201 569936477 219940647 893065154 117228782 161137794 161615954 527348811 953996329 587282022 56677505 913314101 71897645 539052167 501418292 298875029 518525441 874929849 280359114 71347299 31107396 782304953 914648114 399847564 434936950 879239470 468226274 574299321 24202562 460391734 46897597 205531114 882844562 119354595 98596268 852589695 280492388 112728573 379938506 87005068 700010594 289132362 319168 624424590 828184529 501737459 923299619 199226321 229183659 56175084 270573619 112807407 690996388 37738084 512654970 125933337 916977553 980881243 552749010 793696466 293789328 452162958 999227580 29150242 571517552 950340199 881739936 852009940 63068771 114194793 939015007 763079364 403327155 791850527 240020306 231511683 146104337 15836276 430738003 375287996 72011359 553827973 488095402 763007746 591566057 750371 741457434 361059961 834147965 294206443 154756427 980453645 746369400 6500358 9603886 170403304 956840556 891343821 22413243 19909326 5538614 813944601 635505041 261382120 458311479 875525346 492893802 604415816 891361621 776148156 979703811 815889331 329976128 320315564 431413428 921542184 173582286 172870862 135118497 860246602 319593656 289874923 840700246 65963056 296375280 702820483 88882711 105732187 446680656 111295953 125641512 304735621 777756905 613662904 566117740 88584736 341704602 59011541 693000551 85582574 687676048 525220713 901471905 17652175 845536276 185401684 791710711 871634913 358272545 926829207 731881514 677866201 69220481 425098112 596345608 218112112 127918594 685228318 323844298 427115601 649040622 302002161 731851221 279313878 915665064 297968960 367898613 109886017 209496852 60899163 47984943 897172899 438636227 949456847 767341426 136688854 134858530 411568488 8323766 345647427 190914046 592721632 876029979 112650878 17819743 324891938 330762989 998254688 10120255 654607286 277886641 511677228 956609446 9737861 643507457 724790861 160223173 11406070 834676878 369720024 924821584 882661820 119409275 215974163 684635018 739267052 352663016 672009899 3351891 360986782 870173677 194265936 953708413 746203655 306916813 824044507 71095592 637679801 674815546 933732198 144803438 952702186 297925777 101412883 814956399 941433234 826203743 975179571 805355655 513396972 197415946 582693590 248575143 316825220 798667752 785726512 56092271 3847120 310252763 59444161 364833901 180426439 106226448 171058665 779146446 265659612 847619523 702758389 903339412 374951420 489006939 48142849 180169958 786932715 2072083 995126356 580882300 680792178 970305926 238754306 46705501 20238223 673964248 295280644 337063443 325148351 81007155 245672065 328995470 243776269 157632578 693829370 424202708 116375377 717404386 55865505 382034989 565023908 758623893 137890752 939975328 247630831 38549953 120145285 887079898 40622035 967787992 320478549 721414212 790610269 559232855 768119713 810848491 85713454 915916708 428285 410861804 849440214 246100350 739857274 93216483 256249279 286202995 369935542 372624655 3607381 425801046 754659643 421147640 184424938 892550395 213639319 284572121 931100347 186300955 171652018 971722381 154088946 492130566 545652945 944699214 903879772 166289009 608064057 989593225 82205716 608492341 400455029 784162281 854592690 140312302 877378763 110841968 279031648 99830656 335982975 282639028 525631701 90642617 703786668 710056639 983193011 917425986 994628759 766809709 103726941 18797128 591048442 110332238 363444045 136701386 907547804 267323817 155506746 515611860 109433393 90228813 124104200 509888421 874391093 831213242 502717074 604286208 794571561 781748722 704116863 130554535 916904101 82264916 73713504 473207120 792321554 909422866 243149458 639466664 676232575 199392750 510780143 119797368 309724987 874224187 109015105 69789142 141548003 264521850 585401001 103497748 207267014 562021553 613386168 81658106 245751146 968619594 538460665 892839058 602884667 95093880 875909945 519788767 177358795 949623448 992995887 822196700 711562665 88661696 314179715 240311591 288054445 824959857 360108958 597779431 699184043 469124062 667568573 693248398 733645911 105485925 796746145 940912924 520023829 262648664 875087382 765774974 83784609 266064398 511130384 686669275 213674629 387040328 58974394 391033423 189180127 51970280 65746474 900742791 140631975 379926188 141054382 281202771 204886044 353679691 878982201 756586439 822803753 399067125 302351188 408966015 357069402 99097332 202395291 877093230 214262347 77482672 495384556 298046956 196063421 6514939 984716230 409738050 246071618 43690623 653287824 435251744 948177254 719034298 188510886 941325580 98960485 182081619 75044702 156362881 535761310 954026903 912949319 211081414 205610379 215300506 620047428 562679780 166914189 822442718 292289362 233692887 752441741 787673917 531739842 948505162 794188855 368972424 210759563 40260472 265179398 864047386 328028567 65873004 435598035 369055804 859714935 534558520 551137423 934759637 690921400 939415084 741302891 456387070 150496497 946913269 671687575 770543924 362109401 691118115 445502994 654398762 924811001 197944734 294589030 309067195 998966247 88777884 678039618 62242161 981554707 795735367 926289547 162099625 861608370 214403933 531155428 573839657 748962452 934809202 508599293 292400203 874224285 102418535 748787272 877237133 49331803 272991198 500297409 263957555 964109312 945800402 770872668 741436665 143745135 65461697 50503859 995227734 6755932 581059828 57469894 840826990 376795194 836275792 2926614 90919916 50679725 386598394 664759572 652158528 173923947 25875216 944558731 48148232 128293750 545862354 777901716 30141904 671369904 278199124 146615811 487995567 76515877 917488478 229432231 72777364 982950175 132452441 68005097 842222458 713512268 125474990 683049448 90307462 814267134 538492413 33743729 864946858 777607158 551019652 369621737 951531105 576894867 166696819 852195688 557704968 712559173 630097403 587846871 236445428 760812879 734462681 724440994 837328755 504467511 953873225 910106118 339934037 86325665 978111214 182156494 652354285 956102556 717722293 595178098 622886041 108731058 628921826 340349250 886338215 32457829 709970986 837869319 609352695 876667805 542581358 19574014 441743329 25195113 607420884 678188756 786007991 194399917 402629749 623336745 698867427 209019325 385959215 38801463 147861342 216586780 73474308 800215626 25205687 791196601 247910075 648091727 899927658 876831900 988440976 638782224 909289728 698411962 329167895 371158774 427596118 871749252 390732787 869339446 896944364 850670022 547528201 682952354 45069938 802674301 158805451 596453716 11693626 544764665 487771530 12071319 761351444 413762190 664803296 786557131 57475142 912713370 287165209 957402799 642061621 275606185 448701374 403867700 826534498 777869268 775026473 254130615 649618520 18275611 123470060 399079235 868945632 523514612 82031589 766531922 178705264 93353391 215501989 42915241 490634407 555789871 54986559 104502202 969552060 719789854 891059332 27027201 485019575 30740893 836946351 127081195 306347077 285647724 530948894 132881574 63516992 158491718 239528540 565651863 29283680 215514951 964731097 898229312 591545914 899279037 517277585 770251177 845148779 585295925 813166418 335783185 141085795 868152976 440285387 110637854 440459182 183861070 990181406 925478756 214601962 827127756 905076303 373465390 965291832 288541548 358863315 881325175 447033266 598391854 299493389 476316945 666423156 116740837 227062608 257969069 16019874 596856544 28220246 713685004 182152469 693903015 49468189 175754615 414572342 342269927 138908821 855031523 378647348 129090226 633026631 593249310 808734334 390619285 966714699 774026165 679160832 178094366 507867691 126194097 776486219 807361079 455027394 295425727 924101915 534606353 553394795 792638140 131462897 434131392 506323144 166131717 128034406 408307684 341886331 395123100 603093962 480795151 102670974 981741309 609885377 735697604 427506970 271136062 126316888 246738021 45162226 657994072 424832386 405546268 636704520 53834956 212907346 91731913 349260682 137009260 478854618 902655477 782163752 610317514 189303220 141003247 776449230 169853978 549310930 118335560 564977077 4921243 451647063 667648050 986662551 61532439 255862006 414169521 185184852 234695245 660907541 82863429 892689316 85739926 488409696 381910188 139574881 701317041 326158452 341351915 690842652 805013069 96523743 325522755 267846934 285826962 466526001 44296163 308197291 15836930 15148075 873174367 20758172 319311489 393338769 859937075 233360279 501717126 126622947 418545130 736412370 787530487 501408558 481618038 725786764 989818253 863528225 717877996 543651645 42203028 59229910 87010648 847216097 8270004 412533403 115063030 294096966 879059403 11875545 602294256 747412685 879539971 327984975 620687208 198851459 573840095 480624282 432211737 75557220 607247228 850756866 664485941 247294066 204681775 146103978 825597181 194500027 862148554 395991529 738151671 904351582 307737790 825162318 604084030 316007794 90212072 719147059 610104759 969271475 583538955 64915366 716684159 463078925 245416692 189887718 514446735 819256786 670512000 946658471 894814005 130275579 649931688 411816298 230085997 854613462 410436627 55683177 901629840 125101533 451674705 492297862 29453114 759412495 169976532 486053495 75420288 260188603 57716905 538041398 229460077 641255860 455473115 798660587 104334784 700889807 988548305 471297871 520146592 511576656 270472693 267476949 641852234 920404381 679293246 871938230 627534194 89729872 780137759 381680386 67347756 84328815 873978247 96800869 843741309 43954778 435370715 771677948 304143381 493087620 162235697 386119809 134343479 617708812 184780396 91194614 171114970 25845052 562492484 691261561 537421707 832965177 811254861 31790292 605885909 343064458 903728522 85936454 285310682 536382632 467616839 352658437 620711446 194111438 301975658 316969107 238066215 737346372 88647054 394725947 230433991 103399103 780845756 217293821 573624266 965626151 308488435 744739235 991471202 723497270 288517147 381409260 408978798 99772008 413199551 14864706 442836465 169444424 953317512 728147146 705827055 273450702 80805583 326538501 467562139 235297592 643507607 705628354 972643963 584671012 100354300 55594306 540586466 733716407 272888126 114210731 551858909 581376560 858949965 395846462 157390182 147467112 777255721 566368979 99755471 190455272 433750037 395108287 359899695 387067548 123255433 65726750 660518249 56577367 244781602 128080388 144391310 740805560 686225093 117035272 177992923 639095744 172629577 718579389 225328503 445517703 832790119 777187411 879410614 544256436 173033873 36800795 544239899 950289593 603169774 496511721 993261216 36919810 891620007 205677263 276503709 867391791 123920364 789538309 776485509 368701965 770135048 920876818 109507524 308876492 37912090 140016798 947972236 63058018 858596186 25817090 361092072 543902657 803004500 240502686 88159092 976038372 129819832 484915342 778844317 732989605 981427062 624621884 622425766 725563420 830299146 751445826 592955211 954219509 540984135 221957071 175437825 163635534 142833889 137461700 472512026 33262330 277478498 273000613 96320347 136074683 298817702 309928771 679977339 101822201 550431456 620652782 930376925 680251287 958084475 561737593 265757244 792027888 186359476 740699361 517591308 16658622 492145187 963062870 823394482 885645673 185019940 998832307 49281206 180370180 136294006 521793231 213632509 413772503 794793843 162469208 402363538 93611544 472397978 82340876 47950097 875345785 555510010 978327021 408113423 366110836 392580965 673870666 158138724 578940440 267086379 528246383 448115413 759231565 491309252 124026247 497393589 528845543 122858553 546674794 709215723 111668910 920984377 922848231 525441413 568294571 937833790 927804950 514422467 262748119 862662177 562372563 138093903 270688538 393215935 546207326 636799374 785796899 72594343 647454449 217253690 339680721 175700831 517885455 951428637 519526434 641911701 448822225 48371976 764770253 848013371 757587698 876439162 768997747 532952281 254396926 189808669 323302422 34718227 704231135 586050541 749896756 119120049 724144443 20585293 512335983 122868120 509901018 150649233 47978815 9871818 220419275 387659535 185572648 738304729 191604524 705099081 380216429 640426748 605987409 997503033 340956470 216091458 726458546 109954216 749043738 980855472 152279237 72346160 868090050 856510371 510913052 617986805 975630420 87573846 491088450 340482754 210441966 853505819 491131987 258420780 863377637 711551261 498596666 48950284 302372341 690201189 606565717 682588769 183144289 65069477 532608153 524100758 281160934 259066698 486571326 30204672 92438521 638850562 955067183 960528571 495360932 318496586 431031727 323507703 406070431 774636528 663990457 616512396 628142347 7638795 727449527 344036335 719190055 226046193 245502970 21562395 916247381 852068686 556667515 99391669 917138162 89275667 476008779 50815448 200858716 962580104 81020119 145813589 601430665 888603653 106342159 949307948 59616590 389890237 272815651 465687020 17043117 936806107 82199416 645185463 944444901 662165294 989221797 516151307 888211486 87241118 390230053 656975219 939309804 799413919 608883239 708964317 741205937 84892017 759779764 942064652 899988472 693316234 87878240 353935488 434436238 46736750 303243436 494052827 289143339 428575438 959739847 306186455 217897896 894455614 803888269 14859148 409137259 645626417 531010454 149865097 732867534 773756858 806840315 524693689 573170776 268239905 86174358 166893064 205648274 845954121 108957715 105636745 391786707 49352307 312088585 678739296 948605408 615332020 25308475 90265098 43907457 985048321 248967904 114321704 732020286 52856172 129180851 141157544 698482588 660191304 143538992 283866474 286464513 950379306 808560162 859635288 71135563 894734519 26528351 129300188 593204992 988002417 87453284 984991698 889871075 399541868 516247345 690992835 14873887 541555819 633774284 911297695 379120491 882742188 25619398 111140776 935598359 7316600 104814672 486597299 667507903 100870015 770463772 953972415 51249321 431540285 666124054 974901235 326274804 545168756 104201422 919479795 385687525 191654705 756987844 128074951 591196573 125751540 671584137 458586811 667307359 305358421 222400858 46427849 40616960 100536607 10084977 976215318 107853207 967416000 315328968 627877461 68286014 938309091 434366228 972051686 369849376 100490281 946952920 548640531 498175389 903670693 320636677 736379265 95325398 77624520 864454215 539038322 55892411 388554704 850141484 723199769 693913124 72542341 769627618 734530083 25595300 632228946 563261752 133448506 599644945 731107072 613842318 520447310 669416162 48208545 492498996 891781889 1215178 291968267 440422419 351906918 48155312 761059095 88286182 143480709 691199966 805256748 535035382 747092377 193811451 237693217 322808497 740240926 162751910 92436114 327287360 188347209 577181411 890549112 174312066 29342707 474172535 788154383 549790017 143588696 688879280 42289012 887886937 690094457 186773630 180825707 42001374 234928941 941884802 982803907 230926001 485601119 788060654 618477734 85209847 834388457 856170951 408018344 574629382 18922860 352970809 901916742 59786420 930152220 644982205 234098485 959494926 119154739 874769219 361801294 115259786 563648498 256606657 855663074 106259306 443380287 36488781 777031 530825579 830889934 983580937 761751580 169007404 624157943 232745665 254217251 311062751 88916615 514751946 885692132 107839474 867722754 640125225 20142245 650391325 137623781 254240729 462402603 109294871 129009948 824203896 77071009 545174797 80810553 932734082 503950455 376707191 821739214 504727485 907532769 652629147 340824774 521800700 821636551 817499068 754546365 928370153 128561818 695979331 443122098 866770301 656335157 163361203 359411878 676477401 666268880 497035658 930718130 128671482 458846881 912244429 805391729 535917889 309935577 738718633 321168322 813886031 967942175 142907536 171129868 727991296 648053034 364470993 102308347 322205936 181970060 856854711 103092440 163048229 405350394 546214537 29818529 61685550 562092092 389230406 738162950 228360971 738782416 521397431 209548804 197629296 286158211 867456884 586063536 448610140 458691869 907231857 115012522 426634043 902655744 286142389 7141690 403225130 650613381 109450037 577947417 685099792 966304747 681039857 848148020 224171492 79770745 877966549 285857041 641862836 119713306 876536343 870223806 858495721 250450125 932288961 908641368 536608336 799745845 494704903 985218475 110954065 254453112 100230996 537588107 9625207 238889737 544729797 265366688 742019469 654179833 843314105 427119261 473000931 524353961 127783632 697172423 604124705 5750180 835545815 98503893 977979838 712082157 968727698 688991910 962532282 753533011 597633278 351656969 405795207 944854532 189391795 516749271 51823995 142139142 54337377 61449202 233545230 451583525 326815889 975564699 958279709 22646345 255200311 283796992 547000305 382983942 980969414 3641362 241250474 669031580 102145254 219230311 233630089 923389303 908222220 48678722 676922313 358371849 400335690 82717519 155742733 442243836 451983141 207566727 584382977 358836870 269015928 817928207 810420394 448348169 646009257 621216455 470994513 901209567 905013446 17994818 284193508 738499211 874152531 525443981 407530790 976297784 597190643 641160878 752203438 357929215 689839599 281642103 716301063 942691640 216875973 872043795 384935475 668859114 79610522 821834804 27695983 201142801 492279362 690632728 649490969 138288618 311849182 120485482 39498184 69378979 990996651 176208043 807878189 717665533 554168376 67925331 546479668 151359018 709086208 298683105 509288232 251442159 580325207 78105647 46650150 797201180 802665793 431585625 318576645 734792666 105936780 346272627 935935467 598216141 36905354 437942787 736504758 201270888 410944620 628519293 270649866 254457622 657243687 78528055 972123154 211412062 146453385 371119173 215287432 708055944 669802278 724575663 812014454 102643836 655197661 858664604 752361367 457863454 142766580 70938011 45172471 248703359 269726989 981107937 846919499 159148695 271567076 435940608 360419582 535028047 64459900 483585799 789485669 574219938 414630205 614125174 785632000 413599941 985244347 919431 121655885 507562976 578011445 786186690 462723163 85725458 644851293 215084530 543588911 787617872 138538892 588761381 36321230 408265881 422385670 735757080 567414575 546469097 171697687 927834156 81497143 88673938 263936306 723499163 662893876 678566511 190140689 301042227 92166451 27901387 154478009 66338687 535464362 585005805 852525377 998187524 670731262 349893021 65788405 66836524 990027245 204327297 655597905 878864826 612593177 930499926 614621906 32524103 476969022 638835944 960358258 410982516 727509882 76810915 134481679 242920109 755377425 324622367 396478687 847543876 352523753 550956695 766398914 740504466 135962499 471440642 591208341 659210113 821333663 656996746 726046636 663877259 713840394 234160892 542742084 178949922 164660817 9880341 211474024 494146190 648716285 24348633 905128706 228742518 101159547 39610384 324178978 856536972 216749102 720657664 556597199 421789206 124130710 322996112 162293671 112609560 794436754 753502011 771819672 468286768 263015108 497866308 132164026 976855501 732027199 527422461 8321774 749204368 389819154 219795797 243350557 38535438 244144429 995614 119794307 345303976 40605997 443973284 201840947 109871450 17147299 758438145 531660655 141278008 933950608 546470677 253887567 580903713 152489040 25707239 49190480 415504147 376089898 33870857 244876000 108117096 413809670 253197773 709837815 803628823 472993570 953188372 694680612 717137998 954183985 666991270 62441973 847306334 110964553 116799271 809694135 128111851 727753767 193871142 121906210 661704375 740341818 375793776 95124439 892830857 401501014 144314919 160851356 777590911 30702127 405727355 738224359 297028148 511441479 300578525 953173322 984435048 106283248 500370285 554089398 60467233 167361554 469047722 760289918 130842458 438363345 422500404 111470660 166117111 616371545 233376869 680337837 356713363 609170645 775462276 102060571 863188010 772293546 262911926 493295273 655512024 668639280 84035983 952540172 32597111 384614507 758229845 17032158 490897755 258600130 423637907 403881339 278478035 745201981 16687608 409320493 183565325 439188011 373307504 202198787 55559556 606684373 882536624 264789270 68371369 657998899 366849840 931559378 282808796 629761766 277371002 938320819 150917397 361406984 743377342 183514507 746021491 501607187 53063017 236919245 612723668 476700923 640800583 891201702 74419255 657488190 153038546 257984579 96676200 526346050 460183366 4752107 133030422 195236341 269541376 53918142 853235239 636391216 837993871 136044034 118669333 115364873 926881204 269586729 476771856 670258546 453101236 75309698 24382084 506164252 312228942 637105751 982865174 805545876 380823804 57284429 315550417 533862350 167785359 264742969 60208399 480485076 269495075 45755172 675721416 391552803 99673313 381473006 27944018 790183535 370033391 146613350 905548407 296914595 268716430 234836615 819689492 721817665 310146312 844071575 227981916 474891606 333693677 63363442 280437481 714517480 973164222 595987898 100896181 140949580 860730866 161104579 473951008 982742292 59376102 149672423 374295094 11565766 531145429 254755463 801749301 901178819 253885164 559814059 50609765 522601594 794650673 870299256 96935610 957313337 566887182 324917526 432204942 753097210 240797319 565158774 320131042 213961540 13663023 421027222 207427471 874393888 582131801 681378478 709652532 641507902 683567253 83947625 653073668 67229033 191219440 307339320 968407851 297620955 867153378 871533968 820222548 514320403 594349575 917158158 471633739 13753109 94592035 756355032 766850318 335389353 321513805 86981359 401867244 335176828 508008581 609294714 62087067 942656733 143189544 771739598 436680986 826756796 708203575 89754653 893985828 751939366 249610324 714910030 49560320 116763702 438960349 722299220 631084104 33309924 491973729 955234194 47063032 586565763 711589225 813913349 774471467 885619381 753411060 176338710 73312560 113935992 638149775 135399627 56592724 781339318 759655576 493273709 460612465 320375502 435544714 207114644 72314867 685155037 774541026 121875187 654435090 213501374 696690758 138035545 99327649 188664486 93269738 146390680 627746600 657375314 812820381 402218066 542994695 566231440 431073127 616307254 680167431 69222901 604223232 589276506 703078571 363878808 82550214 16207387 684254309 370611279 223322031 609085528 908282668 997863056 583477066 562717757 63880781 280167823 700753302 163208430 321348660 646539391 162115461 949095259 303914705 974935841 203829676 699425751 393683632 634902802 168249356 73851062 704125702 772472588 515643919 259720624 136351395 450710485 275928011 673122055 821321763 499250041 134723934 582120782 349629448 718200999 144838539 266026580 998368821 698108192 429235009 172233832 197163934 591350470 121329090 501078638 418802662 325158765 53020740 812486294 960061566 221270096 738853707 516703620 993742683 254497626 776424243 982610429 705208110 52352253 508248835 379046224 404118645 642972769 961167006 606264444 361173767 958521896 872291024 212058940 509146439 154042384 384292771 706310372 745392853 358138213 59905362 16711867 683296977 112926101 829198160 495874895 334196196 568051866 865094866 180455230 675065843 494035460 163065658 232790304 398904065 671314493 611836528 803022709 166803613 425519885 261803505 527977379 236558132 134094528 592552670 598220922 288136911 976845441 157047645 886046116 187500005 216953006 902757982 870796981 182395459 731956141 219188227 516591654 152524358 84283092 697046884 827590201 430834904 712628893 60380504 829738968 236459737 524733383 485278028 403263349 802769619 747081532 931240728 39327750 881176059 376309749 490065023 21829322 205671541 647112668 907875437 393171545 864065673 663149770 116484878 46461131 247622262 335673104 415569137 400146619 272472548 965132372 80253171 703307451 677761264 993150027 385562770 914221001 370399761 870840797 170000701 173169380 617922329 101241428 65013481 351614739 330067529 555078504 225960412 535739069 54707523 133835848 928910614 918773195 649501969 45395491 817750678 897124230 233584946 85836166 149787201 506057493 50968537 230040371 61881295 581246152 75706749 447444064 347983504 446106510 170801213 517984205 619275889 788723541 471741984 536805721 992854631 801809512 91884224 218815043 190064933 146591746 205167242 118975546 917881293 854669211 16887388 588148322 604309792 250472333 526500839 754096992 756529826 429985727 984137363 670927472 11231878 59844111 118371536 211731734 358466972 141689100 582232290 977742860 930412640 53974273 367064933 775783622 708300137 311465508 994598664 898365069 310573606 52282258 869856966 80971250 759467820 886744353 669119571 363777611 137216685 48136761 117874603 746262862 478122487 954528317 417190334 341870716 866888779 388078221 553602449 77872103 529767320 135834738 55614962 312696311 42325363 275196246 88479932 603141851 586661754 935594948 354023271 897235359 840393557 76396588 978206608 599861376 963140940 499842530 816155338 100357624 547979290 786546292 699136838 26101776 593590960 116327171 367972491 312996091 356921743 774091292 390868193 739205414 762442381 298999506 51901724 657284095 574195752 992898007 112942297 160857505 781009306 466965567 58092863 473919214 543362154 888815822 73780589 359019445 388658351 742452279 311893421 936637640 528998570 11030258 815255767 122589530 979873780 35744609 288101972 189311874 809835900 678970164 928517287 572278281 977969669 832935362 82078727 552165420 678349720 195021024 565539276 311875378 661986590 476148490 785794591 57865096 364964311 712091532 416884540 606139013 454543810 728777960 395293004 836058731 592324569 210548770 811164612 572198348 246293379 99266583 761510221 56129278 778236746 542543859 480923910 608722767 375479220 563002637 13404538 53828940 758023660 578943814 218220669 272526601 55092303 4015259 182908048 272572966 716106790 599792588 878711978 23166951 181086899 274004982 859225682 773411468 337070103 522906645 198126167 583363481 622173228 812152740 492009111 252926325 354696598 825449372 861649091 582692170 240968360 875053629 489037461 998992019 306513794 707258129 124034972 361606096 711273387 306943019 634179061 279896529 759251958 365407391 155579831 940338857 639412372 14805512 566266676 976482474 390228509 616909194 412362307 12401736 429061933 756887769 117844412 636274883 582337140 832009855 218967052 823305500 559579835 708004512 674813870 866093628 267778992 651365193 80216075 979052378 958308212 714395136 111465258 570076521 79802526 267045089 362931729 571731249 134366952 929198404 400730074 524595460 398623950 665608732 389513547 827685882 422496500 359874311 316477116 857349992 191884165 535444167 533171843 751463999 95965030 60502064 470073978 363744021 711867257 550290052 195312751 522691820 117201539 159294360 92768340 49520416 426339448 455700069 621251664 413222752 237414824 874498090 937818211 636038773 540106821 179848110 316241007 815119673 539722420 632718122 672469664 584122936 20678641 58157858 188103286 116643670