17396
927298757 570018384 491315973 113887894 422889062 164435218 56243529 782044471 305126986 713122775 189811507 793627251 203850258 484264457 737452004 562747562 995447706 435990429 851506586 649536158 803988194 861848754 232382283 473784207 367768416 571578106 618037059 955995007 976591723 288077352 84760654 741918928 404746161 277901941 411704786 771444634 532019720 946286823 122243208 503387217 794721774 406171551 985484395 592624236 496776237 334283188 92926631 195026427 611606170 302586942 869515685 411368155 225270242 610761156 868782315 909486651 101597423 563347755 699289871 217449310 801127573 110403520 200300384 141040586 574710871 196568213 346479873 733152328 925789150 547072237 589174741 798458138 180486326 22794548 46911878 475889082 939104848 121817306 245698393 447023820 931700849 210180130 617442998 398673716 157518349 712564809 20411136 299042771 322034206 200037925 283077947 564867524 397620561 894723580 340067189 205267259 181783457 172457023 584287467 2581709 293260945 322161698 597642765 931622082 99522206 88407985 19449559 163550520 187336953 141466238 378930204 232310264 384937715 297421448 766211114 517505431 554430443 191150905 163536764 375828074 911961607 647909440 277149149 156328203 436405576 362547090 594825895 376757799 41577300 454130648 989172688 823644089 755744553 328000603 890758688 814124445 970687166 712525071 419983719 818007509 925891066 320639481 993494523 404164668 109499294 376217926 893186187 264529954 758282436 694955142 916738509 600853429 543925435 224769163 77163120 479927583 486154993 709175896 529838529 605106703 294201285 156811549 799419949 1589380 779606611 850887572 78825031 527622179 585836326 217020295 430176795 578845840 354168829 934229206 878850841 185164805 875975964 565412604 506181857 681099133 277945526 837546279 237434992 140462713 111452378 408182462 252182638 654593952 903874505 577517874 820882022 750099861 249498607 526886191 712368524 811604442 816906632 426717844 774718473 381451658 517103759 233145259 481391890 80618025 333612084 473686456 391086232 545833856 696029633 946835718 892270244 375287908 342345712 158599258 660921753 435575292 423549624 499230417 780607130 168482109 613119298 22413214 156161322 111608998 60787255 820197225 670672759 415318476 462171882 937258587 187775151 460335237 87912465 546451536 615597026 510589390 760697356 724120078 449543617 236149915 466710590 27722795 940937780 531308643 665485859 972010508 766523536 207500696 298534026 975408106 345694433 870992657 256577203 175990515 461486728 775295776 491492040 31712652 650563051 243917001 252556217 241621491 996143692 274276348 672630490 871590044 595277047 380874102 846817960 241519291 195870665 496245282 437850753 991074194 312256403 243963240 706513473 11726016 334516757 70093101 400262730 818861203 431590648 265432466 804893103 170060517 763459323 207087569 229069717 247541315 348290832 309864101 452937218 967334357 360929990 741224500 371314066 634616741 289928172 744424162 169144754 722919100 161258896 494303051 772397946 123840128 723554908 29977044 487194966 325987930 674513781 180090336 491021845 509489057 660207638 388230072 440990138 222162860 666916023 728759171 668753830 586838493 148993316 214485509 568964600 140472943 30564674 471593140 769106437 171717650 698684 544402107 647822895 847493970 995607740 426482172 903731931 105502232 757416004 262276897 843722451 714626533 441154533 54757027 565760585 874353168 531506167 117019464 772587769 272356545 290583780 441399162 736319200 21790528 392944853 426235871 398846293 598529692 481393906 359797775 357532848 60502446 262773102 854073215 402822431 743783046 854316853 200650189 603556557 456937666 535931122 497336873 665949319 695207339 18897764 715792063 782079404 853138322 134196139 998505393 80449870 304322404 469154758 869026209 544007812 691783676 523258075 636378529 305531235 479818493 12203626 358232060 701198464 204383328 566184285 363564186 813834234 611975619 784297923 798885446 727367750 991939847 844109762 125431381 79503491 871434968 11970817 558560020 172401700 55965124 519749718 701521406 656175575 304216240 358903960 340483581 211383485 280420448 732548196 488256987 961545850 899677379 899956964 804157321 772128845 245541219 562281220 115340824 202162262 509756872 669273487 430453420 187860052 968199896 361406199 654027796 540167402 297160833 117256461 759996988 772515023 136190073 291638146 729902597 802630892 521000731 267465717 605522287 756573965 101467497 28823926 447338013 514812045 55099019 444032681 902991949 885365093 360825237 184730777 41580814 155373696 1456798 835368972 234374684 265935442 641881780 581044322 89657480 282051617 903950604 501983305 167810583 303265482 544340922 621075373 403335509 678441370 147692895 18598069 342176152 948518848 491554457 723068043 318863070 412273194 687792060 585165172 630733391 799006152 418651591 662519840 389551357 802338360 220514101 189678542 901624313 231333324 579990246 420686168 542723294 854662732 942190873 35876497 280067082 666738026 305409656 296118730 500061392 126920067 608263392 108750493 23937789 801266 520709441 288678069 630010411 722386576 856198338 105564622 417080158 608156301 480817764 7319703 961722293 57591777 583717253 644305933 604125144 439209737 137550887 895242718 392622480 528230063 916429275 95906758 450774136 918420824 528746141 6824847 447892628 471580734 643003445 167624862 481826337 819051055 287278804 579657091 997618043 965377126 228757997 303321900 565553137 282159918 582632853 319656300 278077048 757181073 566254942 955120935 333765868 618902334 546183631 649450508 352324846 856196941 412355045 562502057 670037627 649698734 56063639 676128198 146606558 281228934 763492962 271023880 811931879 867801666 758585597 257204429 554170150 451175255 962792421 676472566 800742585 368725558 399447188 20872993 824539791 699114588 619838176 805079959 397293419 336730328 260236988 11356478 790614326 181803018 171496241 153328785 134028247 209094232 948154418 297337117 20148341 474912599 779231220 388066056 67483397 587136474 310800209 380991384 4524371 791501409 371688055 176729174 342808184 597258316 819571248 262322782 890376898 986243701 104068922 35479094 721062787 354269404 764085033 254113897 747964089 342519600 215503163 342191251 845845047 972896010 638418038 769684079 373570009 285217906 208892508 627870825 668721121 568243851 148543019 125469368 732601384 231685374 750872939 274352498 13004489 42937245 901687380 749917664 319062127 388752096 398317014 491001463 176702628 925572272 952022323 842269490 420527343 703702895 450240510 996327053 965296905 314558931 269271719 289777500 520457722 446062640 150454287 781820606 251886218 684220779 502815381 955233176 139054559 42855586 289731874 10497916 1476429 928998626 70512004 246861493 967279167 378843973 659135040 576674119 85420558 731902929 236167348 550524424 7757199 593748571 873702517 917943542 996955387 45690308 661830027 815129809 980399523 939183702 216041590 212267572 892893821 665984308 455785439 83578715 10872619 255239081 664465178 774551540 48731709 65176917 812328182 538065870 308477661 366551429 120985998 863240889 928637541 149068386 323189424 249443283 675198901 1113095 129615428 621008486 11120049 919778303 267512030 105099701 920028632 876313901 230455074 207802838 567586865 928817439 172941037 724765085 413734515 294444333 343252888 477725763 97263926 617753260 552008434 822365070 495745416 777631279 527519410 43411986 622743750 294399630 983263129 349893610 157838009 587704859 791473433 297903842 451458048 33328803 862663020 672675917 987224148 49927233 196199699 505375289 660087512 586117150 5856925 197798337 327785834 982042926 180372438 169530312 668792092 245977474 939203739 612310129 148737870 323812352 866357864 903118509 170495009 133484031 918151337 802422430 662632959 82006302 215796 749253229 174321604 319492025 939936632 548238381 891322369 704595089 590745476 9020173 502675534 495009706 636395609 825430258 227982373 816922251 374489231 656611525 827482149 389758694 835295453 458011649 93759825 308043452 325331357 890441232 855504303 806688205 87994874 896410960 24898660 644042298 580605066 468812651 656989500 274799397 573627943 293241614 167869049 504688227 389838254 47512806 84519661 116407410 821715375 720016180 216931921 669396666 72322170 608733536 208116768 832818748 922327089 216640442 714708410 166267769 133543874 909933484 768383300 879834755 582947725 632501743 257448589 512361454 729154307 273913799 504224541 911603378 808188401 474948951 944338267 466293455 131549454 794110745 90283385 738541037 481490193 201378371 619301017 737271346 21960151 41498860 528040805 113175669 318346086 33958835 740082289 742487818 152160351 406805397 571588535 223479840 203910192 834887453 55986415 474948036 76903334 676550721 408673014 108658434 51507839 751686891 6288542 687258978 663225090 723162965 14688084 324937593 159015656 242996982 619872242 2538390 940423771 962522579 796646474 780349620 260510042 454640566 426099299 739399086 83898251 786411123 928052238 878756991 469940237 250092312 282673519 670480634 87578 475468641 8680683 962211880 853973510 105068810 29581511 714231499 984475343 89261666 994026026 881133477 467837215 628731053 30305075 196471679 18274812 47290276 124043853 845260789 767402323 16966841 886781013 670379011 447348292 269564151 173546166 781555490 233356539 268263015 567494739 601642824 361670305 538207519 142726866 416082788 470044717 676613142 464351895 624089773 921328406 725167472 992324346 624824651 790557773 46013891 691242462 155729389 639604461 391606160 870304449 738627638 208507338 506791779 544915132 835340965 283323341 54922433 972547294 568461073 33785404 944703288 216101202 665090683 300458886 63613380 219126261 909475235 545720186 132631943 658830218 433567933 889888743 970393327 417562669 43932076 834506864 12870105 215644075 93472365 80143812 146755410 445187541 3871164 909868646 74248420 249843842 258749135 789722766 716494058 750764208 78454954 916125650 568390695 454628915 144697230 13530006 890499011 187207480 414366196 472296680 527595029 247540221 964840966 677855544 325088971 974564448 312815374 313076184 803374965 229554887 984708430 791982420 436851627 792553994 863758601 493698395 699564951 480654075 593984449 290677975 111721686 27276882 20516156 439650634 7210958 566645785 699816019 58494213 740009901 997638042 834726038 504074700 427834443 401994839 653426322 594311172 400505048 870427369 152236967 38462700 114559139 32586072 323732573 314665820 597880131 218103468 670500500 650728013 404500359 887636639 10082847 442490414 361657584 358712870 852343239 192945446 670825099 351051816 472725975 508507901 479743242 725286317 290777669 494122024 432305432 796740481 527967463 646116969 351656838 584513684 469530196 815077529 720879055 109459878 988273753 218801577 960307217 569743168 849269723 652791560 246232259 122863667 757554547 527054119 430167704 482008954 366964100 885927213 522981128 529191600 603167284 863467387 35508681 730388132 208460096 618618658 794757327 183144314 749770168 733327724 751988577 322814553 336564930 29812074 648731284 777927795 729790691 585837864 743368365 490101670 286336740 17128504 833682138 215626114 456915132 505279382 258903082 926518691 263974380 333968282 793189350 702027637 293179962 843362417 412207186 980950483 539958606 780378965 834254747 459454011 147095282 646899594 397794666 189618041 561446488 947464783 689334243 523838694 711499171 327213880 254790727 426725887 281538334 79939977 106267610 986369574 194742917 416592332 841340880 54588937 374164770 897119691 124432647 321331672 336383289 649494846 91195704 312137732 621269230 203889317 437969269 293940897 946589439 23696027 225443909 329095370 91301816 733518739 579002458 897774899 612010044 700753883 322913745 878343018 778810648 664297982 55177864 352141397 61894652 644804697 351089562 493090045 822320371 544116996 425603291 359827302 276658724 78341188 816770719 491533478 749198934 167191937 450618533 179763670 28028491 104749030 988905507 796572089 255617455 542957759 3126721 642423800 69733821 625745963 844779245 267176014 997739845 890148952 302420821 697592429 979015442 617994454 353503963 288913874 871497154 686524351 431805232 477021854 5084555 696239388 837240191 439970393 575980354 93602405 911441066 361031834 354117082 844774123 48504465 119249982 484135594 770520578 755800061 585780360 52849594 460120874 764601453 790778766 410728960 214448503 887883307 709203235 195093029 186678874 638373718 968202013 369812464 129392245 28105483 451887042 529161286 958980622 365497582 355106206 847039087 514191872 697018674 341010927 961926757 605331246 47441774 430147547 23822358 761810133 81639836 744601408 846116722 962131311 530406828 106333133 592560048 654627390 858636749 648204672 93891406 590703147 253087204 700497979 537548818 607133221 520959930 292028539 666121678 550873902 680720452 268194699 331714485 122232779 445403492 973991039 238708983 930906443 322073537 722171755 491859900 647569544 411391899 517288451 767466896 380978547 894476413 890946759 765686220 948830857 124209658 833178344 414756677 146038547 917332165 12155016 394552066 858225205 450971882 162960481 728916571 505191502 563715611 111662668 264748054 653805647 59494840 314526533 927430222 855488810 726531228 556697783 665548285 395477334 637325305 831866439 42909841 119175200 816507307 249119076 677696712 152314464 494876608 106421782 163370316 720869099 188177363 40429413 743801791 639649546 442411626 787738457 185691106 165505315 717645256 935685713 946542664 486919465 244626258 16671668 154631458 440732860 873266579 906621586 287209833 366701576 355334415 610152047 117735441 661115862 754831010 307779814 638176587 450705836 390077493 980505003 836792923 50195767 806907377 954658994 809858453 956379688 718750744 5589648 255626526 515209914 216641536 470575524 495820404 303654647 436697527 844140312 190666016 825010481 513905171 373985382 902954266 849324948 44928734 269667705 233005101 482722541 316782982 419385508 460876677 572859644 265247416 281606112 107615506 660316793 872406672 204301721 336693709 710719120 70740502 961864516 95699870 102685510 9404124 519911904 585605843 421695387 348536335 720147777 424985616 650080343 876401289 839010492 388819181 285157317 522198335 183320168 996082117 187172526 786579002 247762532 982298107 360844127 742780524 361382154 541908587 17013433 430984875 856542225 458192229 570365650 72359376 772905206 920497920 570593996 851027692 943037931 790465497 599368407 427513278 284175962 921688050 765261945 50214861 626602924 879890539 124271656 516897276 601220757 815351761 815895674 42078863 606848816 236316706 575873598 794667633 545337109 152098345 396739685 655817737 228653333 439712306 241740733 510803900 226031440 916628532 956499689 49743022 822090904 342678446 431630893 58798762 917324987 944340280 366837020 196404014 160231529 485776979 690948895 822446618 177478815 112288261 548016017 535531322 368203646 961700749 919789627 527427571 550321163 104336987 277293797 328138854 141141175 168930991 952346680 881629876 452842021 427001212 441539399 500248115 248149328 409006705 668816573 453637513 229300935 209157405 466303912 305374950 44458980 287639479 304803080 920651122 951426441 440341436 980907449 63667086 486697533 867351723 446640658 919055236 574938707 21004202 123967594 479404469 524850623 373899396 384187502 500757189 161000994 180458543 426800863 482737830 919672596 20198260 157628808 963257316 300318108 514920828 661652535 554957791 887617286 149765248 975844207 766055577 786623460 461515248 419002552 425076668 297266787 306609999 586610822 474183936 390321483 619152310 321082183 563871844 509117030 906927381 807279708 523067088 86260466 74118451 710042248 182751242 930535578 148111948 311468203 146427248 491684630 655450940 52409627 997540641 215921171 903479808 934866726 724507930 840733774 84464245 766355133 207051686 747131100 412227901 827148557 569816056 326140096 783637162 498654519 681270940 332370244 922224777 616396087 606324073 18728361 722090877 30911106 861262244 579973734 595672119 984707004 330157100 642854022 368936148 795323952 85044130 378411668 244394039 278551781 828104157 945290280 226118479 646140637 309593572 976126268 655355642 245439979 206440667 853435487 518628184 585014451 152628330 175174960 400045359 368461556 52280267 516317215 919026873 856119542 514497583 349641783 379412323 86860679 996998067 491359341 479433525 597002257 376432572 911856567 59129468 636639371 792877088 352198459 955571675 844415611 568723120 213531388 683615167 581060714 30221986 435697314 554437051 467313816 750082679 662742941 743251068 748304899 362725589 680653153 909057949 439768348 44482463 122391026 898794777 767884726 383431099 517369128 172632989 513027425 925147483 15473036 354179581 837419390 74183663 608031478 387303209 258651705 452275866 728345904 136313329 846108912 553413287 109199156 185157750 613296488 236112730 537996456 803499656 240288408 438210502 402714940 395335593 964263980 981411747 747660330 927830613 636027433 857467183 210761724 69813986 523776524 803576466 500258437 76708948 347426989 362314047 752102018 343332590 448194426 170728602 846249944 991321035 93508634 336249923 498314341 868470352 539133341 59603553 411481441 623816411 325940487 121081878 863808454 902786141 902849064 310804130 862342881 491468033 712665827 970753517 802290922 646639986 317549523 225607571 177828787 497219258 798844603 180143063 211213402 654818707 366186643 749762867 402484400 825875446 579284894 565498870 257920028 228050156 878108461 163790197 650942527 532481295 517180738 280833678 959902151 18977663 518768822 801228226 983804952 208096444 207054936 334810039 874908921 776848294 600217563 399676471 298977828 279860074 504576956 36313175 310541949 906149641 895008026 208328197 545149581 605668417 619563572 26792368 759507201 631403272 127194293 646926792 921836405 972574078 787055274 983369076 502864035 99035807 869127341 634331958 699031535 964194690 361286745 220653290 167239670 129281336 310097345 47988349 360844767 953890217 365559044 575251587 812703940 569694039 173721916 564787657 708118118 7524386 699508721 310676515 958123775 115867559 349863152 113105262 779996887 167008198 40319860 951207334 215153129 126689464 401954189 744974302 85069811 405768016 548501781 649426786 932882223 415258271 879602015 620389845 418593566 373943874 879553325 386094634 379972687 936206445 689831911 222646216 310544660 797510415 114871913 67334579 692625477 7334625 35899826 858251606 234650301 708784511 369702479 555709506 403953557 473384149 121070451 73354277 34495070 408792969 217262063 319938410 695181677 219542534 886057270 885374912 988485839 331316090 3568743 410040232 974039886 711068938 555236482 578674666 671502497 665695427 793248991 450614125 286984484 846496928 997071821 536260909 109224195 419591552 137845854 84716581 957262908 55606979 435930550 593130812 963899181 213623175 74979240 515331097 859996896 678629992 250029680 326503706 892647122 405026457 768970435 969753854 910660811 164920838 757715214 887897464 752873938 966560052 363655939 684091891 863486591 665570385 531551852 708765051 463946921 133239742 124600051 894881593 505440362 719977369 681250129 187384310 763210454 737605133 472235047 749154210 831133974 122724846 499882400 613590705 364765866 566205112 137237043 77919896 332951587 666745777 917804684 507919864 991360255 226611870 787435509 869432928 29942757 854349605 140622267 373041445 533168480 40575557 569279466 575033909 607166738 50809597 883356858 53831978 587770171 674154486 429192226 149620810 83971232 896000024 212256079 651822636 910762974 72888945 525891114 399611120 714895231 142584591 95823119 792368533 662121076 191059038 457976653 263054145 284550270 550623511 30780565 435086431 335536171 155206472 938633786 424631738 320136818 442871040 498292786 974937441 419228133 481441548 865801201 482159199 448099256 718985882 734118666 709432854 384279559 678678735 340028073 806102045 158962519 721763072 902275363 871501677 809966173 408316142 599048069 525161864 964176540 191452938 364989439 812600476 70070989 895874807 124603780 319561995 694359939 539136953 658249960 485705841 568373843 568810694 482372211 951206348 396077302 991622109 62580729 756636116 999191878 646943731 309168158 507535267 132362891 147970871 51153585 753948468 935939903 191460122 280461806 211089028 327688959 567262210 821243269 293600991 553367585 703801346 825338756 363574911 421420356 476619200 589754342 111070038 185531403 433871761 309777531 645953284 604168291 729481454 807749793 758355114 383919664 88501777 188844629 926435830 23745781 67399888 584089443 83710053 59162640 418919812 56770568 40080895 574028765 734667089 963753531 920712662 194650755 691360300 699682979 456362945 301962388 125877886 946287379 821518726 55360026 947295953 130034593 713774006 458121692 211083081 23555754 101508680 446409999 190241801 544096493 545193547 813620446 942386404 929364208 234595996 762958847 668857922 528374698 701606424 645348463 523090341 149464979 123057117 800911403 19926912 958986667 192998861 486230059 530169037 125209370 100659917 984065924 576425261 546217576 750934162 981928955 885034950 354046866 28551215 831569163 383683825 690934794 606139653 648834472 959430910 152911979 797523739 538071459 793974890 568906417 320345721 389470668 81742441 668257959 264456973 417054404 196201580 531883176 580543051 397775290 808156304 725270147 800656305 171956283 494327598 585231171 630339583 692642204 301504952 428466473 152528696 495407041 208814459 959302433 980320011 828078437 212516492 788341229 570443893 582549762 339588127 664933735 700230980 77222408 92914083 173996946 551205843 592534245 931448192 229376503 639981040 19805109 485261989 286239309 276785862 210707267 891621548 449235381 392141378 615663334 103810003 76112138 224069391 815172793 763831993 439170940 76980944 287986966 489431357 339021291 370569336 543933458 160157860 110301296 790074163 884254333 501926596 769335420 996942917 266692038 789437978 996008073 538295209 992927763 461849833 771470003 836531959 123574015 912682578 442702558 277327088 886443214 962516258 318726929 576380645 770863024 84342605 586087453 317345893 898648628 424636402 467620639 960208659 10301530 305239237 244860790 24416044 249120415 530479896 822308127 399456545 955206201 323500511 888917106 167013546 984087248 26096517 741259289 663242725 933316557 168750624 713148580 630364313 34882122 653346743 791528565 575675147 532461488 54034919 956124211 179350522 57697794 70776898 947471751 169965365 327125961 57751119 10667488 943884743 440792026 720142732 139086468 756615340 699295971 57094405 364763124 956997755 688539614 537238805 219701543 712956865 899472520 397430725 710210747 315536916 580275981 72501614 49896041 355917117 527776356 324099129 909009383 962746255 865468573 174098684 73511410 403061822 334720332 970380627 992138800 68420824 444544381 161266284 160968752 189704159 42320120 559155409 807594052 246426390 914587736 336223156 95758086 569293701 596167611 48204442 796098487 805321942 730143334 413666784 909539792 66561609 423656800 264385088 320736170 949785089 715888238 281421390 78389848 324029443 687917283 258486461 141645162 648715726 56188296 393739424 643851941 446603945 754973821 78105846 463407409 377279212 719816436 740959938 945972197 108663016 159060864 717901224 602826201 598824916 585130954 968963016 41119500 655814963 863889298 323049315 662391430 934307406 609641494 37623892 267488537 36930378 463367425 318447536 234322120 732762370 148412966 591099445 893813407 129466504 517955637 148535215 625845375 566494885 347749446 515886450 150043454 502829342 736020524 330747766 234933463 77786196 445251535 623301209 494899221 999317131 219004319 962531549 56236891 59605244 946375202 518233986 729460454 946231261 818634460 191668283 497118264 362697228 20807052 86436886 972262465 78588950 562208454 250147976 980669821 910224973 280073118 613982582 244172300 159123192 154610836 815748474 925350471 40936685 653357868 810349205 763699373 670638574 467671639 944836268 914748358 65460415 764718380 1029822 617330291 531615799 104578247 430184316 537450862 321146315 518536209 574900100 76985491 650948050 936613344 349770233 192294139 736502560 787798142 626845409 603294711 850407038 934387811 729295970 226439276 725390870 126664218 536662585 201849034 25042653 528341759 691362176 960476439 863629496 611928417 37048852 108656327 983433586 702893040 930786968 128258455 870310116 889172591 626176985 617126087 149750831 233021361 552699381 782690368 94704581 971093646 329694257 301781420 576438070 550192647 692777589 439327868 232652829 10872248 445121879 639585213 707219602 612875716 801284922 112030505 853632793 45978353 684492390 950845368 449007811 767949814 561877525 242304294 437568954 30843421 17058282 661357748 650300548 583178460 562622403 287550515 166014225 700375197 958255236 560690186 544251157 140082314 578901142 874585419 258841664 113723143 952277359 511632090 19104363 508382449 243224037 657260419 924735487 616618478 941752507 607300538 84845545 120171502 794023827 717708671 750345201 115545618 444451890 708276921 527577693 245660647 307114498 147779181 635428894 533060385 985527344 316422096 827129642 642250179 662479172 660638800 754521414 902317393 99657611 673050372 223554543 517949881 619589438 14290459 52074605 322615966 787306828 997713574 770148860 89697046 761560882 42812938 186914428 151296154 955926446 620890879 692681058 665132916 10149633 917879427 940800135 745293279 88091608 285627277 180187497 879868941 595225208 378610872 903900491 566461270 768922752 877715917 187463768 848198047 769276626 962508052 706987775 701806556 191173693 481551525 957185830 866193353 612943172 321888912 761545679 115015008 392904366 775141056 956078474 313410106 993405679 976796881 451625157 846593172 9316416 639590214 273488102 121298933 713256772 242243790 251828462 154957756 11287385 939493049 896829371 456591663 494412202 361496526 272517058 93768702 996037417 126695285 101789423 744602297 304568409 483878635 691518355 319318430 250095996 501932500 516012906 435494652 419900206 306834628 932526871 658067264 772310912 632592892 289135711 173747678 847232509 761938495 314417748 124025290 563689920 837941411 770812052 827018225 538751446 595922622 53888375 280822731 184665777 119656779 904733718 70918822 272759842 639454653 580931538 63631235 495800150 513329954 471215701 210049123 865919479 748947816 270824612 679638667 273834963 511846898 559608093 409231878 798814701 935368127 575767267 640152111 571505213 400310842 60222499 221197574 42911784 258457407 423546572 60142345 931814144 334677392 783178926 828535800 669539668 430663812 268788935 228466753 559739543 971563464 126926299 369615012 63672738 407090886 377469405 353656178 51802515 504461874 794048429 768295724 970631520 308604459 608778082 515722575 957108028 219506479 124506631 347161869 714621518 592498829 867198588 627121113 419631209 368570932 764505475 11052549 866590291 597111331 519261961 435347984 161840511 2887045 320338032 467928719 686773828 968042542 684327311 731451369 730933172 392352890 898201838 401974039 730718675 959033458 720729465 498607017 677868142 674781678 719069301 589157522 79556024 308437490 720196595 778790799 538218030 63993944 446567968 36390079 391661642 515561059 857550208 517427559 848544837 90816278 598367104 705512004 89494372 160161631 349136064 499887468 424722220 148876764 919906859 532886032 740470003 910501794 981902286 480428947 187490774 209930794 560024851 812181125 310396284 726393082 435494939 259346110 478164126 554152597 317569826 477887927 660983183 923093655 943521523 899111817 215192423 820125557 978985709 813981282 571275385 569135091 80023659 575165145 48825068 797362570 332866030 30774628 910162779 144529732 609727781 436645087 881715479 769356067 949585773 748505213 86592542 665928270 486666601 759446815 188824724 469116265 205185294 573978790 13351749 98362252 272330762 109765815 789467615 691889355 223915426 83307990 865029134 703797949 711841491 85138192 716806786 335543115 41671979 79130655 864732619 109656345 599274814 925780422 580548026 280187076 340287917 71158901 344677316 975068069 665154959 284548585 185726430 802725480 621615484 598427379 670985218 431281808 531125379 207847606 339311882 372806939 276954210 436227388 230776313 482806555 174277453 281120527 366972968 71578441 383787437 207708836 912032088 612559572 601775021 383821808 613478745 75917899 576390723 403294475 672592376 655886428 411845616 616912967 674856732 223361266 785176416 970271364 637472427 748314739 507209548 878336991 922581491 883800703 451535845 207275374 3739863 556257929 967911877 936299807 653644307 557803920 534812001 75440474 863389115 690670110 458959406 458393320 879632310 41995869 423220930 715900679 460018093 856679029 978178903 811403716 737254074 487773681 27658907 582147751 548801191 903722236 323744770 869552288 401416802 407999054 541118563 399752686 129784165 339944616 196110606 28883276 323915265 406876016 68238052 81548219 902290386 504744702 68681029 731102081 178257820 852995546 179617816 603387940 560454064 727805336 515891044 621814482 2741196 503132788 857021078 910325414 709544882 306550206 279778891 110308379 709164457 362879566 44446619 226196308 610497431 620315145 434765978 781751488 75845781 880840890 576228294 903338711 487132744 635602188 393179969 147633158 287530707 650920950 731724220 387387309 728442526 636487284 820465419 499194337 537640297 379090441 548037396 423079040 251515909 664551151 799985782 201095211 536208775 872718125 931842967 128356534 326223230 532238383 565690823 522590991 556207146 869646309 359261961 610578800 737395821 566821145 62280355 937933162 901820685 940244807 726813150 749050848 612416618 265231833 360703547 524734178 210423451 355368872 666062025 816114834 645074753 938662160 118313553 307129286 75222416 350294705 824003810 703427403 486457865 88608366 259052017 461470054 260787063 923681473 692994042 222558236 662828963 990197966 59119241 752887606 419566996 193123736 123272476 609924985 703311714 984543579 353355407 215895953 366841304 58443865 613153674 630445277 241771797 584617421 962038253 763224404 349148982 16414431 732818269 153262739 400852030 752476334 251401066 817941352 928392399 568638394 142891926 783068619 3098208 24714320 5290948 879227966 106056570 514553855 117852174 390301330 288810473 519422509 809195995 548717365 246014163 922399130 114453927 505293500 492944163 765686048 710819628 803691680 148731169 140806890 804238282 279971713 528896966 656193414 449287667 807171286 463727901 411435866 208551675 578549959 586949907 952650464 468289981 519213873 639007056 794299154 710288226 177460448 404226823 81848956 624559997 538833235 289714679 126594329 905786631 649354571 535149090 895381733 585788690 50244877 506198419 466847544 873220032 721976236 181207790 624711063 699904250 9931568 941540074 415068556 715709951 883387443 945370191 776119310 477285416 445928764 833422083 132003958 901664626 978819450 719991480 605402253 96791629 396729295 795843609 102748742 690822821 891801757 840356696 865979874 593057636 51346513 870272909 363510704 371791502 545648958 584100370 981669402 651506974 745069238 615852110 115478133 116329968 247794321 527817307 520622966 530916785 507481355 528886600 61599518 419987742 770103926 983124930 787573112 245996617 890782892 845707358 383916922 893606306 99216808 563408980 133130385 805651537 709782081 996697845 153987597 93009699 357883129 365128772 497017465 309678768 230489661 71164649 653452423 574753227 524764741 99840534 545519731 280345201 91513712 276900468 760563657 714083203 487276845 639264491 832080553 154709340 291881605 919472698 348026289 361110789 923543301 544446471 168537532 608060154 322780766 809356775 993109096 541621158 744015349 75400702 560001107 884443432 982136251 819258376 176155357 879927677 360549840 104193340 337310336 138018580 432604915 911967199 65832663 837750889 351277762 98719239 299692825 281327427 233659361 163939462 822469256 865058408 891798396 595579285 106634296 977748313 535353906 431258242 457037387 592676529 849267833 764076248 697488584 112037038 723177497 598470799 81769731 474672302 439903280 332262203 845859087 472581569 399447766 46285641 162442361 992004430 777163820 878545373 615129370 664160174 336637191 313534062 293445839 544467357 618990052 269413721 258906658 182944384 329135221 611531164 603162566 792199779 763714337 334837723 58469312 569570639 154113086 305480 551552778 639882626 154646817 266812713 241663734 585111634 594923556 521320399 247692715 318944800 64737755 790243797 802020112 832950056 789151846 353557057 359709094 939158876 872137267 336024576 268840465 520539040 126116490 135235268 940120481 364090866 586618656 137090824 947348622 486404756 256021056 526894926 25779922 544245603 371365050 900214629 171004616 945511802 887701609 547715971 17644660 810803600 928931318 48120073 454016971 773750642 765184088 320539888 396832001 534597342 845348862 571255815 755421490 397954633 740148336 836777365 627696201 588062154 750635626 184322286 464415451 218710689 316398013 893673895 316752436 431506755 863181008 648492532 42162612 396302494 417410176 629878761 866465414 864136138 895301309 861959259 815388836 151521026 622544235 307798968 936048274 824411745 411958467 399720854 394880401 783017297 247307727 69684504 738119702 232419919 922838548 119837916 542703915 587791929 91199115 712025241 401062690 452187464 719865400 722163706 825056036 921131280 791740998 508825693 1219053 874947578 520395993 547312759 740553087 226566489 967610210 353700225 412765379 447899933 489120203 966327741 905939769 652437749 142328596 624889740 380492960 955724152 723951615 429373101 844658057 397682096 587779768 645339048 20827490 680912739 405081268 761028091 53429832 761341059 635671147 261270630 60315413 249515861 111215232 670484375 811685400 994791616 519286392 424556414 406656137 897251428 606076950 960675638 296388528 254435755 52988537 35045093 869906859 752364635 988908172 695787136 23276808 669775812 978437712 56694398 745007544 743381272 653284020 669756503 330204263 781169745 259479794 808651126 706342767 745630278 185912485 117041843 97615790 819209054 60555993 39083575 623822243 926683200 866598911 640728663 1738198 454356468 852386955 60961700 360019343 353549707 739899614 158477548 319348604 424386222 511104023 656861637 668942377 553477373 51908065 755680765 68929243 841956770 759607722 839731298 647316722 167887666 852512909 139178851 812786241 318547961 326265771 785187594 290451138 357925924 303397013 689891570 518751746 444805685 38627745 547185275 781431649 338992487 365983858 907798244 164901399 139372644 105247264 19050611 359456696 734707709 355355512 953863352 564568141 401933659 365088020 345179619 836436730 439360721 555009190 469159842 14654757 124499973 711123610 588093820 952583401 530555131 296319726 644778012 780200382 302196633 177170491 10276222 771985413 156312227 939340184 720466494 550032835 224403846 971410228 868849682 490394201 194499279 227095705 165429598 51468870 282520379 395171442 589689545 796082918 213606248 108875508 173736486 981822713 499248094 647400907 101241175 152720326 686903384 563028191 956916609 774581183 813537849 715989436 468512224 267189105 18127385 535217922 75756233 57772010 540260891 294584751 505304181 447358423 517457589 981801240 845675431 440464611 555786984 549484178 573488604 272759880 362037670 469866687 707099797 86985139 90299749 543254695 585309575 143804575 180181262 861772814 152514085 352060209 574223477 689252544 856861692 41681689 612476658 552780662 1035492 142018871 844232503 724663494 470712034 159850880 537950078 694521840 157151013 520902004 315461704 753797239 331030629 844615911 891571727 553396068 751789765 277767615 473208078 152097663 79164631 46370173 297910815 24872119 138030444 960606619 819830127 396307545 619965079 33841528 632929857 136730302 765678595 659832689 283518993 895292170 601361022 438927888 551043325 680154048 648295226 727470988 299842795 17937989 913822786 690816599 426326135 643436769 875345447 422041269 521736186 172713828 712190976 242284771 99822315 30214311 86446912 387196549 147911927 646266162 498931046 579807793 40466558 321126343 427396362 207685537 184241909 576759591 930975678 349036294 457562805 287495753 487326860 136115013 206761241 946285692 315856332 697717394 428443720 558589616 300757230 475386904 637078917 837848107 700669435 626798107 101456406 550607484 966364543 47065214 828420334 816423701 288052615 86429204 587969904 406123616 910310032 497525873 597412301 66838400 341470938 24234947 160291199 626895446 683347010 609952230 146765763 607528027 348775545 111507125 838044439 256629959 963207764 219202713 954516691 269964627 695874587 712495677 905165184 102193201 548302552 274533513 340155385 513254537 694197012 661630699 353480882 990042289 604359599 590143260 337359380 246088712 768577396 490690688 999867595 366911852 594649730 105483495 860037467 204062893 397468071 508701946 177785844 506609834 452272303 306948485 687774490 738367738 966579327 572766616 614696217 95860608 541135797 600145811 592619742 842801061 653937262 40294086 523865002 161498250 445144624 591503898 8943207 583733574 29248103 260670816 673101219 856120786 632506829 909951362 733481855 331890634 727270302 123785805 549565964 108750734 527906467 9084524 974622877 634475596 746658486 345085675 473890785 769612826 119428758 779605540 994847128 321671305 236691430 875375565 25047422 736223575 438705390 956328329 64753428 815275575 995119864 262564045 957510235 478959737 272585191 737053786 289207229 600161645 515636065 278102638 774292660 246699277 946847358 347318167 379582397 912754249 131176751 358027923 928286921 490513540 245399698 693343857 677564611 711477240 324916927 127463242 938402090 898754850 128603023 367691458 747171408 269286663 676063336 894273872 174411858 764227367 23248956 131394095 697239000 409167575 625956968 396738144 740785890 893645540 224667196 663520208 203500037 360686668 153162259 21116503 397359723 523029323 93844229 458065267 559929098 304833884 267288463 647703140 167213358 946695751 162494231 418934586 206444512 760553534 219679322 625242015 212115456 296078846 781386038 63870382 732416271 807352561 23015411 77314369 680889398 154226878 118824335 373590440 349716396 339334159 875848827 959066638 751639456 532153263 953090004 758404296 637183741 304480956 766662783 453897946 955057508 89100023 682208704 243712688 346760346 88664690 954804730 391751458 711118841 230176394 664409397 525146623 267483548 502475994 752323253 854233539 398983536 288005646 777075191 257477507 828463879 118524770 47145038 999592745 373020890 781065160 660697676 938213351 702148274 943389456 201549356 108955443 895532409 678494218 331314622 725153734 141614544 385981748 429848954 743343518 369929859 690969206 158129265 564419820 422657583 905810334 298719884 881839184 583186925 424283474 383926613 928991820 49633477 898926043 856024150 751372403 904849259 104683707 882934953 139454408 242985222 85005989 32162984 595728581 844963530 124346263 417295496 222222193 405232643 691756504 205556083 633070756 322643460 476258176 823482273 115497899 335541170 558235496 502652471 624040746 418952121 313533972 547690996 155670451 673245024 662887864 641102036 213482211 206332750 322564385 351642065 504892482 554957699 862706618 271768130 263412921 212037288 626479709 58247043 661961284 531010420 358959985 212347680 768695217 323310048 214520224 309632639 816768018 934999412 264265728 838589836 92140304 41001057 129573239 631158785 254577953 914364480 867387956 5493434 302813299 966235458 79048410 601258104 81474828 66201483 245178163 884691238 367912458 182294789 629422028 750268916 94586704 865357587 815350683 507519785 383281859 866816766 634047030 938163223 662360887 153129627 466714298 317895894 395684441 911594711 442262909 277351096 468713640 772409741 340962164 474799764 476307523 147813169 663576272 979462474 914903026 325207124 190885743 491647797 242419678 101014223 290826615 612875247 607108981 267647291 658098379 444853132 104624027 759391532 961855009 460375114 182000634 24273188 630694826 87795145 350579899 17546847 562352611 594180697 43945508 355585751 366545609 147671409 207935584 38907843 591134236 563903174 813180190 983016675 165027470 359681068 247180213 540024640 848724425 938982674 562726748 765167720 750881422 641510463 152770101 549877556 14371716 859882973 386023890 270482688 367166151 265486932 87382170 867980155 309759042 348472598 292728357 487350471 870212210 730857357 206849720 608525176 989643685 586683982 315368791 455915574 575947498 273011188 141184062 260695724 369295968 347042272 938770994 62904937 635271178 451161108 607790445 345705085 385492422 916824296 897803347 249590106 522293053 730193243 220833519 884019577 75567958 172290076 679093644 430216771 103967385 335807850 545603374 85497943 194207122 774607473 451406603 951868443 164218063 261321667 266045028 64921096 819113450 677823489 491577183 820833847 638311189 538290014 835624277 402919976 213990998 756120348 385231557 248768993 612880200 293289227 806392479 701673723 935569446 597644969 361744648 244500409 87710854 543800761 416228667 906428866 806825860 697527958 777534742 812959743 441493949 368210608 881502796 56304062 584299192 895233025 967083755 782158150 273608679 388068526 592011473 870115897 475520615 166666317 266649633 760541723 684200713 156968476 744115239 847919280 258178627 566165305 765130500 805407139 820181443 536286160 24068085 608206370 17482920 224861967 799227282 823066771 668569246 685249953 720578643 542692766 287219371 794397077 846547861 277139597 812310308 509651698 637296818 671472718 532660345 285837931 403567567 503171019 989760949 799144041 711131377 226603771 372536611 917872475 895523077 704746089 778093244 240482751 34646536 250437021 908574664 97332420 460708519 905639941 343206503 208759739 466970551 837569216 116875104 998456547 7536894 2357499 651734967 990518414 170449531 867734203 227881746 482047392 414527710 61136868 705431593 144749549 991781237 498392736 418796567 591736290 218072091 195758877 606625107 628783935 651293539 722601345 794420921 458483093 79485063 156638900 573130052 301341238 33068025 925849024 490047058 371903695 430666068 935549901 602925677 102820780 351640194 278511805 201571234 552653130 446263266 437432363 364998796 520112794 919071204 463575978 406646955 316751725 87642888 231539921 908185131 26861307 41596505 185305812 82975641 615519720 286591016 320531268 427908382 11299312 684410516 278466040 198134210 451429323 937794302 245315932 915099843 442714891 34301119 772540088 477194777 808870260 426455842 601502328 944574642 292991278 813221576 998002649 891475679 932085246 318358952 205934112 110596554 136155114 742631878 72456048 670060385 699641467 625062548 148999454 42083007 144708720 280048802 28012076 625089657 270567727 753663971 495499924 61513718 361640232 332210291 792686081 757368928 357149532 576778915 94556125 133955396 986603648 484173670 580943016 732448744 358197053 42391297 67056846 76256327 143845904 806603627 62940634 759626687 523119956 119146921 342087628 771009161 686975571 629324455 989009702 524605005 724244559 401623811 146361824 661234871 240454377 92266366 208949375 600219555 26468113 199273077 555791760 304234167 243620926 294485498 255930779 226174535 864499207 120440280 372813546 423769049 92512130 445386083 936659984 296859431 282883470 372755582 238649439 188993660 201523744 771259854 875114081 541646627 407292294 704065137 48595124 575531523 968404746 387205555 751436078 346434680 536728398 192876843 42268320 753028958 513212419 289286266 821139913 542445119 215145051 136491061 282097186 512586445 91116878 69829098 411005507 902778489 52032296 718652596 526844263 729511489 43770130 299196000 523503347 530385933 478609896 766836311 550605023 714521870 16160784 519728414 153582929 247589408 415979482 379829032 55103062 210514680 379501138 365559839 816161488 370567454 620071146 317142067 185733788 972638918 524400831 539548359 536012534 918905411 951849927 236132075 884740157 335320567 706813610 489922150 131284599 930173206 190894842 111829338 383737254 398113832 402225022 371258671 854678407 520447681 611070770 300271800 332695853 678850463 261101418 28360554 450145189 207403603 10296603 945193759 611868715 760472436 908241837 704508137 412943172 828109230 148435246 647234965 188024975 881611996 732925014 684868182 22925033 663783137 649875993 908244610 395833369 882251901 970807086 417742818 796756899 379047878 557840196 320932670 391166939 718401056 371365211 842325132 239586871 144271295 356638532 842494581 278679967 4003657 539775325 530676240 701255264 536786163 245130698 226551673 588601808 348838061 861076986 335210374 215386260 609463335 682047057 252893737 610935727 321420689 237965648 781111476 573292209 346650612 88530972 916552233 347940184 945218407 249965223 63871757 162607916 501693787 160545869 962718203 688114343 644138909 625036413 835937625 515107442 210728101 276878132 474523242 798796724 285208199 830173804 232897787 129670734 410377313 602875491 491168007 926204066 350587267 822521143 771638747 250788663 710359674 577296120 769334506 857548973 194870011 583310998 323628492 37903599 94007038 405451156 457014413 309474669 866925840 796188202 469948879 12506857 725894449 170192061 821633688 193854976 524428274 627234626 383108544 137617584 676077451 564324206 829263052 726282655 70121520 703155410 179235819 524499988 749452104 36113699 2338408 450536505 480349574 907172238 464569710 460393830 50133700 989083658 174989409 484586214 945425790 931228670 697922895 804492640 575396322 569697899 443454304 690105709 503719703 939878788 201076227 587268487 577800628 85010213 569876852 688812149 608025578 409844935 153833220 655721166 766045957 750013420 829146431 26835732 246950393 255825058 537581899 823467781 536584240 424049259 659356782 992040222 629333606 372948103 417113566 190786513 628255972 677548037 413596036 971107847 77206087 209818534 406031529 317614495 438255697 767106655 477179204 74823609 862143174 774953876 599467686 78096511 20290829 179479775 993036569 900359002 369386117 992400692 888440053 129040196 31696081 211755217 151905248 827237684 37032968 294824518 232183787 965304263 322605305 169512656 218588777 462511279 580738328 943312701 491807577 25170354 156549867 356453925 311347560 335173416 258449356 921313398 177195595 500252698 305886797 441831458 549388006 594252524 940768751 507897096 869039942 883799128 734292941 905722729 937600170 572921693 260658202 895190276 795462999 881748965 334411963 408267803 402713971 759643655 423442073 636937960 10828208 442090931 550688558 118931692 203203295 978573856 989505110 18176151 123231186 99139426 683637791 665374332 653442491 458096146 392478520 46362110 325653783 245562766 789538408 245022259 404095400 342975598 751503302 721736460 774374397 652735345 611361827 637661696 184674087 22235961 980864019 87796055 674082966 8314827 199321020 898711143 535179692 56058154 226774299 818632946 909201945 398960947 659122913 891628973 480541078 33843199 985053889 993014297 591786413 563230337 174360816 292087963 759101281 234575452 481976045 652755448 301707242 313754652 766414181 851731 67728548 539285308 157844576 535131904 761782079 330609209 238908472 201981032 474753475 672185466 928103898 549099786 597001876 565021560 491993639 663056838 475644495 335588087 935432312 575454372 441191450 988905352 620216187 959853262 938061320 60938592 838493548 93026014 343250288 292447550 517743590 307927620 995266929 898045347 81098309 491544052 285756752 748630388 307587773 594354578 550492442 234370290 79327804 350761155 807848681 186675509 299734546 827917465 418287971 101625768 408784538 638394236 696331118 705673097 384469545 622853447 155386927 673739024 349814760 352999983 975343851 967750628 602382623 90933367 790591715 462886262 455612126 404285131 877790347 674116951 895719106 985206012 301474526 527463285 880179353 548828392 296851819 168694206 172180231 867887745 546112400 458034286 80017506 96293435 81272172 387266745 972811394 763302853 700398504 405286271 850723253 944483061 66575091 660848285 153678636 801929714 988965356 986889207 736862369 76192157 220909341 954391360 346623064 342501566 655532426 406722988 256636739 627718661 928586437 751964444 445481272 909234868 395427150 875810566 231371330 274161306 121636806 438305045 72773870 750635903 40802323 480668775 55663423 746773717 55362796 206453365 467251661 680285124 877206131 919869531 443657822 45337694 958084331 122715965 176240811 778340915 183504989 337077041 386964077 495691447 995621077 765522361 579379781 596690988 503607687 735473746 103453448 103983493 193453290 348403190 396001548 270605936 577769667 956341570 590745166 779989151 834867433 117590315 136513645 778440117 973697047 931976308 73976930 938358969 511509470 723912519 892569853 282339580 418629196 178775786 727902738 239264697 581036506 631012449 203764834 664258565 204421601 24732968 167677327 458853980 54276426 802476408 367795267 318885387 549658678 189223680 718389223 410414354 487885232 621875254 820562724 572214266 554614030 932646957 233413245 537604564 880018333 525691217 304224197 648427991 743579986 104630196 344629509 170432945 736983733 212101845 722864365 56865313 295563549 160526571 921127412 122954670 409703633 594760566 781825309 305481859 241658325 756700192 298596680 681754580 622845831 336463168 419806489 893624479 993843392 811203087 956673681 126022975 12080731 112936788 65392619 138409605 353506123 757108519 999826010 956236698 87707649 820866405 122247530 140455698 281703598 844963382 795382453 830453518 139344468 516046086 155943942 567666073 573160777 625914450 531997302 423265311 206907498 927281219 14452588 553553735 940888806 990049157 47020825 1024 404641092 480268108 815836924 386825896 324005441 445219097 58315185 545701848 425455594 306833398 260289849 984202 485930617 43762114 347948451 198863009 271962203 788168208 781491287 567238920 373082351 983234553 696951307 429102553 30730207 932889883 919725780 399613605 121638071 915086191 7830840 762946640 661152519 253884642 930991382 94321227 588516756 373221337 696027511 587293912 267949928 829508382 310506760 902428234 115182727 3845986 189438030 848461339 397092733 300087007 626115895 423917755 681432525 981733303 413775060 921948370 178020774 467052768 225307651 921499674 756923743 730500253 78961753 875785968 155425665 11447055 205515715 934146247 874549141 5641577 508669844 482403912 600700895 845793267 785104000 113991433 860252797 217951990 425885655 351405684 285988834 427307115 116810033 606228334 795453741 654077634 475425200 378872662 573710713 507409012 545124814 270299639 199195371 659432633 159766227 360038503 247661197 52896704 379313989 242150120 321431906 574433221 76783539 331755172 435896574 693022140 976499763 789283508 524084822 1514065 526582281 120064308 447384551 259936804 274401346 931917373 67212616 222512427 568954061 719157880 314803404 351326161 216044827 770478352 505196155 988324382 719949526 630570609 707367533 98252659 87362763 792521088 675031349 222556371 928358542 191828696 988380788 984471839 897784439 253501172 397075227 917885192 217138804 406948141 496829384 437803264 657413286 175488475 612760099 810481346 578732658 740299321 648499155 73929369 922450584 491548979 655419389 311589630 641531911 471685581 837943371 572910239 850321520 214206567 161059027 854569175 725495097 743540779 219266345 441396598 913972719 320133602 110170880 721075088 675700519 459832081 596940340 836880728 174841662 725927564 497965529 566502169 463297931 132248101 115796437 662766104 172351612 689490317 565134836 720220982 9569603 962672605 455796639 464910505 314405167 502992230 599868307 287074244 219725914 934065447 516115872 528163708 686862694 676757841 140351909 256629718 687360593 599053925 43653380 970238567 484111403 534693101 115518107 416058717 306241724 253609794 102701179 521781695 929603461 583470941 959935023 725858082 790753551 300201397 749200679 786566471 721879253 406366688 670463166 789538377 158847459 343710300 694518552 357820326 437040208 769051620 693665805 531665323 842250417 180380137 158934931 950667651 968501804 956680602 293938713 660490495 473100423 247616270 994857829 279857096 853641013 928027445 989716882 403926297 265095362 677611626 228424184 841475180 364317622 833631846 853318555 59365617 344230137 861506658 667346644 625664695 548946671 304749600 369675955 867746355 799833098 54672237 769497497 90453301 463500371 996776955 747771122 687794167 738515177 968412569 301690586 394765248 313916770 6515785 165282529 24558233 846203627 39729614 407054495 614062160 845931603 766715746 94896665 880015220 724506687 182911538 52185111 865763363 157901612 302318219 309867982 82152513 50654710 85555160 954180088 286306282 952418667 778957423 788174689 688151922 474644766 537577767 605097852 394916157 434218970 128172014 920165797 734992857 705700973 223462874 120765276 800518557 152094344 839479480 244265733 874440237 546720987 386474841 595388770 502098335 871567597 371068232 589919997 712350181 101845934 557614659 335292863 509285321 11889023 130911143 192028035 246806223 789549783 418075070 640184593 422409240 814395123 946262463 633851211 246068302 997589200 350067279 797584215 77856013 182391070 399985295 904287564 881265015 319182653 43841405 180405956 332950073 253911183 937061504 391796157 57807335 211759161 15165565 129014849 992976910 968090109 742622440 860929614 208602733 173059012 455968490 556364115 958683917 847270244 737387470 823526711 268049414 911374338 431661049 52818405 778755887 174122378 438698799 510625214 246603745 632097763 658657784 873188497 653204068 465742625 532624590 677896649 184524897 597752695 723334350 24944037 981060684 251509893 756568058 619244059 994543845 353502465 480191694 945099100 961962359 820475147 952984084 953608366 628568273 925168501 468756722 803147956 451176593 767465333 774519504 440013709 393877437 328195154 490738562 71811428 16297851 829144056 530134521 396881214 730779423 488641259 404197163 643659519 969853024 350588824 120406734 333634035 791854731 966684421 369330454 315950397 615729858 103932204 73313926 381030550 753080976 274834754 755173714 81952185 395119308 283115654 535413870 697495051 883287156 520712721 1155880 445594269 278146135 30300862 50051701 411326772 388571685 902434295 507587957 76960122 73788276 333457238 557524730 34375401 176941788 934185934 676732859 364285113 70580026 395426420 970020780 74016030 686995005 655719594 976047608 30410128 329633492 155985406 245455122 868939656 182707593 999708267 170612671 82152324 985962752 559744346 659320356 566432630 808446630 486164811 91786895 821423987 797375056 846106397 67093876 41326212 662659810 679546421 261439779 258183101 957279444 191496669 254537220 113770223 16708495 457421540 681073225 773271675 649343453 880432694 584911500 466934712 607948756 258354841 531322552 460088322 504478666 431731049 779620705 292717402 966698778 897273175 18813009 78130369 46146764 136209874 677436470 401188373 304482160 33082479 384152115 89897257 428920958 86212256 217255926 541264036 50927709 250548434 36671347 836543535 623900943 1347061 606098878 829563048 224684129 768605227 842623675 750415457 273129081 659285194 419265122 205403843 756026494 609355682 181303626 254621296 805031561 798739234 151095189 841703604 865685156 168395178 957278667 884859026 437709405 426755786 336866347 223760116 142825582 107613993 946096165 914797084 721699619 492621029 481369568 886115808 890300057 380778923 341183568 809765170 65835456 958903197 888745323 115405250 300931538 265065198 163189329 163947958 199544146 585149693 310467047 299096223 60846465 126429639 355331035 915091376 135827103 61772572 663141428 965664191 324970383 995736709 559249083 12923677 989562619 629598042 742294319 242447903 69592707 866175132 377540855 102388618 446822019 962528254 565978149 529779991 87303601 794657836 868204617 255354215 210921049 710884628 264822304 161177060 841428001 648586829 538352065 392992135 743534026 459928371 227881797 956194635 113988395 973798492 377968125 226017696 422749721 424754939 956736526 971447500 778435543 758032452 933884318 809601709 33312031 819705278 18944048 188066899 301455335 630935331 215691768 679790481 1431559 401201976 643631889 435988161 997980609 369176747 881324370 551142366 862533972 350416577 132504013 494766682 157912711 836115093 209732577 545808107 412547448 752675659 562264390 11707183 664885798 881623176 989467809 523260856 24834127 689703984 2067409 156799222 145862405 386451069 468354198 506387230 813866028 315049948 741137026 282522343 891526748 775453063 647455971 108143027 91911668 167918607 754425431 37244288 132265927 102144743 419195628 655086071 358792689 31352263 225732212 703109074 865833356 65398101 957383248 717129426 46085739 980138262 149772723 726112657 829449450 149759823 689210207 5642657 338466691 188328314 831260018 983882287 342303872 244687194 517019711 55153967 188485188 775348097 657712439 893084024 423201747 741629299 367303350 667412166 861626888 434503152 952509386 602270147 87934442 118156046 317186857 290773348 237983553 93780613 418041441 674097148 274873665 903630233 304154825 958267300 290353324 336603251 587445314 207643093 871149040 59404445 357514380 1935188 770084437 329166430 203758277 606306192 606949940 495097717 997564372 48169126 628633387 64427989 417211825 994553495 264233874 998093255 438285939 789919458 402858363 643410345 352891447 746898614 230179863 841914944 732309035 741511549 663075608 413526419 389510938 556267586 925795272 928700477 539225174 45963980 282538585 727209318 419708799 596359003 842152216 785318043 710706230 197944584 505231731 238798721 679309135 903832969 143115858 433868986 182549195 271719993 80678290 424891471 221071165 744230680 679869653 573794724 358885171 407612401 680074831 976268981 572456775 216491224 437713427 831705079 167879938 889500879 795176114 95107474 615154797 281187162 900374677 847464899 134851399 777243207 682397550 591330114 183165241 372388944 328172579 18175305 860506942 79093938 202019213 831620684 895962610 831878511 435376282 837027623 879892094 44605626 748525430 401852981 869281406 53732327 939939469 573518437 739348421 47918392 823706669 422199939 712361782 9264252 379957635 904614234 861917720 285094716 267036433 953628030 694341831 908341842 971619882 715213940 341758526 449424898 541841958 524785665 971588822 678992383 277840741 178887859 624676126 615398509 932365261 294268323 735162951 966034909 131952853 821111282 822936445 300675120 87030267 407042919 336664700 254765154 449078903 139478255 910185148 227035104 385005197 386255265 681611177 923483203 96541807 594756333 75902675 178254035 283937092 990424178 992536856 599372921 679248645 316002342 658986455 260172659 785932337 95379363 941907577 339510663 836432344 571619295 16310067 263492329 790042688 46615489 683831496 661124324 548389478 287642382 274113130 284649865 966935093 172587028 607035645 235863063 909530502 32240760 979773598 815806892 269576039 706680226 804765219 448250376 935918299 465699341 303278430 963167015 333257220 230124356 611705911 901079773 289417008 491680401 887799843 965860010 34185845 439559655 537647690 587369889 575972694 400117150 990113302 64867009 797787737 149440537 885397156 852401694 718927285 412864956 798416840 976640138 282607453 899897844 413689240 545495762 546677602 686575903 26972707 654411299 924097535 126139612 623181701 487309650 10550007 188945790 133973304 341669173 225265107 782256230 697904753 565170615 279361681 872460536 735101164 906951900 102539038 73729839 150000945 495329778 72348171 202476709 700123002 311770634 436720123 638612729 879051351 524456696 947017925 637662782 366610130 504931858 522792570 607205292 733049838 52890115 545198741 307661656 766740141 761849800 970717889 439122244 267127798 166612448 988833295 393392238 332552452 899377083 831327488 860408527 533894566 310864482 183690791 885778437 279847476 22744752 972951654 775527352 365448817 997424931 858108655 705070914 728937797 419681988 170269619 760902566 362245677 210089844 817992267 733522045 257859018 984923941 95613385 822536376 942733678 311653403 55113973 382112856 992255566 278705937 738819081 263193402 514698563 108602466 398394404 503451022 919624364 465156634 45433726 457384422 310682652 449523193 719753512 511369858 788644512 386361266 417129440 91500644 709681715 685692219 281524203 216674387 730530904 892760788 588330104 525705437 489719200 563206762 723851681 164711466 118897419 713947057 849151618 686173178 872595875 377058989 212452624 161922294 808389730 93542732 744122396 18739351 113466041 283015633 334767555 338462409 238191805 294972730 646769543 182280945 585452625 986615091 726028608 313132155 745807559 64908481 506579196 33925587 25917253 731440651 192979132 554113761 486966437 858968699 428461274 910399295 421930440 101452165 641203080 845476184 459402575 709009694 584208516 956438702 49531077 767240871 876692120 845216574 81843216 897665248 94479086 684566238 354281291 816139029 73907498 251922723 366258040 231127091 484288193 291428423 122590918 198488839 177001941 310734237 732540458 826546439 45317704 942817736 214458344 285323523 365784133 797454914 441748566 843451372 332034527 323606640 806166595 344343476 489709212 987595310 516633952 8953319 808982143 878160011 861450018 992708157 377307444 297690346 12816033 430492981 508706541 307464544 824012156 285837247 915795873 779087819 391371309 810104340 657259899 58937239 616822157 807494416 746866474 34948250 137966588 29857078 181752185 145328141 486486018 807535505 431133328 554834290 834921463 739143769 114773657 189837809 241623599 521374586 498362261 266576671 729363545 924602504 228341965 596732631 578150047 444627780 90540863 521985663 601158429 448647251 5141207 648331473 429824988 950151160 666644329 69258084 899264474 899759871 882801626 426295565 976421388 640592707 699411146 233806152 54366809 98164681 248831172 247569600 616487643 379464376 44928023 337812766 516913665 59362515 880724226 178731382 422477199 425990516 371309488 69045746 972205969 24549800 418519998 909157860 138252630 376421583 20517069 998358138 742709089 113763522 850794653 174376814 152337308 750812899 50461024 412495896 266409218 646840851 282394619 766095929 378909817 602120107 770182843 735973059 32426830 536929308 661609216 804826716 775799297 232202002 780827299 330715252 644104372 992346636 637688759 735623836 536507503 489936507 776394778 108078994 927494751 812977886 396746251 717454370 162154679 925053784 46690027 268488868 700403440 321290173 896234366 943974912 812789110 579080803 536479758 778139282 93893152 997512058 395989184 727861380 992089701 54222553 145208849 348136739 512536053 677705620 624001849 260542784 170811905 144893949 305122470 167097025 607345290 161011016 253693036 656168938 950962170 974815622 249891071 2909065 86645096 515243872 569524427 167127317 465784177 850959362 516536893 668096200 494444799 643932218 532823564 480847436 308213577 688766991 838846976 873981882 616736682 130903497 998683727 410718399 40552765 603967507 221963329 733138899 325996988 687321026 853114382 465358398 10505109 40338196 591798375 466101353 261851438 353735700 381765832 597223551 114544701 322262637 215987929 177958696 971454093 537278779 788198270 238600489 578217039 833544139 262345374 837214997 759766386 207309006 207552775 334690800 447162893 36917463 969850810 700073794 615393074 353741527 623272582 884620282 174955663 302298612 160429196 290567976 697728755 25068175 911553769 787682363 561454321 861728792 447048511 60615888 481447953 78035900 544634671 63790149 466215621 886448968 979612233 800419696 823211893 226750799 741001777 386795296 647557620 689285118 171549388 474105004 257601539 164896657 508828902 359370101 36703512 807120981 23214860 764987375 963136048 287810573 147116630 734537784 27815960 67367270 925051842 389167643 245539669 761154185 364792792 402301671 116122664 870027557 23981315 45776002 382945336 254326803 832559784 389263720 585879381 250228765 608107641 533502249 413390555 334780117 878095949 480900747 890405303 422188723 282586239 961291416 801088359 7119391 645394727 390462155 907526761 685317468 794890821 29620438 467556155 418727231 619630241 140779305 906327238 920188881 441218473 722971392 329736037 538008378 512208801 218319208 776368155 542860105 12690341 268900136 9150148 780636698 681714393 330537421 77941588 357358893 444122832 320931681 608711055 177666073 8120233 258035705 423109677 890280509 647148154 254625771 978659736 231133045 4225429 761205172 947038556 636142578 512787641 414325506 726313162 551669286 97037206 56680561 764496845 927559961 861543548 286505855 423997801 972355625 372761546 59675441 983380593 712162314 473832791 671540218 614271073 401385172 907131967 670078192 265074097 590433602 908605687 997796886 85447065 446496800 711361070 29434511 699290443 962967008 239107571 920138899 844086079 75842266 642705061 591822789 416171816 55335221 807001112 749160590 321826001 999065756 337694546 349547152 693880954 119246650 264881764 353172355 647709339 284084600 676136787 318168041 549418064 310972252 446903651 412208293 359577109 219245269 280956634 11237601 796872934 837172692 214731583 947870167 227603319 69429229 852368788 758021362 536038379 50380325 830133108 576630119 521631750 585035492 395776133 746943766 633633431 548272226 809427433 11434334 543605085 614029498 894950532 965439077 727856413 135547430 734639610 136946285 814464565 481098864 982286346 222643272 943814813 251876887 661422406 601839138 653706297 605481334 611568085 544449448 201643587 950018509 91785372 285464529 137368519 925485035 322048529 471724314 36428354 763936648 961510045 814786216 255184110 467999048 363224903 695566763 47226676 842025457 761698392 854188927 152391 186829413 701421869 640183891 351547337 450990379 889075157 188300185 574222601 838047067 874623751 222674940 854547591 565770591 798679121 19440747 231051418 990928535 894681336 431133885 846088863 47724140 971313624 214515841 781417433 237696768 630911647 862703782 966992764 112268462 957256410 429472340 163983469 822814288 820441822 544468713 370334560 261136083 909341984 807980584 471073051 403035243 527511873 112018554 478203119 194242572 682979731 139432271 525512489 865405922 440430673 329230332 239032065 571093610 111802523 52546117 199650641 703867845 642004747 479925287 331375305 586407899 503148725 223228725 761563870 264313292 338224546 364084646 650592303 241275684 873742890 227130521 380020104 649206139 960611036 403370296 151883323 135139245 390593392 759837783 45033520 907563648 364620448 74455524 150129168 587825874 770522093 50925676 256710504 949043565 2095166 928417819 535047535 771697045 364090656 276311931 417673565 895804986 794081978 855611507 217725155 280427666 160503704 453133461 178003382 931666185 303026538 185614176 514564906 3742323 190384360 536138729 221776307 565326227 506755312 387568267 985074860 169351763 332150417 454151814 666834746 949364509 609959952 296868472 242141046 252447250 644674997 700270599 358974553 260418471 175292944 814095948 196314498 756307481 960479187 28180520 872457738 367240162 260254449 59256997 539411466 431344842 316584133 825006849 450675258 503018348 462341641 750626920 749852659 394122681 195624538 158083198 330377203 912498474 639868368 3331487 325018258 20638409 154367815 871769502 81239041 97141798 32845715 274880016 944854163 820055575 509736179 664258152 640743205 197875587 177238530 510401378 336852158 759912412 846017323 904551524 199859664 995882832 569212543 408000498 81144943 844672729 430651372 432224487 589702176 187919553 617541149 884760498 681963500 3793189 570892458 778596442 365425042 304100825 513775738 621839871 711560781 388384939 343729379 956992195 580597231 890444608 582798755 159644345 540908612 639707021 137259631 43183573 690291556 39696845 797774646 632734605 513908843 963813205 363869555 850803501 264861046 868600488 225314048 8199854 802047757 123267725 381453215 81370220 944643681 242977533 116119949 205678361 442118005 334082405 184627081 274782566 436810239 683377415 299757379 445438612 271310245 624305639 956926316 859356063 943192637 551148372 75081950 596651917 539974476 827548453 720072578 995745675 372080851 538059521 23776954 767879177 196911829 492350875 189535319 376995720 986115907 979385589 762021313 619020453 572545425 510097694 347055021 797173466 902451078 430445863 314930467 298291672 376936955 43646007 854376857 481703395 810610240 600665623 642871733 180532365 237915820 782038192 443552753 551066719 647873588 53611827 711964591 118896745 384306934 969812437 875201093 511060632 833755452 570745958 938324448 404657269 423841123 970982752 555849194 954642851 423586778 949121174 953019558 803152221 619871317 676482333 337177548 819337268 985486083 811836692 424495472 249085771 295699348 733201096 941122770 768296463 112857974 639317133 233726486 976225745 781956941 291289212 320578488 361748022 934257782 500304435 999285853 306506261 950545819 713359368 250844822 841827820 631273563 180923192 68120937 212271185 556309653 955164451 56913269 665656080 95768136 556883732 649427158 38833897 47085398 705962180 147971044 114672168 566144422 554921932 37008016 785500282 600619240 87385160 620848611 188034377 121406162 686115324 844339415 519397651 788419726 466066672 422490644 399820429 391118386 288481998 217061957 370133270 844005278 10808258 497128593 852282471 745544968 150757076 338701360 861426804 55335264 229582943 466315557 642250245 730309038 930224968 227186101 70546799 763946015 318245797 879472781 128440479 768783298 573012924 873492252 474340926 915831842 244630691 823525633 685504165 774293678 313571589 643026517 452259206 79057893 703788100 455439846 117802122 277832929 876567092 635652994 671156229 689176022 465932648 356222468 536237245 337820981 741943901 443563380 922374466 476508208 605202672 174277693 637568582 913871323 603578728 3710686 295498847 929825545 976646258 361666570 220343075 17240641 441942957 860326333 196071194 323602750 644535370 106250429 836722735 632098440 786224054 92524918 643477955 963793436 357572340 653354707 417634628 557836239 760858359 561470973 700227392 27764624 480232793 246896116 22649600 439105439 310384657 144426955 347384646 147466799 632456689 56996159 150188871 918456339 561012294 338633776 123061490 283258917 685532480 440457797 539085747 408722397 191136675 98120949 934058367 478711694 556902682 223640873 722082848 58283473 385787806 260681026 193593942 776059364 833687994 78381274 511454770 107179747 175337391 698848186 35523197 180974786 714952060 65139038 139901392 820696729 18442378 85314616 175119033 460392227 784296389 558423793 737354222 345728192 254991728 612629264 351665416 655377289 848500625 309932869 367599598 939945618 115297593 546164433 651480201 754400536 965309223 907144795 811766044 203133302 520968325 192171997 102492364 670813343 913699346 839404523 86421253 591905580 191547936 254029409 501824180 203283502 128444335 318254422 417044443 952323190 383301211 632742940 935042743 906986390 399228755 409288523 357008221 365044126 294640415 839583129 79430417 478994028 669268746 599021040 424983078 303646861 554856561 62593640 193711570 201831408 867726863 628926919 514435750 572827514 54298829 887977463 887130056 358488658 305296477 619630003 211739166 41944242 851126199 851020786 487051452 749217617 996703072 45807319 675810869 166728434 720629615 377254114 407743735 848490662 880079185 240055271 135742979 915703569 886229646 885574479 746639989 475337278 524374906 874882810 112802110 687623212 817472191 922580978 813960737 354161822 287140722 570305540 794450636 501093524 412336296 539970602 729181409 515103918 761481875 730057890 216797245 26870906 337663984 371541976 724134915 478016459 521982334 841409637 537793481 116570404 744417209 808088435 545487568 40581337 692024219 146249588 492427669 347406023 932373494 955511357 42005150 422128226 708687069 575560523 79991920 136092965 103867397 536263765 140561067 929646066 63467562 243709077 63762540 75133244 137478267 574507739 428311784 731594219 358413069 909303877 152608763 709655622 658492148 724531985 844286344 909884128 159822917 298364965 387379406 936124521 596069457 243864808 281253319 415418601 209045543 88581738 693188126 553550399 17610406 314539990 965331856 356591846 81144815 320355001 102326916 433140938 769869016 755951351 737497231 430175072 964948650 623208673 682324341 861210147 841641752 514009556 523773472 261091269 913383826 752430881 356668084 27541123 287169622 322428951 2152178 853952584 138517234 126517048 618844497 689050295 610354289 718510408 483637609 664191249 599197242 145162014 377187188 422129692 706084958 390488793 97024702 532972196 196609349 893464828 333826953 310256434 852245979 808287379 563733380 420782931 776596172 860444467 166535472 437227759 89368221 747135433 739093320 794495473 18984090 663117723 880557124 543532402 140109395 979762958 93518401 718894483 308040477 128043190 187630039 622853981 263547628 534097247 10025379 717475588 329859236 981431108 379326064 795831925 761007158 773106437 442852404 238875426 6172735 593261860 347793304 356595845 509801639 739107191 767037398 751802364 942125185 328911699 62660104 161468166 90395968 601504541 696342549 720906666 346154623 239671231 565291536 862720841 157950619 602739051 741479658 619984478 811192632 345526293 862267210 139460403 450494925 512419327 904606419 201164297 717260161 978883497 561441227 902040319 685227385 532906853 30674718 276213826 175319451 606499584 940467643 897595640 776292541 922515107 539223939 788547733 994643189 404586203 875083977 302949425 294856905 312683710 242875182 896953174 741322738 666053900 314875676 678998399 175781785 440185376 787983157 38129218 259647887 789892652 712388958 554590205 973554160 582626659 107526743 278820446 755871034 713355942 809961317 844078489 773903568 543667225 191701217 399947558 660742976 409084889 81876456 449141832 949197789 157794673 892572303 248021877 280247011 389150510 165300425 882092388 454294069 794558583 145447060 384831978 876155911 682951898 111053759 691700186 866542136 129856322 589902259 898871807 94924212 288434548 377307913 601364742 640613316 355634996 834861550 18750382 205900089 101084500 552831357 920909802 625240842 849777955 881171855 20434123 888365423 398600189 781217258 646453914 747877860 496214216 620156075 517903077 92036597 119203295 50842756 141394554 606737717 770513238 174108013 361522006 107159775 656941180 292053201 276906771 32980845 752647580 664091998 582027874 299349173 847545515 275139343 789281037 949819507 627141975 895154827 443658609 253151350 677052263 286933899 431886670 43807811 293012177 939162305 414610861 634383440 919561419 398733941 216537089 865672578 523713925 490133427 37464840 504568782 696615022 245968226 358367762 404461303 816570822 641571874 555623482 589207940 744647022 703197245 181860611 637537884 23738853 129358753 853297877 498532951 145232290 550902251 654743772 99867915 129142423 8847034 428673860 579978775 931811537 682646249 942120410 669863727 843548940 135838557 256644139 644764682 381103797 38607703 793880642 921959184 529997108 562915076 63035337 144362922 577921142 633982123 403729117 208346077 840679930 662793423 620309914 892741825 63195869 82989306 267556461 759211670 966654002 368134580 452692243 109410019 457917885 932767243 386133404 720607502 262554620 510949520 151590089 285019691 608018394 301160448 128014869 946527887 696340271 166251221 891605697 669884803 571360359 743707015 382852012 837202032 858468626 374107780 938081139 735110535 230840718 906606836 112410595 730578489 435399250 407271210 253564834 773068052 458655084 539784098 14517462 597326967 381221657 802607600 760864275 309047740 708535246 835125205 462091280 913944217 358985935 850339824 291506468 964910131 446852653 784436265 107356534 925011494 363919718 842163966 412663487 385790072 778506542 815443114 566767337 444919690 209290033 583850191 491776074 990175533 905126672 155902615 247380253 221974759 8789115 574491932 48263079 43356270 98834475 917920318 934747183 79133686 951085681 804734418 659522091 88473776 286422041 392102811 661287465 35035243 630749839 738330558 600890865 138766975 155277489 359490092 571088811 4771592 964329199 277892445 827048735 266611334 71563636 946447232 897590382 595849961 27096071 943833900 631674302 606674692 456402902 994823543 799919985 399268519 128928499 816312893 688293213 235505164 679353996 556722923 988027957 615949874 50973844 411046057 297749788 574379705 268487746 362175644 795091497 214272622 334326639 42263285 665224753 502553759 178063719 652736290 626156797 719805366 459888833 91785077 818239335 769075477 469889852 396049521 133827946 165491551 578283899 692921983 831413767 961219677 108794580 611932512 517672194 444639665 976992915 569847578 157808370 638165522 686266029 129117799 269662365 599108698 113386364 834079691 572239848 625687334 389770143 356987921 394276912 742376199 211542420 182766202 522462859 997145973 710711448 443886766 524115601 323931211 69272288 797278242 757737685 938955757 87947471 65388229 578503604 450736435 914703146 411802127 384873310 467450015 447324524 343648248 850886391 619025244 834827863 95378771 293929825 836059882 735931219 37963359 419339723 92656197 819810917 914561145 641180461 624161953 593621533 831733699 964172593 459388352 672820217 834505835 680506323 396726069 129872883 969063694 141437579 463194058 955428847 38895209 151414102 23177440 86571454 95762032 709607611 936558851 917055254 901528642 260200234 663753974 556811766 551057435 671084461 61622141 225849858 398641959 881861937 3192517 263087008 190651237 551519852 845118530 143136231 972170759 34012227 657106124 775498159 262787500 282720543 525310685 347346 202483844 513055902 522005603 343600425 582827490 842443011 426885336 741642454 615224004 82206927 487832227 334178827 623166470 992432449 880705477 505910898 649089212 857250778 478553107 994064014 95284827 262046799 65379997 793419969 298355222 18356372 647294202 651295992 895069642 672220787 622557055 399972365 778695585 297092772 964107713 595670998 669817584 360075447 114352488 189845090 175446557 364408770 912025646 164182174 542285463 120970637 204976221 786544712 859256446 470449656 510135725 768935578 609293809 480475768 875418081 609423752 521475372 797660585 508560087 186469147 155457224 204468298 213959282 380616636 523110013 724941950 278035361 643134041 422162063 313265931 842661344 979939126 905761356 595598279 539422480 737750237 704836410 622032782 7278551 60515056 29145999 560125594 717366744 844145548 174148802 281798600 563758733 332358435 132177866 76973530 155486167 181983206 133040139 791127965 196872480 199628741 895338138 152157198 408452284 648269877 120791408 542221096 431195604 640587543 355323227 953061670 274911259 557969800 253291005 333522411 179793137 994562664 55180539 287540003 113575892 563919965 376898669 400566690 345882559 697900216 754001203 62180120 486621556 883711393 651937238 842068428 441118076 781491155 892363645 739373501 46344936 851369262 495106270 623264587 613034254 61446165 549538940 253313983 904753019 270755715 301713451 246658392 779716602 23929435 993327162 989562386 384656050 554875004 792199701 417452712 522823592 943008852 810762168 765237559 92641402 323424810 834921019 905585655 225857233 21886629 395128595 729915265 872031122 281537103 500542442 758603678 301886058 384661193 59506742 24708335 107492780 355035913 905020375 207565054 881817737 790989942 484079207 705549940 702337332 873980149 944902241 667378095 369098590 615387846 775210274 767975414 748346127 757100400 5594062 430129817 473502171 536873018 8316906 918827051 301234964 537536852 187896559 572796710 542415174 77675321 606828166 943054534 535268775 394334341 965310951 197865007 127435707 943370636 214021085 75448531 499175691 538329030 512719868 139699769 319507757 694793022 986223149 623146440 553575329 239814106 314182007 52156421 604701421 328220888 46551124 260166579 189453389 965099434 874668347 654570385 617227135 712602361 380055584 923786426 613021039 535133240 913912064 754947910 702234162 405025557 523856538 605724588 620005533 271221626 260917944 654417451 936471832 552780493 767535006 488408852 512779010 846801724 97333969 396923214 888644327 442445491 962230595 348779623 276777430 387471568 261454457 790159298 308739783 235749022 947246027 706207285 781847872 914740075 723185153 128641438 322193488 495584082 232150476 261103853 262040309 793969508 89261177 583334061 841597575 965704023 264872254 207357387 634590785 592295231 726743933 768370554 744424360 829060143 897153347 775252552 991673938 999444165 354011741 607368891 146924386 373471465 548166461 502332482 637660578 358439263 427108721 797718973 256016441 682178538 747575143 641917974 945610059 49051601 598232347 725357894 115323632 692083518 8083393 138695391 138347220 302937095 444371325 986112521 980802372 179520654 862276909 818080974 348614462 19933048 537275296 128314109 767524032 637906662 488092893 796236102 741091080 74973732 778418780 435235355 474927068 270364049 794385538 110422295 772702820 142439894 855044272 129346127 134074308 599716413 920307153 970017130 21798165 833366516 481963201 159025126 52356888 525153467 979431428 47426461 354268129 591684301 447248637 515069178 394006659 443580752 907011170 121504787 741076667 520538009 699526141 951565172 474470183 770092933 758710200 285377272 237375254 804468579 586148962 63049585 947506593 173811815 619922774 320010492 279629682 329541198 34939676 831338893 496862185 462121959 329060572 185530432 356815283 869390645 43262286 719271847 692881310 329280569 610575546 480137271 448169235 531255260 906319143 61517573 254660199 520870959 251970250 159165248 921504951 345227653 605980105 785036462 417932202 93318250 332335293 23120191 630152434 266307868 953754602 909727008 260670317 616571575 3192691 164274052 172242783 79922697 186858745 659564674 156477630 425347847 40428433 86382898 15794323 689046707 914853238 277314144 341327270 824939355 749853668 663754826 988973363 833014714 471051272 233053217 885005479 439760130 472101175 555503998 282381323 950579929 690011447 232801107 23810469 227935538 127343230 113555530 786963224 882582325 282833190 414485131 92896061 428431822 491210862 985694261 432292274 524116056 558438465 225234915 73707288 491476482 165751535 343592686 476870267 865657627 875321482 355888137 198128841 817795523 716101079 534930821 773259040 770877352 271047967 263693783 750629181 522173464 188417982 734905962 811670448 891224326 268413863 61698737 428197147 142642199 220443906 177159236 608700334 896301679 962368864 653096255 456247538 841228049 547156168 221111876 354857051 739123649 780159967 212635308 497326120 961015468 753330229 607630733 576203570 81839110 313898595 955451138 692637152 338047111 694937620 802797691 315161516 883058480 852788620 180640937 386169147 236369940 943292106 560337779 61007255 514974162 468048650 640123039 767121849 343247949 688717680 884526373 139534960 830208420 916225824 10010126 37340850 650179379 167540093 914126951 513654799 225961008 813352815 898174994 461720509 809655275 971085465 478004576 484318394 612906142 937543617 616896187 680910653 95662447 172449500 834309575 685348976 643718462 185198498 849195704 44321639 781830976 122878194 987275532 612587324 501064010 705036934 719931391 325521881 45278068 492036220 662903550 75892980 188944028 957277734 828705616 482934177 652415492 837417990 700545745 912586748 216263506 607741675 92551645 473879396 537189388 913195714 459829283 921828060 332648017 874964842 152454256 352261988 788852374 503520010 350958014 68177397 747985245 440905656 997708874 361758003 470066244 803220047 300219478 269874743 671272935 145847090 780631801 446741812 387764006 713089804 2789293 505250369 388912669 255327894 160954755 967426529 620691638 574995 215716645 632360551 672726942 344714182 872870554 300029916 228422468 700655466 597580724 300923280 434511032 686906909 84724218 427364531 356676988 28178695 328389836 571413181 511315861 449016942 903475196 168299250 879597664 545602357 329602789 601219550 115016453 212506876 574027743 901108812 477639060 503535980 458956939 898842467 790374260 481497511 137834820 758744440 938957880 327257770 751334931 163534114 690646658 871576895 660610111 713291384 337712971 504597156 105410732 249809355 25194107 794405830 5998642 489576763 896480943 979850637 718966810 664685398 680557302 537708235 614833058 480882992 726153080 769387507 867632273 612215692 449661710 115722221 12722481 468809440 913727593 41728522 568830462 517802770 420111934 944878097 770398460 175997321 576888227 568494220 729192056 843096667 490404381 471998309 679287968 483494459 505318278 23444597 423619541 970237240 646498302 623930325 681498571 479308062 187879142 833370079 899030574 962923717 698372256 128796703 895047081 881615325 445909639 1653950 434159829 225018689 160207265 806616851 83099298 206028457 633741336 214861169 882254584 290041533 230590504 935347557 422059946 164465661 45596869 812029412 143005868 733867604 892245853 826507606 195447361 970464429 852136259 845068293 751284748 512958088 314089947 257931278 875585298 952949294 429580447 512170790 622867736 994022190 892438734 722882407 249123036 390866105 558352281 553979120 756958922 964673631 293798197 274516325 721976034 219313558 965070330 241779090 437891359 645848047 179242046 889322140 547046635 50234358 238999070 410994567 172690712 136155552 308930004 471984584 645751573 550621857 435748658 577401761 293021890 648180212 6276717 411594839 582879185 168270923 397591077 836431358 360815498 922644520 668743181 743098856 488583174 386235883 197497317 577547024 714286104 673646211 873498154 421519310 470667182 154490785 317432134 988760182 311857057 956888402 909554673 788459613 497948767 561642934 101195762 492810395 894609457 964004824 209949709 396425947 122291827 585660592 538297388 697005406 395333546 484467718 414325462 925550545 763604042 361389939 717426606 181704545 653204117 671308108 368763037 437024523 398062982 592255088 631661643 793619913 560806032 849295268 528888447 31117859 479566502 406493433 265241239 826686518 571112479 884745272 340044778 723628542 688553759 233963613 818378430 175867320 347974280 473347387 75088132 547831900 227524183 563633307 202837046 585576470 326794691 765135918 42902110 19077599 112647252 847176837 887779909 919865556 873426443 399198655 397757685 475335887 724549729 296273684 162320656 538627993 406297892 193220883 25154116 990737043 994377701 866063487 44858354 684883535 521861875 140477267 111744391 651395935 655586847 514684661 205142269 481072532 222608177 689578927 42117840 260722722 326843302 775927550 302917582 120531719 350529170 417798869 250779022 229944796 720126602 859497014 373808448 11076804 281633462 808976386 527677695 832809092 370015129 459967312 280299111 646494927 568914767 123585498 416288743 669834344 46153031 793368464 582113297 516835666 878378248 843376731 434325650 805546508 422280635 795076272 447438712 471880025 205857117 340588926 733297107 543559112 786644780 804342430 772832923 733759764 354018495 222758133 628000574 118789662 533565203 199536270 84443576 629301625 172719524 62869451 882661111 393696248 260163707 665057588 513344436 60380306 964477784 112079239 774658121 302832012 228108161 662454756 148251900 660240109 687530285 800331785 449393622 83600632 797317251 224608928 413966832 723166536 412676012 151153096 991854600 394045993 630207992 429280785 866133281 765634839 670487545 908194867 359729710 863085653 500065211 571867919 184383973 70981362 984270993 217222623 344729390 500987212 969975921 45694417 799295076 688177574 350501566 355782031 561460289 395490379 211094190 278429890 919028015 41520701 363941584 677358323 431122831 241074105 482704903 358188993 613914421 664085965 538030008 723067846 528132341 876940516 918391534 44060091 747152649 679949840 658191971 985624502 728085400 454521529 581367471 171245159 440905949 478275858 850826387 942658311 401906601 937928753 788662685 636558123 899534065 129308641 51488359 525480398 652689520 913677635 528253267 915358533 361445124 740653954 449560082 493060784 566731579 551091538 707769153 411710748 202596883 189937840 401005167 773491738 947558025 912749590 812684558 427782125 275158745 299840671 772917136 637934465 533609231 548976794 803303656 89871565 682534394 224523833 132203059 454053977 3419988 802670500 624726692 470030926 979761495 680980464 788882447 394909210 501440773 508668282 725113926 358082143 864146720 957950297 698969747 910024441 168477231 739115909 771715246 284518215 78426482 583046675 574720179 203294593 544742218 730797797 894809768 381323632 304591676 157785560 52266454 540217270 357691991 935735637 851394254 397730425 895353479 229839490 915341246 10230580 349483093 164439967 51465910 606172775 87980556 254239825 273648943 559697130 281608413 202673039 864164323 314134831 797844128 345236603 795658026 945178283 670259359 924833415 13278656 545541331 966249765 267481502 25502213 726954438 786137044 566352519 739178760 523860253 454799264 708647347 13999270 756314854 731170413 809796755 340061541 778245677 471278408 803781600 257364853 282967374 397223107 467325471 907312973 427808153 855213609 399498761 380902532 554630876 846787092 802916958 988830727 306452827 462070739 958220785 429184356 884254665 401185342 576189405 967667096 641585 315947001 466882982 247677163 966448179 878301433 255777057 569910901 613725207 290902099 598388216 555027749 453383174 386360934 101532837 940069953 469810127 57816299 923697951 408203750 233539960 915664334 135107569 458515354 90324591 283946034 83722261 877738707 438875324 154299443 687319246 216655095 226863049 822572868 460741455 626431170 234443955 827598863 315896349 949310762 51993141 950599081 185631316 374024240 396007174 837694417 946954854 461677653 578870989 511068171 690657198 964811363 190941707 127714967 305956422 571032124 873802164 768017509 269765914 700268837 907396623 969578638 308298233 932204483 520009232 555466448 544552757 679246264 819888676 258400854 63096383 548781270 44338471 756920677 170588497 71281221 621761710 990144766 548248262 120338921 609419385 283380095 52294928 399044189 628662886 910671918 728639861 503664659 448847046 234138631 242208961 807748826 757034037 710752013 480706155 371051185 670203411 73863032 945246865 309800427 489336239 74674830 739324723 230949386 300444525 163180228 890344066 461803801 41901172 812287794 806071453 123215454 128746381 912853809 194402935 637978286 58154345 994563699 592188381 407668578 539604876 62687059 759314626 537807449 128739564 905091520 410273133 195350158 240249771 100218002 953282851 898305580 939141557 74222222 123029499 889510681 107641271 479187385 932365468 413065954 437528071 888599769 258717331 694988324 99897387 670468548 745817676 406363397 793592711 792521831 486540520 405272613 109678214 118477479 217705190 298160197 845917556 155540572 478624965 2945595 702463776 442003288 440101738 900164204 753145815 310904398 341611452 726779873 107937667 128545472 585685184 946079214 904284887 204942647 813647121 223721558 589600161 273724624 587720135 510545245 839566736 702688184 910632811 808701865 643199818 179073192 336973686 28034057 607428351 483937087 561837734 738230206 812720746 494408507 326929232 257073619 312263254 727813353 619517208 911999374 903359135 811060803 360823478 151554153 799338427 920815921 297070093 846650877 669355434 192552657 820944466 686733509 942432355 22401553 33277895 20212673 210152420 133527188 251064142 934014255 74185479 714824320 572212822 830287694 746438050 658367260 273735263 286697727 653544789 220628657 544424211 580595670 220334141 618232948 894683393 860026409 822365876 418396323 45201886 967038601 790356607 825946538 504524583 688183306 182663425 538817932 362735868 688438383 148405219 156158193 982412830 599492696 448040729 78781814 9482122 775827129 815027299 285625165 933956459 653540041 946952400 471257796 213787516 805546617 952426216 517012773 841331670 327171724 655835986 901391362 467735445 546311508 761671938 374512549 678463046 80462860 815412787 741609050 722131414 492466100 718171562 577141618 575664103 361037309 655819438 318983013 274262590 350131859 61340714 645192695 189019736 936918992 812689164 283451899 548315432 659840575 699922426 73393137 402816501 791033694 605894013 236084938 668678158 977143448 389364045 152370141 25232126 566385562 93519963 653991699 573334253 176364305 802474777 753817807 486846528 439342489 510113253 160845766 590251308 691777746 440803407 530694581 108331969 495478159 416462127 178831366 645943994 579769547 133260222 189803246 724602535 158374904 359192374 607680539 906200960 114189463 427044175 47603053 647862194 662324685 113176773 526249635 715657008 144403511 978440021 932587246 960002971 738879202 859961633 136721287 743430763 92378894 8511957 651737794 215127310 468937603 851148120 108664193 632620850 716601808 842369975 990485140 708775211 660558520 860423868 737310645 403541660 905709725 834401986 55684976 244693704 97280584 495522727 756211503 735273278 960509824 654033043 467474640 68820420 661650180 595767656 520427561 103420764 955320568 577418151 7013412 48286493 240511629 652406188 303739546 365091627 787541306 101699362 341936734 403829420 418207962 558740779 760342560 385755933 268313779 517910258 91245679 129074915 766987933 295491378 705890445 530061516 613227368 36387059 334964217 265039618 488384453 513842646 389766820 516845097 696427675 137337600 620741534 669874715 17307029 452411294 993950830 322646375 795742655 791621698 610750873 952384249 712503677 568529989 386774082 287640378 665670517 883718753 695525697 209370104 757990118 595288752 568425621 588465762 382540185 231547711 101653244 974357337 38492797 853787488 25359791 99382035 140400403 551335496 347284265 422977366 673333564 262941509 61718132 681062439 89482664 751130830 901158568 242223742 152848293 45310866 783640757 950964890 684510813 256048989 461191609 311754900 776620170 434752844 750262160 480858143 358370355 876189566 797644281 802763077 555119135 813675190 287071805 868981778 153208157 351585401 484413747 177653951 787929578 681786561 799469147 498933121 273944467 193732464 350746558 25040470 386857428 540266333 490250541 993251930 647140258 729968911 958343324 837012869 567326155 395696647 505074318 234005339 245520888 292503499 41816822 919565748 353533039 74091429 62772581 433265652 53299473 209146931 109946772 815350826 497234917 646869077 72755162 1872829 555152415 607485541 266938860 714202000 733576729 555949109 616193934 488804563 370663936 356317721 421252261 669210918 470194212 720799008 114498836 701873920 131280267 390029636 221446848 964592429 393749575 875997168 484322888 819660323 925966943 349892014 332623963 676010227 991829699 625035653 753789061 624482684 639267612 740521549 617613390 421381244 573759150 386577388 917527719 450491303 718008525 594049328 731465296 706513408 612519901 18073279 208892274 491903955 765953986 477609603 448011176 8231619 867311730 110736084 959008438 278362604 673213874 423335544 257770775 546101751 656298402 322295907 602461931 844794368 909254063 285375182 114735262 101811300 223778026 521531531 843010000 725500174 423997256 754502172 594293793 761157163 475886518 550889493 360407785 593166260 528404447 942774454 216957142 392487460 645600522 222388057 119384212 735139475 102778861 758915619 216809134 928917703 926508489 970488067 142494260 339648858 36360263 435743556 667498199 768596791 471115733 139173826 573679930 989209632 902658423 812124538 426610838 720740746 558023370 233419642 774951985 231271562 905975075 804007187 357853301 905719701 317509272 638158305 298553271 206462151 500801167 109401928 95512083 975795776 385538476 669361270 555321895 392262356 702439097 680396909 217681162 668934368 458479830 896836501 516678846 620526623 493984207 542294645 293268722 231969505 876175311 952747104 338229767 480146293 687230789 281465013 305956482 442063067 989345580 642514606 205409376 455588567 687970651 304352371 263501390 341290168 878835268 39577863 558638429 806883755 494644144 495297840 144757578 717585899 211262955 349917976 513619137 778980514 489558378 379867342 417720026 873187808 326404797 834249637 624001054 17128996 163626585 630059936 277827077 668546636 353271212 433188878 339143985 345093258 324022440 304236044 833677293 588663612 205746379 19014529 418338301 649764148 13381190 78203543 382550835 687346763 212750794 775155807 389196517 761070944 538802731 227423070 973190639 41701983 774510749 749107097 506904410 235166782 406811827 863346444 438110853 170507936 153733569 775624410 537373054 258019018 333038140 726078738 185735900 397824939 293721760 462365294 41156110 384841884 748183575 560559530 608705416 259140007 330943481 994214822 15509057 207492313 445792048 920333105 398409947 738999396 491446703 506640229 774234796 66192909 461802435 60580285 539211464 168099858 566564134 955386918 938138579 805950521 322601537 377839396 290029469 44387022 125272273 530474831 941363322 971737699 161900758 914269179 147145212 112860512 575250233 989160462 569086843 107437428 211733990 828595128 944319891 223261936 519512332 899019049 160616350 520057453 356458097 549474561 431374871 739764392 290211530 379086513 79199323 93893637 880886654 534014166 793671266 598257954 526552043 292530800 573799213 705742431 975911210 23496066 862025987 50339355 214499124 474411004 742722153 572633985 130098675 498691148 918533659 424573615 509654770 503766674 11186049 892565205 920877000 496024304 218925208 226790160 866959446 250672874 684406316 252728305 379045340 252908582 279256223 514004735 465938551 733413335 180112011 846211510 244447505 674783186 231757413 346344785 862821166 610000986 922791791 460582582 222863376 645929755 34232112 952103009 577824301 55700184 203025517 856055290 732745182 29147410 38446608 651242897 979657289 36259743 169948651 745845709 591595494 357693803 943108655 527545870 44194666 442035690 544326637 558717418 273173060 489482622 136036288 129727904 473975323 670855748 781703173 609259301 629442578 600274906 629900207 432080175 520510116 410596860 70128392 940754649 23193037 992130609 864194883 158870183 720642024 686441873 793437597 678134968 783688833 402055085 938162949 677090428 568400235 263904346 86115535 340029147 803854696 251262638 753092059 934027829 869668650 870115035 578432382 633978040 74588993 636216093 369906954 8087767 396398659 490692890 589882104 611810595 504107281 1413410 828393583 573395325 741507083 890018277 142061430 507765650 307258674 418538057 245609479 611927140 618089480 930451966 738328025 54335525 722148647 860147999 798706318 22525319 793654477 610116022 235291798 995429826 743696589 535929441 59090731 139971713 292686086 392949862 463532887 12146828 316313063 807906263 86415309 404387568 709752780 20234707 550198469 246034988 524370949 706868435 176194447 163254760 691635329 416354308 338439688 648903137 91580178 391892199 32289057 360736051 526809916 925851075 354174132 774363202 621750312 695045563 749752775 150550095 752370034 643309746 243845741 586038633 520069058 169802197 153250470 324739 444446866 515912590 38749262 387440553 805177523 345905677 423176605 428642393 524378775 843698755 394470722 710806920 433802946 874869647 739219571 494974080 526646757 586885055 571176379 932237757 943747393 798840503 614754144 529784212 955638718 131440008 989833846 706972073 8636661 406164071 516256069 965647162 52712271 869672930 548880188 729577778 575410607 239632154 197817875 359705924 780282857 263842698 765943369 587423148 663966086 892573751 418154946 488196820 194793018 831329290 482828121 270168742 225404912 538804982 572599760 550917894 327587015 396441023 514419086 58335682 811256645 59067688 394777048 415476143 382191129 314094708 744235842 686584260 663481422 813304461 276525611 621173371 17139111 419468363 735689073 179895805 778764546 359004502 851623584 101100501 9457447 507945901 978873314 345348683 514854404 78538681 502341192 103664356 28686825 871511361 979587524 932017508 221298524 843831908 442590435 249213519 29874946 433419848 274090298 110415133 166320349 247745238 301369360 623867480 829732301 634017174 878258990 817838791 978545582 763525287 225220079 803467843 96646090 622898952 772352390 858146493 256183255 590053961 438174153 326554162 89687700 413726116 134652546 540282724 373729258 17971732 823246756 241081324 788506947 260633896 683291571 936700836 551620948 299589353 248934725 274605337 94317740 422255065 246979421 703710766 195205603 703478917 226276463 743144711 162181060 197553216 568663821 882153394 531420712 754789197 768433718 513875726 200458707 605004572 474124067 749798960 746657072 76167072 850174827 555102926 538368390 247273713 286469473 770553295 311887046 822643701 244941995 886324431 561880729 999209428 267501849 473848363 80689954 762349178 777541630 893210089 976381030 841543772 620104622 928096512 334340547 647953354 186242586 627466037 348930250 199075835 337782672 4869137 814463969 551247259 521592891 668740595 822040405 294807500 312888120 783911572 440976952 831333155 13187523 525558039 133502890 428672154 774580163 680551191 754540835 562419835 48696118 109771849 120323231 379874303 766668823 549922314 307151382 967751018 445235430 177610567 594437250 991983087 787428388 743693206 938495389 297331956 789491115 917426980 79249477 928182812 496569041 480398490 405462506 269593752 702041401 634092244 492356689 401087246 625209814 495943198 30532878 197446438 489761988 935419073 296181322 113091849 714679332 417231988 971145714 165928363 192231572 976308252 728023285 964665672 720280458 955940580 746457264 134439959 881200923 804414423 311992955 752844189 996853044 124741075 19187535 694540925 748250299 786226277 444586125 210535612 121729875 11891820 865414640 4037491 484934925 651818522 536539601 536152473 591947944 731798405 99065304 804212996 690460927 374712043 216954947 525867151 117139108 895655545 90610970 774075962 376011701 558917572 920076561 599178076 238957930 757830283 140511111 632869289 958642650 248554675 894013230 547324331 118901745 284622354 219557913 845140328 711658766 726255919 768330920 968198251 405119283 409934451 499314123 906920695 311605817 766040458 998269739 586580951 561663047 90608005 816602053 372915765 402736969 697685470 471218489 673075658 24963378 653711205 454421332 733889822 159470102 536951758 837545576 639866884 185586370 378078489 634666840 499525205 914920382 979245407 903707519 828824081 815056188 52383042 322497791 966120278 945132634 418856698 480798775 984818444 989463365 866358198 492213144 501587386 369949270 877412821 401166399 970063287 606902192 147176037 536323584 378779522 941687409 524939040 920328513 185741882 954849221 449684251 382318888 704587462 241573136 830930144 335925773 760133824 486976339 655679835 703901628 295015540 686595712 336192045 781068426 104591105 72452099 830142343 288260200 955489942 544843373 227723049 287193520 257229468 677380151 45397400 960984396 682921338 723654347 213044864 322503743 308297988 526020334 110787877 51992898 103859939 572398132 653316955 218934242 864889680 827136951 336015630 149263414 833920664 31755835 217919970 322968479 390473094 373806196 613805350 273447359 622678793 761999270 518069144 901437600 553717745 297007498 252560220 238376676 205634906 980217386 471894237 731139763 932569566 515706340 841835542 249974106 679917526 595018907 559884071 652044912 763586371 129596771 70803207 804131194 766977236 64284280 651482434 300663515 647115870 691241626 523397172 722903750 526201869 385199074 523399887 146266678 567829640 692965108 489663705 826604498 806055431 446312389 77790083 950554929 684103699 610415993 799536771 362177753 753010285 681282371 153986108 421321667 534687731 443451162 698181031 937983264 961562431 414805062 788471766 455141979 329820869 913515675 577417916 452342044 258327269 46541488 207944762 542195104 656274258 439696348 706063590 265571834 836535448 754931861 976498605 113842646 140503687 449736183 674671036 992417545 747825375 508634675 73373993 205592386 994724425 796362651 170006074 856834860 97548061 147546215 265139736 579809561 141460777 81891244 808700929 258336679 763117147 763723029 117759780 883129130 324466912 922719721 698596811 165901532 388683058 981156597 718048798 41266062 847535105 403357363 535449983 416700214 972421745 477146867 211210165 206490459 404336808 70128882 29380971 331240942 373310818 89937162 99000536 434631032 839064589 667837484 860827922 235068607 931187637 16127094 987492318 885103478 138106016 542032218 881750809 385548948 568608129 510195297 125977519 824920188 266629467 381962583 924902475 605073526 738278489 766021287 918702268 630095376 241858214 429131521 886247548 722372078 508701344 822411952 875561033 843529932 871829031 955053546 725410666 480753753 162630006 380765790 86184340 581450189 980834460 588765545 322737724 121423634 795289782 335837994 569234853 622640869 407305438 3283600 725163201 553740392 351322082 44651624 940748292 109403017 232345928 976022946 46028614 247001596 255362425 689407525 714863723 770649810 854768208 941231396 520954645 69951039 690271299 220910491 823119441 90371724 783566803 516642340 42452048 197851781 372467687 558181774 752251460 507634318 994087112 977379576 612472905 530996116 205453701 318591586 835133454 969323141 677831592 88021753 103679818 964348467 909035250 738079027 42403858 316747360 281731030 812407666 512485883 591593409 730628241 646429095 599142473 22425223 954633534 669875813 897438701 435898656 854009260 649846045 709282457 530757768 722004683 179541254 184921711 973425311 818489168 170554314 6107048 88068422 293421109 769018037 60541282 992020252 530219223 552639714 5510864 652735284 229003048 844010995 153854812 288917678 116518398 560652608 724080782 498116988 459968138 39765676 887100707 787539236 210287030 891002741 825665076 531610071 891624765 192551660 624579547 652865391 767843898 215088382 10852672 612831003 882117787 850348694 455904942 971114993 27339287 167751366 22360612 446718408 574120723 435660172 971438491 361956227 775892966 319968648 128980386 39508057 217243697 597721453 343846127 847564014 120459395 259621416 218546776 631058516 383169053 346823812 784738068 348593624 901732658 42644976 761613730 89967097 440421524 948643624 515992281 597865241 21928921 450399675 156778121 302744534 668995540 193521692 719943104 18780925 104804902 116932332 816204802 578447481 916820795 650995600 572221608 424537299 896302539 806271707 937293670 211634499 763111489 434950839 234493889 230314977 878007334 275638982 804078941 319193279 950976683 274005735 108216066 911432687 546564169 835660306 415446077 699345321 677079437 484489584 256286247 565355885 442160875 111235887 181230939 820979880 706406695 8429369 689587039 255454936 678938631 79489718 451743458 594681876 641236660 969638556 936488698 206986313 313049133 449683253 791517028 838563297 601703383 868501912 405423569 871070687 804022469 615509590 365945069 690604655 655255703 655285097 619834459 392790136 25405860 47584449 310935146 282620666 129847658 426178842 575032553 665095754 236968703 951914357 678831368 513329378 357131694 760239497 247561316 159941165 14986973 493437833 19428729 199939606 61560666 355900783 60467087 181744179 654806915 616146387 847606378 955943601 496522400 588004152 598057374 621094577 961460869 286900034 915129781 142030870 86444116 37451698 80599383 741092504 597409728 236237965 152434283 820181338 934541693 143378918 679430311 211982874 51488747 27113903 656234390 402276898 709821758 22998746 465901725 773634547 807347690 378191079 444182132 464200579 590536954 831272014 188869630 731673320 993055797 618573500 457925732 773970777 585157672 796444595 591936880 406201993 907266026 432148072 111564411 148733872 443671670 893479719 910231867 286859784 372032391 707612459 152566774 335086150 37436233 290485519 631887242 386633882 594660741 370617876 733288075 443216567 780199757 906408416 255921753 322059776 887128127 211726526 966676215 6646950 488560519 285909041 720597614 693791570 611422695 689557297 347738709 891868355 702615124 846730853 558957645 669467061 556847437 548988570 324653992 909331648 214486688 512597889 349968275 493963120 762724051 345767324 653690014 145772680 259909352 755395282 675625322 476822681 597882970 314285510 301978638 822324192 914058469 677082724 978246711 121033725 256222477 108195360 14277148 429252540 307434480 591374819 30245044 776130282 893871110 524002529 111422368 537669220 966790034 463923012 429000641 667794012 65953615 396688674 490385827 909774311 51757583 350098513 473866694 447564276 373135381 630615347 613727194 309483015 692927363 970535303 831383588 844151556 166330656 611242359 239674244 882779800 663216477 602598525 348902803 500540277 814863178 999623390 100538897 722288789 24031030 823289745 65770099 475358319 659417577 57341238 684235452 199389253 614448170 622264008 600645118 99255261 793887021 575516551 797231813 225009870 630122574 154142134 618297947 231568946 311320468 291190616 44296207 474816892 228447110 27601653 262640327 810869 455004256 937106654 601318425 164087794 288429785 439570245 209238037 918093341 708881117 23958082 145405480 350293987 543397658 463281676 607287549 552376472 792585655 75881706 379621398 108819459 964356899 134984685 196607386 591162513 316381215 109288632 299017310 364377066 608087275 180692856 247196583 174310829 336761802 46828405 578457962 687672265 716282542 59965643 751480043 33360518 452143960 753779052 297939849 914268060 492069841 189941273 163406244 63779809 258281369 894356989 827724403 961689436 321565830 981324165 227436741 23421166 62321081 737874601 676907359 128416882 359189871 543131650 746131170 35082541 398786284 145048169 888600192 98058096 677837284 645159587 179623568 906924969 404479818 394683539 949791027 399218049 963944049 890118046 666466211 774398776 653142625 383800888 955218330 968391873 813016705 188931354 532370783 133343883 885027934 943430046 286569673 105002759 859877423 970753490 573799968 488000816 50031579 893755943 667531454 959752869 141923185 217262091 967253494 862251364 228616082 839923124 115803883 273824889 655091885 598665812 701643845 671250174 421439380 753187704 443091432 190326642 673605633 996055082 640152494 62640906 768278429 870315765 290071097 535043932 732926854 679581149 346821514 126700873 941907471 130671959 437875269 380043913 218656881 105446125 648784646 804135830 912195878 926679958 956519677 264911118 338825648 502552831 541875548 311758249 493319100 377356182 76411030 545448733 29406433 339813374 264103414 239050149 289647017 721697515 971979254 259923642 775628619 121550770 838366709 610011669 181870660 628186418 457012154 986407019 983290352 109735586 714071081 430617505 719277755 762335912 91280450 970248379 659028940 243086060 414229770 821306717 828670040 947237612 629684843 701319574 745181578 242874398 504121310 597135443 156423713 84091912 41021532 667464368 822860807 729012926 485028270 694079759 896743986 857268701 233658301 52534337 4721225 925634828 199527463 302869624 902872638 863924851 339872527 565340118 318937302 972927165 410935433 686214200 745555144 537087034 527869978 174125801 891186029 718312728 71053448 301111846 9747315 735922124 585876771 567242926 121204507 885645593 375006177 179410452 707669404 210272478 260177522 925512248 431068903 334921091 108333370 169838980 235936589 911638935 670913111 946935940 346181755 484984466 869953179 419381386 434139309 245248816 323376055 90002699 273121974 546072556 594503268 439269236 155976298 22130738 843289606 279503821 984415787 223053945 34250513 9830714 379738538 967154276 48846784 686917905 661670435 636950672 748207425 465980265 269370130 26737218 743477755 547520588 155368586 152909351 774549614 190501886 647823689 713183016 721738658 664665873 125360707 452457060 74971613 952893580 346638390 155473454 220711072 714652227 24473073 379271147 652801451 920904401 463708029 551200072 634205371 143626527 796939834 928057008 677979081 684579126 456078250 155609397 546417915 942594831 770533036 967276156 467373983 385514567 705969590 251477132 14924196 228885571 157381741 992369194 995840279 219658069 309106954 44472257 566256479 693208620 708783885 512234452 375478216 218588852 112409022 764816060 45587530 984476042 103045889 255372992 933266102 791161014 680535180 582221076 560143739 513553880 48549385 827223295 830216464 91925 263045321 278297726 280347791 957565047 406448255 236108844 359766825 303046692 58350716 602484163 86090357 203961565 367797560 471155723 105717231 109922441 214016052 485604183 373155514 693304545 260556669 716718257 835245206 360769853 739886829 685760387 467130848 893569934 52918167 367816333 854767080 140432206 693072618 457438780 533980476 629923194 904161833 293743002 809239565 493128399 350573816 569440473 16762114 753656349 253027669 374625149 618335010 720790296 420530317 435540273 287682940 321986752 433712159 769008095 804754924 606409742 879639365 769678742 979522735 432795288 455517847 596815716 808753150 879812313 30079296 469253945 823633979 106208858 686349589 111218895 641648336 641836607 395396265 610353902 914089177 789142836 651877753 396123373 876939358 632800959 654681175 872436830 448698372 737314055 989522558 202527307 659386019 309970989 584659138 764783514 471479720 252330223 110473724 421527030 43613341 126150686 245944716 325433960 776398895 781939914 700103619 149842626 332347424 762007573 238601026 38329291 28859357 865242180 890990358 235288412 54808553 210892739 93651739 255539223 892980161 219307071 108275508 207967943 568330271 472163331 208327020 159691824 176014231 824475028 60037116 450224543 849121207 16606901 201295490 145807152 341624545 919905117 509506547 18013112 277616950 206152955 845527581 413285686 535595352 33576828 512404671 438579908 562426013 948111716 163085555 571366094 986070347 325722776 892690707 183366936 219606510 11265863 957746462 647852345 880263325 760465624 381573548 531890695 762351131 42860938 300135747 450863761 396021077 278155431 403904794 125262084 934229616 221853693 845251387 555353697 554442017 892830894 396948716 732416229 204588322 866030370 196886874 855472689 205313931 136519013 848489461 433451248 497738266 331927935 156705000 143853929 437599540 246978511 240335436 794656546 59645883 415624149 495651080 616076599 343985252 621080630 952374868 948638300 917210612 615145616 984936948 742934760 280442897 741623404 453585808 819641572 387188980 153871858 249634653 970793143 265394310 875265821 454599384 700625837 9482714 470644144 895040994 232798671 200495136 667979194 673114261 637750102 457827778 462279146 93587799 194523759 731596143 922999303 456880856 127823104 620370963 593301739 133999296 188889857 219322699 169715201 280981925 768437303 437528635 60595796 41499955 44573090 102882895 490568804 946856782 452083660 882922991 456050181 706485511 702183146 934863573 611460638 31500921 115432823 926696001 124590258 216362308 981948224 715508704 320825424 12616485 214693304 332490247 174767162 979908074 61795945 90776153 503001290 482594249 55541174 285386375 489005605 689301885 775927146 891183081 188686049 125490599 731809882 819968123 182692029 582125204 717707847 462459051 770744073 570304764 888334669 18462531 738803610 719699027 606347619 509122250 247077715 234703026 843041419 733744761 170767291 847650423 843974598 223742269 157301663 233936096 642073981 550353802 159079359 318677621 233159938 890813759 132818924 294001157 149250172 495558820 649499371 561920402 571425551 842786896 603506970 997280838 666199974 745210401 245781827 895105625 725567967 562327256 628233212 76635433 875984117 743867712 878666146 839597125 705851994 999262078 393008861 616968222 734474408 823077828 255328096 485854086 939361569 906747690 423423680 196183057 284616272 477665348 416945884 176079070 721505277 582060976 225068958 441614349 708955838 145799612 634165955 31748396 827551548 519589249 523164653 453488380 188952527 348904452 674825244 139092435 262447260 178695875 387883780 577121206 781828114 560130775 646717878 750242568 526016132 107067840 398429649 760067593 184976388 80897083 368783311 483392524 799029878 244921859 655123043 465126650 507855464 241642474 499062002 599010742 604358668 934227827 620890028 111566946 747356083 864000620 200150901 822292183 267714063 925268164 309650342 957434411 506898265 398528022 146507 658849436 972455829 291043536 57610984 478423593 684678676 330659137 769971626 359452983 219075726 238466936 445803339 980745688 561254738 632238761 105644139 167676571 81866471 25137568 413056663 648083976 345074558 644349893 121494492 14681396 205840377 879305765 475989881 418237683 71496413 200190938 47868583 608504902 855453392 501583810 174353330 536506038 866408620 336967540 566772667 489505651 23078426 154381453 188788554 226668603 866951627 302320760 974385910 504348005 129579684 419472188 64462630 424653761 583465528 809491245 555997328 914980998 758713872 13289705 326744181 174982295 84441836 611215745 675662471 859394072 665245249 332591493 397126314 346442351 325208297 667001964 363511670 509547363 193072944 639166800 826719519 799298792 521349242 15802403 954635516 10273967 161279432 273422265 931359559 548465071 464024079 372720315 244070638 715422405 429934460 164372328 369875756 274043133 571616581 798792095 699688728 449422856 986906478 977074130 553903091 641165839 743211246 68911854 106472802 519913871 597561146 4619102 378812851 244749315 230713454 169863463 821257173 258253859 780348959 835794624 980181333 247036585 890531972 341385173 808617415 8602773 257261712 118253952 455590937 418251574 884311299 693181640 522149388 686481634 926271350 167725897 166716328 258489919 863314643 862693197 292259150 208240992 377549575 925840049 830751021 194452140 504104093 210386136 76679190 40309038 791908005 147569644 980835474 523325582 96816211 905183846 723138694 939458485 683147551 74176777 986820106 473530812 113019141 219754189 199606800 293591496 636659736 325071987 347043266 419215509 434141398 643315738 446585128 140949466 946038900 521747023 244560964 165418139 79223431 161862888 692682501 176056864 871718936 705808745 532216159 485521305 656446420 865900182 637464823 577665026 898805104 412504235 932991406 598425078 598002694 302759729 71191449 368647468 382864814 615134596 877463565 777018759 704448445 588696612 483660203 657758223 327165890 583249852 864086318 312631183 668674376 676807260 678690375 282909924 111787296 997106950 516868843 955748186 417447361 922107069 62689903 748979175 922113636 315990195 347585582 386065865 523273511 24330097 79135215 173755904 731020301 569285873 544846921 862476621 902745128 961775474 23615606 261475908 20078884 104281559 688866554 423167675 51703826 450006016 148432450 949372619 451612583 130560370 641731550 33964428 339133231 179502340 265248041 848474806 166536601 379373483 622018515 239560580 436810777 750002786 358510192 591004328 183667561 224873467 664113122 787912420 163397430 768482000 344439355 383965658 203529223 883657694 559334338 328538004 54706492 268735722 313386702 515814594 192537358 977756397 342042086 768509948 355740336 704055661 476689241 658721999 452148476 946720938 68012258 179591417 610910663 970220058 281000138 86540557 438663535 167505019 465203564 329573347 744505994 59546524 31943810 484989339 894188942 366356869 696120639 819650646 640048461 558778134 397179791 915548472 358669708 427594997 683194268 756214622 328520657 810910267 135435230 936195986 70662120 173968455 675212423 544959231 826311657 599410786 977651691 255517509 177381205 657776450 397605019 445948189 952016503 794885003 529732897 474015341 575331211 867402220 994167005 696183088 538978869 888296483 593719904 580797864 167926250 609002907 769098558 116154762 800437418 801432030 756300692 362051041 778530308 821271938 997730200 629730228 276447584 246297023 695610335 786118443 49974467 808144894 206001369 80842276 985471526 447585543 341094995 33607132 246040788 888574788 586755912 331082460 55076704 407043516 801361864 93275497 762847518 785279296 81367078 91071161 554417074 281562720 749869721 600080550 243388556 157098376 214115176 439897670 658636339 831596463 527704220 759643321 678533539 836706529 251779347 327496753 83555784 611208453 187949387 540792125 665844208 477953547 353116711 128451333 566035055 345843963 494515303 168358882 112366177 2814238 116459013 111889688 752903440 236690094 934076622 870330593 636936552 888340673 306674680 245129740 631061688 412488984 808890747 760636240 618781353 645674083 762613191 204733513 125065437 380829983 373712597 579175616 677007212 692194872 438108681 907678186 726998245 493956177 351673037 984154358 816747483 201684270 214981832 477801498 954736223 465055995 488881045 934125255 58661581 906130956 979013541 193935514 841535395 427423085 614562259 157254198 297726596 373589675 89660495 893799230 98305012 463634453 709092284 399747554 614491421 16663875 431671428 802658751 805400808 642641351 621592669 411436984 811341877 576552179 114791593 54275088 830760333 155218306 813900858 629312327 435251534 209880024 892918715 226984766 856134848 691396593 590084725 312793794 777841066 508936278 418523185 176251579 969717434 665069135 654887710 46036489 534632340 196644714 899754041 267086791 266374977 8933313 665823482 114565455 283258520 787108622 273888638 487343718 484718557 544208994 803090409 284150754 723740316 855907069 615545044 198834571 711152133 627608816 40928416 644582359 343461388 72977341 414928752 274467572 177679667 57181083 735757176 818677268 329749902 344740862 250395773 385398574 539292139 481924758 784136605 414307360 758820751 432284751 670297318 87822358 687136975 769977855 936634802 740083027 204754277 460124389 212348460 828431439 683128471 911902477 368582024 723163204 328269617 908145173 52023571 347598836 906582304 633196034 899082456 573852336 936828663 438296081 641337851 144775286 201331043 574557129 803268877 395117492 394874481 560617655 367012216 803404011 37011693 74771381 362441344 201532781 485717728 896509833 777388496 622503434 878288452 304511724 262124693 326541942 567055606 144990576 590759458 688911478 264092086 598171886 88005276 193974255 670568129 514878529 748225715 50246290 209155122 880779910 810241609 387119364 887777129 587081723 523880416 828197287 202231991 402398772 706811383 68011940 769498296 38396929 471712395 71321371 555509549 527499118 869669339 786322220 354963040 499838245 777027765 204834489 607386639 140816390 136824673 814836375 976850175 100731058 982002221 178520303 836094455 905393583 764415761 260575578 14332645 116575181 389065562 623300342 641408199 447075071 886806551 962719410 824873944 889584510 964628898 922630567 515488816 356218243 441311223 255773114 484013364 945386494 741460935 96258070 450252507 249588278 902186255 906313639 898145337 800895954 720325817 214765607 683625621 319365585 17958546 860515355 969337252 79370173 55221993 10392216 151417616 167115016 458064508 255195860 689870021 862739660 715317531 667026615 760493536 690530013 639734065 106517124 954951170 806699987 401596328 355539667 456273297 681225002 448483484 403022726 634527422 132651719 262458428 488816714 139474908 744966615 132920390 92097158 629565541 728870896 69332015 964415865 851604872 90413023 814067067 39768807 227544185 451904002 76493611 760995089 749902406 232726932 618385623 761886450 466359911 784359961 877153762 887680502 187083447 799585907 602644115 801634307 23655655 287917064 210309622 382042662 842171062 692077321 568885163 766418171 288152493 393338727 533691656 860963076 616885977 569669399 383486448 636116635 234912834 32942529 611381360 719466878 632253709 658020169 461672933 859149566 210366323 294563587 364174871 240883953 181713169 915841991 16251397 777376067 338513212 260850227 370978951 237255047 624646737 891794203 318151790 15917684 997185857 580382021 847199151 366206414 335245068 43517248 823762751 968464178 449741345 2898131 850150590 930791694 620268617 589112861 103827683 314896179 990878850 821380389 992673314 180340798 657165311 356972168 989261213 293815397 793242499 532978368 119719453 376755822 26526581 365457583 495180908 795904596 5212514 771587592 925682754 814668819 379608631 585696750 484655780 822507464 473144840 760936720 912049013 345950633 331113577 50396965 690260606 512608300 636197627 287277543 352435377 152697673 263557636 637385459 950930849 721871643 977921606 267216072 873754060 23023034 356736673 252401449 190502454 45886865 637053082 7285086 493067399 247053800 784546830 635379980 285102348 300722643 463717960 224346931 561930498 378552489 374993775 288556811 827704888 928137506 152436807 744077324 857987040 467673398 363361820 517539784 445197517 453541835 592042049 66958233 399006134 99254424 994529398 284311931 911878321 973439529 2462064 160448512 868276189 522338700 698175229 496596265 583243479 852097916 770360647 944656369 998398275 322306938 999863871 89113855 741584278 542454480 328995129 703048626 693287823 488916715 662832045 943834853 157425489 391831368 165921616 247458636 211992001 991419148 964144626 136758695 118733775 688022445 670916572 913763524 401286248 118123195 479082974 692917682 52639635 723643953 89465799 570601684 171314358 948871787 767272066 10411767 991485283 556934577 493911208 621618084 379026936 411419118 186914947 249149104 685646398 332135483 506730448 706925000 84685332 184324756 737348463 16772599 888676064 580084824 279496842 290541655 973462531 853359036 835310799 953068987 89231129 2593855 575520696 240183357 727899616 11126956 977996023 353791358 745559215 666839202 769194818 613583197 813493577 403921955 302264375 496394960 258704526 96583664 634436305 195731045 311079696 628979613 840982221 345843522 40874673 216538042 351693823 128406783 679841111 528674469 177519867 24379991 106944636 972357993 141014656 238339459 448021194 37572475 312228504 137229983 852526391 385511674 265800960 266290742 954064147 305697274 789413462 586314001 730705308 649072373 174338537 978642903 339387402 65036885 427175176 507008880 332849131 66055554 152211637 61721 899321341 872530646 989085931 854811083 941168262 849912062 319714136 726746557 323899206 98149842 854616422 457493341 179167524 473014400 593668853 530657420 18044385 466664327 288269195 961344032 380016776 868346807 801493330 550371838 993449365 245697333 729379579 881072632 457841956 717657251 612838137 470683057 692584130 527172685 808562142 384525303 705978787 595487884 246263628 968141250 451051984 450562894 873419396 724497920 452269025 567188482 329073246 224215353 520974890 223392613 756815332 943118982 166071013 833460146 550506394 975349373 192429068 447736495 4992204 399032974 144961623 803513931 236041705 800614469 780035851 366477163 976493320 272335511 776327044 653826174 767205924 905325 716534180 239840110 477743259 811303182 760750412 732429225 382215239 57442080 708110093 438161886 399667502 895733760 12216003 786429898 985849841 278042384 672123088 458470500 780849116 997288944 626608213 355159426 238190194 225109751 301809849 293828467 137822590 625768219 445271820 467639643 945318524 454565280 91970948 209194085 590735700 118583926 80227216 227157879 582493471 190535965 929468340 854058110 556345165 749445848 849776913 685641944 165031165 196249747 164269095 249213311 812966674 952394114 597681696 809869781 201893667 189933455 826289866 516673541 230887895 27892159 73797593 293311703 624714794 425037213 535378170 287479221 864636064 158884714 567911032 54356047 7109895 999091108 504766380 467070862 13041765 452182096 216633335 821129348 356271114 956048613 347507694 679515854 259866671 470997783 523043534 279060110 704049358 574108563 508177770 566831056 865051392 451604750 990399248 590409729 51856816 833903135 161961186 648136812 283016271 864124909 518662665 157562171 92306503 41258230 174157414 41225950 368900152 891283772 154911775 394068432 217501039 72836905 721748722 476007805 497362544 928966786 247665169 524502353 247456014 373744039 78786686 77155165 263711701 952690360 466632700 315519712 956214860 723792760 192484634 751719187 85767141 665214600 128595859 904098390 991381124 407694613 787266102 636677629 575823926 518189232 243516014 819106804 173067306 903933098 104315955 584511384 715619510 944159698 812245260 646248824 415958979 920555676 662126418 91290487 488506918 829211891 279338021 779218639 546087914 381705848 915697927 445212266 332577085 104335360 680539970 323918569 598405715 916750716 474144819 446651684 290760965 2494868 9987282 648685440 483251994 232453967 822628811 289342787 1127745 28076397 505332629 851673507 181534832 976881501 229009999 806463209 895938818 470931646 20243664 235658747 319352457 416180788 128414642 36742822 231846561 69189899 521678726 518707047 867475125 454817855 295761515 638293851 27166932 315858531 349533697 520438110 435908905 661180126 868741663 844618679 212650517 555733999 817457029 132726242 44282340 927952115 738411140 790734797 966529345 909921985 691559876 568515418 346405418 792690776 107244535 339417631 277588631 718750269 867665377 929687954 892336613 801289061 48794242 122903739 760986835 127287271 630786455 199802445 397975196 186601503 994879729 347597155 360888608 200708025 849105514 799305129 180145995 150596644 278691832 323436778 355401871 483414855 286182747 339391557 888842138 205763733 294540745 31400217 533993462 243215712 176115379 756527152 585956159 929145522 923573499 707967468 126129082 567416546 530108202 136455712 970992367 287703906 836616386 764270571 915186253 678673757 26445003 996644964 773118883 392053489 528731244 74000387 548884982 337894819 47082705 744695167 527620480 901786781 514089423 327603630 333248168 492106731 630715485 927453069 966871895 355647186 176096789 716660902 297564868 237193065 816327899 983902734 20518998 421458518 445598026 714018954 831558088 576989676 43396655 959258722 770690022 81652836 365767924 641665756 118235726 602812165 946019506 722854271 811618807 126004599 183981329 193685025 827771359 930455835 224094562 237590058 173514674 257021048 237805295 971713013 955295734 365388571 345888809 209177990 943565717 976204922 411641651 3635874 140809356 301930833 35171990 28702173 980931651 810948862 908824118 360429602 133864847 460294414 500274247 229806576 207934616 9614668 313446217 58801435 450009455 4069065 261691302 315416645 402137565 39883079 303466795 363284197 681721074 277578521 826966346 92264217 670511540 243352376 350273905 44017019 308911260 286561456 941857603 700462522 410391531 425643480 493141809 686010448 498683214 134939634 284679102 417952457 185056901 973311170 782115650 252133367 994693358 714211648 342959526 742009655 803270429 745968030 909179671 515131147 574971304 486898507 954707865 970611444 281180558 744582975 626880567 163364676 868423633 340302069 216848492 301684985 415105911 872622551 333481667 89087437 402480666 910415281 601880977 682644791 61983941 471861537 561600788 649100136 573167236 371699312 477605343 405122405 367146338 33694413 924917801 579966547 778518109 106012727 610370485 546524408 824323884 897000654 59558066 495529364 454774623 224563417 322721164 399795007 122971712 281864626 387529973 914609343 319760877 153922981 551160332 176843094 505653310 692244529 733070784 905981265 994703972 292495345 198492405 152561529 904882031 671313651 202428045 978171268 507276711 792676013 418164051 420572768 282829723 572762622 318207705 250739072 413714200 699352102 453486324 323082066 187325875 42207881 406777834 36126732 249222516 348185158 83418319 55328715 511220738 11224699 367557834 198230957 952676399 783724879 457632599 952895681 858123157 617547599 442405124 529360935 702862890 888183760 659515358 24143913 811927733 228726165 757397820 178404024 721671890 496412871 819498615 180148207 530771641 557962596 552318188 890897926 144997997 168096866 99237260 268649440 559244062 984933072 389564493 717579665 648458625 860522279 538987856 960473516 930882718 600441261 626947963 554144305 442913815 194338200 70545280 294885168 57757105 749305044 251659007 361751362 25391065 326108890 266778244 17122996 522773650 918597311 268234042 319462875 171765312 943700798 644601753 558754206 729321140 102496535 534773512 544399701 51228341 16430357 840080726 791740195 195962447 364170987 915532146 164514524 330108410 262037261 84388031 843875694 844745768 542107282 150512523 223686608 323103691 809587898 477731473 415019821 115832486 471948526 661748206 86155980 912545630 830247859 39838649 294348812 529817348 582758088 167348915 131123947 41478271 896877402 588955821 907352996 179441586 396138541 804994503 462925120 783829483 134706155 126018164 467264444 850352100 746338717 91130734 760589988 747937471 207320670 446596990 421824031 288437021 250757504 397771475 9100201 857807178 802162683 295336851 225284966 98979705 807559389 682368855 321298803 22483208 734269360 491355311 579024231 619759651 554074798 221692614 416644325 464971511 114834420 156500930 175583456 290273519 81563606 286186058 900761677 856946379 760351929 107746925 456262217 637710303 502959726 400535128 616180498 220060028 822326815 951130524 2989760 229287510 60511122 403468946 910916589 874624908 900148661 584302998 84376260 637445132 768403765 431536215 555898840 151972055 583424800 654768403 243858380 80175074 632054177 808242460 822234550 242043979 636921526 365602841 429368631 826490068 6349532 70690017 993272014 553334003 316047239 456062679 696976087 514478987 960513824 890824490 111284052 814213494 688175582 517322242 526697146 467250741 475380556 501990396 721301876 594472909 864129583 240110890 685493216 22241182 984192150 506220669 470133180 188413675 118935414 199184949 869155241 163724051 214266876 220485461 132009234 161601049 430684612 809522904 122128983 997705051 531028416 186027037 140081291 714891765 23759059 465903815 592721831 874865852 384922075 770273517 925682539 688160881 7260838 347357260 103195612 349233862 109050729 625798099 628256993 360439294 528092480 334920366 321704358 999439849 440035931 248377290 704083424 866648266 976915099 386765483 992943438 229056836 178022054 441136412 248507489 599452710 958337830 228659067 159620369 100531486 696685862 147107586 224313305 648975969 73843020 580405807 288150693 884354316 91674604 454268399 954695640 810407944 42590079 979247987 223755999 712750359 375600096 299366366 449587344 100765847 341243578 899837047 398042556 26246518 121172578 576013403 768931745 915773970 814483334 37273297 586377358 462630973 696185646 120916416 954984966 688332787 70211517 516540676 739007509 295120968 786776787 757105299 882640325 997862626 467866804 862509535 662933832 79423169 36363308 554679125 7620028 473384627 81811971 976988236 769537763 215665382 246011207 632463556 395715203 734321782 772539560 533684622 505835674 365354877 281987367 355017233 187195496 570246293 169379318 59455428 191744040 982540935 161542853 327989176 339679979 320742195 424119411 537091404 81112019 287254474 37235287 264371496 722684829 711056078 694772886 680415962 137487309 569180928 63590847 797163423 692076666 656989721 445158922 356174166 679747015 652877182 162614228 864885264 963414717 574054196 781122498 541030524 134884003 669499431 991637761 42187231 468715193 797480648 706797902 536172278 801409393 367114158 195422913 747076396 341016656 736095142 831057815 805599542 394064774 603128944 234657073 231265652 91503407 593254221 845693138 34498359 334567787 925003144 990419951 364216419 188518998 410459962 67334895 186876114 374955107 993148045 108953363 865245268 570342216 361305343 701497383 911621605 476534003 461590556 10027573 618285647 635761314 267933289 795891115 717160639 837178649 116108538 318966528 339765969 399549032 467530831 473960389 518749400 806128215 509166640 365221606 625258156 970649699 503820506 13861579 985284428 296009469 513593692 101450706 444403991 272978700 82862930 74888688 471937261 543469954 621507111 491501026 37839145 566378573 181368347 552164232 769757705 800228264 296764211 141567832 70029679 310636846 518574476 373359287 206544006 295060228 748183915 297641023 323156755 287628538 189834990 397752273 633824659 536845311 438992133 610840685 704627971 877460672 532759750 904774582 427082077 165418610 74039086 775722335 678117831 119224676 639352833 902969598 822339713 764451397 174412465 299425177 327332545 717953810 887336952 806434131 114108181 44348843 884497600 996478778 284609191 958836195 530871586 300298770 257071440 106069314 782198485 500655226 108003030 8135815 756168757 896001893 934147215 142423819 445185181 277493855 144557414 401183389 123044495 919091104 549299281 257625799 754102700 676394127 666619282 885880640 301538011 761007133 557231032 866770160 990340595 824717126 868654156 415867154 757785143 624523817 562588783 821893460 611733986 377097369 598563297 101689159 660662640 793609801 389476316 252919123 969488641 187509117 32068085 305246228 407871403 75378857 705511596 627913798 903205404 798885867 574565097 20346582 118295473 308723648 219492202 303441689 968279845 357427952 610075313 937002146 626307044 416061138 50743022 694966359 114145200 156488115 989458310 10134178 534662068 744156515 29928160 793954051 741222753 898566899 301314841 68750409 44417864 886818052 636416377 356614406 905279075 105699416 79040195 229633752 338208465 558430109 861341900 912110470 690211744 522159230 162968117 316629588 505322575 409953619 980304783 507836174 434424147 633406323 237298874 725079945 950387912 503296846 821041397 583219443 222134055 143634418 928023408 3638261 610733605 491539823 187295886 773147497 811146010 937197086 43275146 41029549 809134872 889301246 777306419 684452834 899288124 318082671 177706022 863736804 38778210 44317802 737195995 779854084 162664711 225092150 91289540 282637234 855887232 639804229 838960365 17258078 985229664 365314026 809977929 86386882 604278800 582139930 686155600 476218197 983274022 170203685 12268517 211037286 212312299 332979985 90863720 498358829 560806564 410934040 434744716 556982999 963826108 694949843 504216894 956614357 331875439 544744815 119486011 188996578 492487196 691797781 889599349 879702665 300648734 978157610 957419675 894916989 813525581 711367482 313704786 164167659 224491166 780280705 976830548 225721104 846470327 758572301 903422516 676782810 349028487 489964348 379263908 193333355 20019051 648127003 404455437 496402146 375793624 829183235 36750617 471883958 140246940 889877338 850685125 273738825 710166672 11416520 521224238 283138507 932504562 849418208 229771096 134982847 874457160 198969043 518353523 114843178 803718695 841809060 128784203 978828982 842213972 64145432 519475496 45127255 638837480 422024836 672325900 591944667 744268333 542489199 351744747 744009321 908777909 635500394 898821029 35959940 132405899 408638096 306402630 351118959 249269450 942319267 177675968 807301102 935626365 587746840 349779322 937516026 831507661 279388768 826871026 468067023 212874340 225086253 459781422 416931054 325834964 846058365 609844251 394435298 656090043 807156334 352447701 998458931 342712407 401433016 884866604 40518804 883582384 436513839 512100994 878650788 298092498 671244970 271917690 708503173 870496024 526583242 322496508 602545487 290080502 217549424 954162332 78826040 969549425 834673458 489997671 845169056 363197145 153389595 37190554 339954849 194510167 889035369 996046899 911947545 477615416 630700509 431469367 690054931 957722561 468120303 914402690 952122995 218766775 452971068 278596148 959598583 109064260 28969868 69100525 685795900 834423034 796922763 715583867 173882471 944185712 836654998 832642158 276209942 431289165 290746964 99748097 304805636 81770792 775370910 818056117 719369870 348387425 460895206 992710880 48932867 628777669 726370149 764180725 542123868 680505200 662853140 360826251 480320753 256453799 36968248 816206083 893187734 900521091 373983962 667872953 698921577 860856386 28181618 45702682 310872043 933036518 580300853 571466273 216637760 27591186 81054356 416753366 605057480 437390244 503789671 182198590 732373041 372324838 89188659 680363873 98693403 121566575 883942075 448765345 268370708 27268233 592209136 795914600 58207679 794867427 531432852 921272445 798730509 236417950 190700468 221780092 762167363 920679442 766399031 135805738 321402422 655694170 836311798 587052646 565318761 424891341 178844978 113840694 914287551 252254549 701180374 878252295 494166847 870922205 675827414 906597680 529324518 656027000 721667976 333178821 519546411 725044961 452141836 472022191 263425883 356817396 215856886 868059528 705902059 187196354 271831580 452356249 79703106 320695328 200287077 647465728 374138427 972229393 152880753 348681091 575108811 517648655 765383389 661257726 403658220 994190234 822653204 99102937 257469434 4684111 351475355 60410323 926293276 154856318 254729608 971899874 606880902 72079711 389233946 113760061 837784635 521159736 709778406 389052713 297368171 904792176 975071816 733356341 718800603 835943582 30032490 90073934 617327679 118230939 840620106 609509775 700119373 229839255 411140501 188342475 401702292 904878179 119986741 685388829 446756116 467907097 54758560 237996961 389743230 839079403 779768186 433877589 541077774 328345033 673004721 883453645 814552525 389765440 950373970 257562087 595545581 145775331 111982726 945449106 254441917 406466926 402606085 195492888 431097407 430811330 337851499 524546175 742495136 460171452 695795268 90281384 44991016 25915515 437307965 82466325 832252269 16502817 730938730 70666052 339366374 424279701 116975192 896792496 207087177 57984523 353523231 424530800 487441548 623948541 121206194 440032005 225003828 638440785 226875374 276962663 418798975 406800667 606933576 501036846 841280593 939647382 82378495 512961398 487679068 839954997 928046452 24002672 474501789 52658477 142449647 303624543 646940900 511239085 954597351 956746351 322198405 934159499 346605438 93967608 115516048 562938555 52288594 8275338 1600655 456846643 947449626 918973500 427712546 251976523 631700314 428802973 334041756 602026022 277102839 770846511 934041738 920603363 60931536 592792094 824716713 31697422 748921052 721223162 401854756 613768998 16934427 776799351 281144780 234564980 918841841 650623568 498858647 39083632 562142613 190847148 349363382 447837299 678942750 16992775 428054060 470397398 722081314 355890074 216814409 817252004 251961072 173868519 375339009 614843343 307859979 734224321 55546402 494788057 40509399 525079296 2727667 137766924 489984015 116659741 413106621 776923880 950466459 763716030 578936375 660370474 833389920 444232630 525644789 58869785 476740478 823556643 684083364 140463895 227916935 440101581 96073183 118870124 780142638 344158443 945762411 787497562 629013964 747716693 516594514 61359385 732023885 185154779 227346584 54820916 47897921 585317125 897644200 492075443 547860206 984385225 933413215 550283048 122422646 798772502 483250452 207141533 778004230 793089571 227188476 119980782 251746402 200167920 918618620 732556186 322305373 541940000 504848165 996651595 7304889 333706386 388722197 140076193 879847406 649076321 766923454 243675156 941160841 480402748 529109777 930253845 73677854 597225262 451377997 35500175 466462290 582976635 603294084 543720140 675527250 557723475 419723262 560778363 288894248 795714295 778052634 415606591 990746146 738738272 765183937 614724967 738484802 407132300 197625197 761251671 401590101 731697811 563523579 953046955 55839972 825961478 440187458 12816466 786273885 689245531 156974201 797533699 424472015 810992491 614949472 255813545 689192147 224613173 991751943 326460195 774906957 802764100 330144177 307622915 388179 1935212 170441303 348861390 378012903 200269819 35711519 401017590 63336256 90849527 918808598 536592698 453849625 401158877 589967846 123869848 826999036 748001656 514926616 477490163 711195414 86555507 887247407 262786721 506541793 5177501 338611949 327326086 492374951 257114133 306410201 965823784 910415143 463698324 292152691 235258810 423961735 527991317 984061308 824163856 76194417 8666026 448963524 224130845 52133864 560055668 999238358 697103712 664933575 337600593 98540710 180499089 941765794 896147529 956158788 648353355 62675554 29046005 268148615 720929839 734049959 909579364 392988377 803087784 106771758 584120088 304766031 446967682 181477745 112135712 641284225 475171905 480309937 790549371 380893477 505909671 363171421 988655328 58682214 317799839 881959350 979442401 107969323 92473693 938180295 963414276 93325206 232383775 994935300 440943727 906250985 884271609 293045212 551756535 592211497 418513267 470363040 833642997 569554832 540245770 954689438 507899699 943460482 846322638 307200706 207194741 145759648 851294256 181020159 301465432 309628916 694571177 150977116 604348958 629934273 25820302 227881361 433341816 781038141 283071428 476353801 624684336 482140124 587053850 712505996 932178202 32893210 136970886 783616384 853880043 959067668 845973894 412352363 338955874 36089417 508299892 137797213 672969106 959197270 850887958 561293618 933597419 985780145 804410445 42886160 92332065 824611350 89276624 327861979 535278973 298732435 595962422 725096297 660238212 804854176 174209474 470217795 497954797 64244070 1689336 927229958 371765484 770973864 413641021 30640308 918537125 526083173 948319020 608470729 554723319 69596867 78634159 643904804 662981726 927962896 353484219 754685836 938601256 651696825 168553852 104444951 144528627 688157010 865519388 155414651 947258464 58429578 79297147 879346498 364860352 250318779 354673557 299456371 914329794 182505835 205933979 748713432 359567915 521375031 493332721 302677998 881140091 87488495 987053670 84776600 459241873 132484381 264478017 975260484 21878898 4648474 581363719 385275104 918852240 880061182 465250737 841450942 202131314 860181719 53542120 923073076 198548979 712489620 673675598 356461450 571601678 438063236 138623954 849957778 775686817 182436467 20640884 630925390 178501323 455862364 611280097 994906785 200964489 163986329 208861851 622898831 387483280 13585753 14535334 293549043 261670777 634046842 148276871 627617866 647727279 417189074 142565063 89813551 900977283 785045196 810096089 970074928 554582753 782363563 666230686 730041551 627010856 299107658 241802336 309784806 339886751 684663603 228915251 785220122 873275299 922547478 234426395 116533720 939002795 336967447 624980355 338754451 577223468 716794420 65370405 506133842 913730473 980059208 228679771 657083220 255119638 630987509 544392554 951961700 395732223 489163849 340161028 101159510 8733265 829583692 216705947 337009718 243076242 67829092 212319268 745928472 75337645 414819506 400752974 202223558 759944687 490162416 611265800 709842726 613671083 975728604 927128973 612951604 239170335 184066620 476275235 49071978 839772870 169477036 327256386 824511640 568128650 236230514 550667069 126709243 786822387 749673991 346414379 88400051 554419106 453734219 588988693 269549744 590606997 392057699 737875933 805614479 98746939 961477582 423504383 273158897 754764054 893001307 773833537 629984127 917149463 628720418 386227381 999043885 559242794 993627783 599584269 605569788 331743485 560014868 94884731 752287596 140262891 857428907 582026191 949817930 534338940 472601265 439020720 321842011 217935501 887602941 848225202 299360706 904562692 586943079 506823572 827152601 141646548 359114774 838371298 326996998 936450633 661853499 144144485 415407598 162893119 209450103 847269518 175515793 760427960 904245674 111115906 31881791 189256529 391714660 277320884 846099370 905881486 465722807 634708674 4877 115627331 764666969 123972333 336539778 616584120 794166028 841551120 688970905 221451969 306861057 905683225 331657610 135378083 934985196 435127567 855106680 194568571 112082883 360299696 902789743 176727723 246402636 911147863 308063167 971107946 235742448 588820303 177405724 402615354 13554383 536053427 672709264 423789698 29842960 223065861 349755877 299513421 844948012 97221619 240805694 849222749 981391267 724576588 164032144 659694652 211945360 303391691 148283201 516977352 272515915 110124875 220069115 452722554 374089905 501691996 789931825 84048715 288134942 282979014 611037595 534901414 512218436 472081910 70676984 76356528 875111937 693598995 234386422 542985168 129663182 890169549 213807423 220470672 123314254 774353605 675713045 5016850 497361989 193562192 256398861 84285997 944019978 896701432 744049037 630660896 366287281 99714823 207949400 312890702 323335830 318722757 39713644 123608281 590513740 226207784 703879456 628536682 474746452 403024071 407258564 860311358 83766480 334348660 52828331 497695275 177895506 246227634 276407188 436710755 675472490 299675364 825619581 40592922 682586487 377881220 912389 338737837 805269978 603352697 335936646 521667548 493051471 837303280 555925831 45385976 791939155 980223099 295220962 378409988 567323964 650292199 759619024 543711629 522351279 340204021 615787451 143248419 100505046 192532291 905110752 743017580 476122971 105874985 730077996 259999915 83373239 914324503 620046220 684286826 588183961 874863022 890727229 780597330 548018549 698099487 600625671 662815543 161257152 234434720 889413403 883042600 716129652 361108122 153249135 72120356 844751215 792360741 176340665 149861393 502481403 20860317 178528628 187304689 516088419 931871032 526535525 68122609 340022323 596561859 808843380 304149789 145561255 914258529 888643793 49535695 994794638 655148724 829103343 622312811 115737110 193568431 6242072 797837420 868003136 372586845 182747116 670311854 419698741 891050485 287852364 952664025 286470185 438800008 854806323 666610396 770634644 942447436 677546789 520432265 478089750 788396898 293993794 517636456 428827810 756057667 674397790 833442592 733134277 884601934 627579468 968495857 385822861 615371067 469791593 364854736 751665852 334545614 904484754 326826662 47358523 443747948 385727032 902899712 329482982 827010866 930732802 198384667 990189678 450005239 863274626 475369709 608742624 417096059 104878930 433864792 617022630 450974881 762113797 878575046 583085046 816650094 720783784 536531924 711659802 183680216 913280105 28865899 508774444 102080106 769705737 92367927 703118658 631492097 131730510 917964480 159903612 162257415 202939257 960680296 678804137 392022868 805302926 180145226 911635274 251637083 695461563 878888156 801881214 777675708 946612225 622134731 809771542 561443931 792401676 969463271 633395637 821054069 384560838 64241099 154484723 989186361 120294347 393989539 774569395 885653496 121571282 899893213 530889544 519761909 623534524 834067064 908403376 915521739 393521437 372681679 500090121 865097274 138980461 215620074 159938960 362673456 533921502 974339648 987338594 916016541 995505041 496802669 807237370 502644658 187162450 618070764 277525892 816365021 494495129 127116167 318586137 604552961 649065197 838149576 183855166 64665309 438444336 674939347 148489751 501285685 119139694 461040922 267899298 308871173 83692329 967372845 735990890 287878021 937892829 293034054 360173960 345174528 935650601 908864644 936678954 411331230 643120584 100413697 467657249 651099191 479702561 333674513 818109271 584206735 110941650 912053141 300516810 481708265 786574517 938962015 740155008 845215068 882176447 953570766 559140839 653399247 192311918 276944377 103675826 847683666 5520207 115506139 90736714 681353586 60763388 150922184 598816419 431810691 573296760 383130408 556042174 116601883 638309578 548709741 156059672 388105434 76940492 364089224 274045664 627090332 192279312 838671461 678395839 522859088 796038524 779784909 717587888 379647394 121533225 76693327 471813090 128964284 45751581 822768587 576526292 377553618 12958184 600368748 806388966 379500210 742697011 162792878 284357313 46996803 476885431 679195796 578873712 736336720 839424043 296521749 50223466 288069076 198874906 607648783 18283830 871456503 703262621 18843108 984687986 235438554 635072697 62272974 902526074 661173009 169437840 516115043 875178644 639425107 97260793 183122251 687100003 751752997 572844479 68152686 951044407 756598044 760194699 515409705 755328297 304831454 424776833 154668825 897345647 88884575 554285516 156848574 587967665 682390635 886685790 51563678 230811515 440174621 929882637 339055595 661113168 451742458 325132222 408675459 170082370 952657108 358532793 810078892 952085963 305455297 192928187 640649211 467395466 890351900 358249089 509629473 279002612 780232669 10852455 658521760 868508252 427395368 54915420 513373882 30249670 108943175 873984922 524448007 318335391 476055800 148945138 323935879 786085780 634254313 180080478 474880034 824397743 705523391 446876125 685947587 906691214 402886650 418281504 921400836 232828594 428654035 232142731 627277471 502060248 1118712 211630026 539998227 160079685 542310260 481643095 834666155 538739616 634695846 407729874 755652102 96709777 322870102 216695010 781382357 410580698 636815549 961169870 193185182 631702787 760910521 110166866 830613807 403337227 843741981 539129777 346556062 892817389 220260414 646848583 962983198 28319416 145217058 644814316 790523676 430592064 423483788 335551574 348081687 940832953 419887172 779955205 550939789 399641462 714986535 198777233 369079296 469275258 742043240 667645221 197118751 40579170 14046229 246814091 947204019 453598027 6200479 175728118 210098800 964539873 799775605 502411127 47059611 391860028 427949242 389840546 597819406 818311542 952527445 268082701 389169974 155659598 191295695 466603290 880010561 967918829 752574174 778480393 443221694 533808659 662722244 802724829 992686186 342191624 546730755 528964545 634540564 455190779 624939965 690424311 677600792 317828669 944464151 804489558 109400597 837748578 72730789 11174216 361743950 875893903 217919899 504586683 137098860 519133029 616816919 552424886 952771521 397253041 356385138 239459245 171446673 187439078 307527834 983402825 421583032 942322605 56638024 172077612 467091157 848201970 545430383 1673492 230547712 953521189 144717157 422376998 633715250 8863185 814135792 491306419 888167121 11144157 925749216 415848636 618175587 790185116 987214948 8742834 899024805 647191038 421029678 943844929 778288866 175900458 229305098 317238868 924848814 250670118 998413371 898641283 260354469 319158041 554031225 719205792 584946288 765016077 306237874 569207079 535898031 252948134 743098160 881328943 841385427 665213831 420663202 823119839 50262831 894770889 593336236 867284312 130283859 928359084 390896399 757596235 785015850 362008254 500001680 950852411 397791248 912003329 565444929 96850998 745521533 318952878 683540667 571780063 512884984 65589056 24211384 213230245 361225296 940338153 942472504 378219510 480821383 200419058 663399099 792591316 177218755 756360119 910478754 499837388 359044181 631664000 147169402 662150306 690645174 637357655 749797160 35597287 485883897 254202776 81032044 754642812 345578450 182270478 721735711 128351368 921114054 851383866 652319953 589652179 212887596 427566649 143108811 271750329 325214501 955993785 996773229 875998246 142396932 77199461 267186057 941887815 456798149 498080935 87802696 497100092 867617192 399019619 203908348 342907402 598252946 432222612 242512857 950198307 352296250 302777922 560996077 647912735 797079209 588124195 398856622 366750312 857864417 615323766 807692500 918355762 189510442 846944910 835107285 728364580 795121920 538379567 894744918 842924801 282810272 150151930 407706554 962840625 475893173 290799977 338604691 476217180 591424365 652165536 427146348 840081244 822690717 419150816 607505773 314869649 903553846 639184201 770664698 578144486 974990646 669804471 360055429 714747320 117953702 518992233 490212419 706365676 903928669 518146304 416686327 479916893 148024066 548477627 444241028 260687191 624691847 345602923 414673269 492064060 761632954 239362559 686270653 845699523 945207597 350838314 913512096 729942649 178357662 144076937 173035897 176590446 411391733 187748904 223721999 685332670 442393127 863722036 733896121 777012836 502957966 741078707 923746260 111795965 602978486 474661516 540339114 142370216 506408364 486210601 321328893 42361389 59275851 694564373 442130103 135903077 289899807 561471305 290991341 781376784 931835878 771124849 314597021 822241253 359697342 556383901 600392768 796553017 458997850 710754834 274328074 162308349 285162313 170846494 73315224 386303267 326609095 545380974 465699224 776005371 32648659 350999234 805286807 749196271 45561004 73589061 788902068 812042974 221727769 880932810 540159360 407430065 242548688 545356630 229753989 339456801 684639127 892401214 350312802 896710678 177303772 208002278 762587277 427080440 923672492 705823208 611128361 50203737 7945081 945485302 803654128 619687705 314206711 629889559 777705156 981758464 989101170 759005174 694092690 380375123 845425409 809983762 405872997 313006714 102496998 801979093 335903928 384615626 53649556 520852749 453170172 888346306 641938650 621699047 182488686 726853780 234959741 976473357 852275636 999187071 275449282 138149689 971102169 579360350 695804741 348037173 421419317 891667728 362761298 289661633 745183700 488844555 69361597 183644649 85580939 376744129 138609585 939646265 803043621 621399014 310371324 840125394 819324531 308506122 860838982 639072172 728617060 311632733 220759436 112671274 33936111 612687829 347729902 960458412 757627625 739117024 177637699 582532391 351998748 231952656 709143005 605486180 276579092 802008169 386976597 973707260 22843445 829911696 547888014 527161045 858135960 271849325 823619328 804256257 385751061 118771273 806920472 381576711 216770071 281563257 946964254 697780181 569177270 251337492 193005001 383579533 639083380 481421853 16295140 727056915 286918756 932615293 821023290 893715139 864406863 400050571 9371257 395676086 541051889 699536330 451462985 666169441 562036198 924092317 355187618 151927957 680339017 761294677 505408409 672232078 108282307 800511197 566644330 3586038 331278998 601024565 979048595 723353567 377362729 628307966 968047827 512177760 994874346 308020615 359744596 959401025 256803164 335336507 671951957 534793519 716324653 983638483 140980827 919523959 689494856 751415792 830184672 814530175 14839415 167011873 920188110 772797280 262588815 471772281 58435682 7227537 167466781 111814511 100901515 296701262 696353432 276655049 175271806 466245185 755880967 765434264 734656766 294462508 856632265 668536841 834648957 803734064 701408823 15180222 728008780 840553210 880035852 243364822 848173011 515958411 518012728 87794870 203226449 931078065 56682388 469018413 119144966 602305548 669621258 999422957 802270250 486995582 679133040 750291069 646840337 593205652 349196287 440696818 298977542 840292234 169296750 235414997 977423354 682130117 838142998 130062463 101510281 271874408 897555909 338926573 109699745 826276828 270724982 223292736 52409533 161777724 718650564 545687178 647339616 683214423 558829248 319724565 966727052 859481872 51843937 812638296 113000797 701985836 613819734 85156214 278701743 975937796 278461629 742735219 55899432 40334090 639524079 56297360 275906049 52534180 640721273 468352954 982235885 320900269 782367560 918541024 676900041 871836660 854154601 97329542 782401649 621101503 242531076 625282681 740842538 14741559 49720387 312780176 894988543 628260049 999855932 395627483 494381383 670159531 442592502 404786583 551981193 979656625 185454021 966169698 650398992 687136397 754118022 83140407 745695789 347307198 40073349 827989375 475458648 740097776 565680048 283702278 586340451 326661406 128276820 306463472 857755933 709274296 24609922 648892503 919316377 488335585 229361396 305698009 539200635 701555370 568148268 600691456 189220215 740237038 283502196 244076858 518848830 982014964 646342637 9428751 808399480 95941669 499493801 255202403 703070029 256271669 882279259 197227102 677467351 326964381 18590605 934999640 96320821 574304246 284640949 780291449 67341113 494197641 474971688 358455620 366542005 722180685 568994044 545602407 488141275 978525448 400181689 909043968 440762460 508140308 352335026 836041170 957659845 957586942 462396144 572079765 385507157 73357874 627121341 523419802 758727873 183977894 476364192 999739723 127326242 642199444 9637012 609199116 905267623 972903064 330914102 838119433 112184484 484694285 192775569 189512942 443173911 768746993 443193281 83312079 732979499 216893940 887671578 649800866 422857274 816027525 881691274 234065599 667922949 334417688 866659564 905419583 741579408 847254850 36876053 359362745 550830005 949786527 925149979 627935794 644918347 135964064 751574415 14510708 603951095 953614706 641250920 124513686 580610976 248450632 377633074 163362919 159062119 315954555 90008304 181684803 294080592 233535639 142055154 764080080 708234213 586545197 932763365 810256365 630049644 280205559 222634011 244277742 733373407 42167536 35078336 323635665 61253764 776733941 431003236 578268390 100009841 904668665 471875909 803422602 980858355 725483890 257125228 40221322 722527030 219239998 385194591 173380265 583598254 280352372 175289420 926018991 34460312 444564104 669482926 430901540 997153893 381606221 641239782 41489568 85194757 962191094 929440902 322898068 694133638 154177937 126564962 734000531 220358396 8109849 793861456 181012511 31644512 634742770 483435190 817239023 19024456 264443210 434701753 466739846 328366188 14171391 688982093 911062895 46045312 571066397 182640643 103203922 947853439 198812629 992525064 942728966 736974942 829938740 939717036 920497368 11710266 467804533 505318552 582851006 452134342 137224819 997730959 722341944 383021825 910781183 975117375 865393093 318924920 620465959 482739752 757618139 757131700 660242315 203854868 742574667 811344986 573130307 76197739 148350723 314378307 969721825 504621334 487701921 860957951 352548733 337975241 428332607 523184879 457534291 721476812 322179751 275044542 253040600 898081815 54198906 768752076 28833581 869355198 896496615 256097645 62531288 390507659 722451277 788790014 680397161 425297519 521721150 463659638 509130154 713331851 649739456 908516620 376547533 631459065 39930410 411184073 976641167 960178243 425763444 901434848 735026711 459938937 398142736 69133720 616868584 396589330 47227558 916230082 840567140 21659019 338323332 998714753 42775082 284810731 34167130 379039925 941188544 984474123 69320610 223793206 592015902 352979597 510376020 495994412 566029275 454702176 447998310 289272332 322289982 814501660 747018380 224069440 383836448 727825446 776596278 207611477 577503236 363702883 837334580 755354671 270633385 539062865 897678065 658585774 201103838 736578786 554655582 213594322 403302895 533010793 388562097 190925655 169507278 416682285 85702684 548888456 805644261 229573994 214329014 320513576 938615322 667000597 4111868 523819750 429945505 405184663 917767299 296677610 13432096 408505140 526638247 908338449 812029510 333564814 830540328 16138156 505323009 444963506 937571695 372885423 420337750 692736620 673704943 346663367 368807741 769316682 768331263 827924892 140847422 760686841 249366923 100519334 411746597 312736955 44671855 262271834 247810784 612851319 15413070 362257450 227418408 14600957 450410502 417091192 374134317 495671586 498368833 532107946 607813015 688318179 964999578 620552112 710467235 324820150 174806556 420958034 556607078 171568837 671402537 829943146 189662453 36810042 634186863 341715474 290465091 680486544 654811127 593055403 802098544 125761282 895646907 392503297 835780744 200140732 733664333 310075672 327114221 798184729 624810900 233135244 906296481 303492566 994880840 508592527 726963024 691038291 218061018 364980136 563208579 313609939 97051602 802865017 44850913 740567223 160945393 647176495 504005770 797965980 520439847 967292378 602571696 805676332 485287547 405350395 577566763 926474455 797359047 850582327 834975092 407207449 258158380 975378581 201178292 729568838 167727845 230998495 507192087 733510391 112238966 617149767 715436051 686383995 44576676 385242720 534729842 181442732 895446500 557080829 89356391 105693315 462566649 426829074 435379703 528608146 886849542 76385071 532833509 802907024 688526806 644687568 770185024 160647437 393722859 523548518 122582646 926723751 722724566 585804901 260645168 717622732 926480759 988316119 90470372 261890074 72930009 950871559 353898234 43807176 612779852 181808791 440949736 852760573 53169762 801392804 472034081 102734017 986621343 905795690 988095157 259261733 750085796 872591904 648072455 554263603 151090454 283145158 198096333 349472610 600158999 669531093 197812734 951796148 548683106 867979955 785724834 488171202 524477669 881800171 137185350 907467419 441692118 373720806 861750544 342707719 372351760 888186438 465954768 751879106 404727842 489350922 468041375 201574287 807257909 354119994 842279513 867501683 631479890 962941289 122634138 127548287 608224207 857551222 78394936 409942898 136732364 782849410 606193838 493843316 331468586 519401104 469833784 57010483 521859727 999627582 961397900 847914021 249505203 747982689 531770760 100337861 797667178 832209531 163209751 285515166 688425809 916118120 619028766 994069411 248715173 280230780 139568171 298324198 471030736 638112992 264928077 180503806 805271052 711491405 236233803 985032599 941790705 293191077 128074585 349203837 818646479 380286597 801636320 185284849 254844690 787812347 608525750 881190349 792185213 241732805 923169165 331773945 867988337 974979440 425440013 677945505 625051124 465726403 474280092 895360860 647780426 653081018 736313987 161638660 399187513 652505676 978963886 884749135 784493762 604246691 372149735 772615688 160977849 864242633 547257289 360410406 771560004 861110475 416000656 641190174 600257464 476829117 269002853 751022082 428041215 625430392 10691242 383933099 849020007 853598777 658500134 488879736 315979083 452720819 512673793 770142354 766722611 401194732 601210615 949964804 908237754 703704301 249141079 246318576 670996973 350034754 32649886 92766486 333145913 640766356 733650288 186680064 136985785 633697431 163963428 907364857 989892751 759848045 60720283 206209646 427114176 858651811 974826435 29178203 597874742 909170345 679764034 888302030 833943594 489381780 18779950 94467346 949689506 44163225 637704397 964423132 517869229 94062002 621298007 407400325 465429845 145606267 422568906 344939038 711639326 471828444 197534169 396355934 457342925 578167447 161152627 354596221 883325326 540820005 80303517 448930779 565201601 394317812 989769393 128977690 85719377 101552307 541119728 808056474 681400727 927663688 781144045 385240232 168894271 902074163 541696421 559312042 380795494 126963206 169577415 992851243 584549007 477679980 178519068 305443482 384242996 588134612 690698620 380897993 502600092 564445559 673308803 246079393 885865826 643898857 410964306 645134722 213496877 709483059 18315783 367556738 486690000 616140304 928386676 201900932 767830339 60185619 345465243 798580864 143820952 922530421 67452422 369078763 601620277 538371044 374950312 932223418 961717162 923055244 179673877 466403083 954199410 380275568 189231635 347883779 397613259 993752020 607831820 53071463 848307975 594268548 197913486 304493776 397341453 174321261 959050939 966341983 444578481 915437651 849156305 298486822 240301522 264462104 598294318 575717635 494177053 692939379 342105342 700130621 272032813 41717298 404037324 747286406 850702435 488217709 71552490 323517928 16817160 540010875 656888266 447281446 56879753 463582382 226993585 649911989 302472674 663619143 655877155 612739195 821273311 388936767 629389193 785832377 458054585 551096063 193402721 698800181 84943117 996469365 908918033 551873972 554103385 926840734 901836095 926368093 560881821 748221270 378300342 296351881 564042244 771131198 272615498 483755407 948355220 170494081 158797010 871860407 489823655 420688974 621464165 376818586 446703856 953424719 770460336 225429556 268169881 528416799 82026595 84255205 407936633 11750111 753712324 145087685 343834811 516288988 509846774 262129804 799987388 151073410 4034793 222380607 440829604 672804520 797064098 249314767 666275415 283772120 28390378 909437313 237488349 648666991 159094385 188356927 944206517 943305382 144566207 514433874 701913238 558434020 881985533 410321344 576781684 931272838 153391478 163850978 195517565 591179545 434410696 487459117 833860640 760732776 206251459 69815833 461385696 966407634 928613537 769430334 19771393 227824404 632118415 234975 591327287 628829469 269607368 930680573 525536569 326273940 899552431 314747606 73347108 77509410 736432769 141890890 590743923 638427886 65662755 437876243 459897385 615966972 913540529 766834611 43768078 710046754 375592658 182814153 430604731 106733388 69404320 361146355 638775842 481882090 166419574 573120618 271157232 651744909 291311168 852649780 894435661 177708370 285181987 919406570 514066111 121981210 903749621 658742537 47061250 46639338 609383089 822735292 901969701 123801654 79890876 485230292 600893855 87965402 889547616 742481491 749066137 505576941 389161094 917917217 874349774 867694134 176862880 843256859 29194352 115441638 541437293 562396654 316453138 642047463 548926635 676613245 937683897 359180687 883402090 367035229 773845421 142228879 615592836 784271190 171126624 733093548 925102880 443152797 437198881 253262534 562626233 765930728 72305863 609626795 873464493 431583336 827640698 547108057 475275795 104308647 995820293 862826587 24403137 78449050 324120589 97798424 531998756 521306694 508781877 458624782 36202464 863161708 234852827 291560196 615309881 230105746 798613603 217580341 186384189 455038562 31635934 506493774 885447459 68030575 875899833 601425449 617253947 499235685 473093566 675610911 195907290 67401655 485441129 319562543 259538192 98251930 680976281 470058859 547871399 548392962 216456478 65147543 570320640 724914753 367285504 116806190 316730727 78614425 591024664 148776528 463792694 49225595 605886386 45939780 279441157 609705121 211763769 154983860 98573190 307026321 835449301 638788578 873047956 938955983 526861519 92549323 454750611 863537166 873177609 783062840 153666064 967663740 286215145 866119863 575068057 408659429 74687979 137715743 783638983 827657609 27952493 504046047 422679236 199151393 648229239 169938723 74552374 120844171 531731602 939076640 35712029 985862076 52375523 603666150 341597717 643603974 348711958 878932379 170972263 641177356 191394784 851216768 620643131 587554094 203558378 608633767 396836674 979191924 289874692 73637388 860500084 176517313 376225850 3968623 946070932 678202363 425693478 746465695 838475095 714588976 162845588 646583535 989233830 931138371 473155007 452696194 291392131 836036753 38748360 250705368 657963614 601509009 846424751 786793735 869196349 766048199 947168939 244013636 853094487 239690121 538401646 798483241 289625324 232684258 671660418 553244698 795170876 371736348 1041550 273261285 1465969 782678264 583971919 444542451 274967440 828051697 928578359 997081562 266598620 582316748 521720621 309319596 551333349 688530847 904006801 809518588 337925135 702728145 783982007 872157096 902555038 100151028 941993622 805855318 767740774 138288856 756449426 268664753 423226000 418486943 855245356 860774953 290725834 590267525 687267755 588266514 224270651 8688787 352916991 749430786 460790720 992333140 856084171 39333721 802003877 99928485 104992424 224619935 321984620 10574171 701730463 602097452 895967517 67762044 407170314 697333546 927801557 291221615 713317988 711969445 565578252 478637730 164448764 164195325 685825430 701383203 179544768 567304044 160532621 860194623 144589763 316211509 41193877 559186820 621752472 324722383 991360839 500135895 42641770 820181197 637926292 523196349 547357630 567221763 894410612 191283882 648013474 552333150 948737575 816504323 415162209 74697853 594759455 706242672 228132642 845198334 317835252 874022271 574113233 635703099 929432834 810495638 419307419 602228676 60441494 152244801 708127885 654326101 345035134 44676973 599387201 122121295 941789931 278759979 232802035 866520725 785240196 489002583 281315912 631424040 347832549 284423064 949886487 790682431 453727280 255671574 494900002 133027369 851358358 599373439 759465643 999942369 981885193 412234265 60238445 240149979 30135921 548015602 310265553 498483754 271985911 418971799 912922153