100 93 899940079 631288446 93792064 555699182 506101194 344848508 939474269 535778512 123935909 993303556 100028654 631516177 509204560 195621879 997679842 509529871 7534351 264798885 176131796 643432596 257113068 599435709 904711723 2227914 735811316 549905632 114105101 691019963 611421610 424785770 118893718 76369138 843002223 14348768 350294067 501490725 124670294 123123438 457577111 49434696 268864443 616635516 520776886 517328430 40305016 542746226 676714337 372071750 718769576 165214 966910913 383240620 918595645 857055955 697389497 140547589 839827980 363586644 899744913 233922311 412844505 736693932 379896029 439027595 691586465 564300709 118227731 259100342 655715424 474877010 425742961 476921304 275372257 908881882 509326712 976207993 361005030 334795252 838937186 197789304 357605462 38687086 117213225 294948982 433201063 213929689 468275564 638790522 367857114 97435036 452457311 653874123 6231250 53 827622405 827787655 217425852 541223524 663387512 987208119 109065727 949236197 899309278 517605654 181628160 430498182 491982279 331925690 787882958 762492738 427594350 666676208 846824662 110774972 15171807 991646402 743334099 838852955 242674739 589697629 432428049 641212610 788337952 188800499 662874012 566680313 72102337 445119637 99878191 284542838 827414626 289074248 504884427 172356977 863828670 839623134 295585495 985004018 438417371 363417655 172600149 694105734 770793825 728067760 925871864 740575454 901548004 90 871337597 427253795 642123832 307067740 836100559 182418188 447362132 668200006 294469409 577904169 674391917 259395603 502350709 47791498 692585511 618320549 529347818 744984256 484842976 534308039 788696419 751300588 483392612 35185247 472657572 902024786 378764293 807676536 649916776 2311532 625511766 653153872 462812200 673964267 844258604 191134524 531921569 486070005 364494323 170575102 32548136 364695294 570890479 611698462 276781655 65480933 729118048 96763212 460715949 748807260 428454116 715576854 687883745 540366265 338189324 712457816 414753260 106405804 753914768 290925821 630506547 842994964 280505034 160278024 560019168 204474809 67472371 641398358 594769997 607591180 64304895 185148022 826628366 274572231 68801231 978413701 146190448 631830230 443910003 945325596 791676589 122165952 576806754 504318627 952712130 686459058 657221683 875294126 317622556 982906893 65 642407285 124591250 916066889 951784124 821873786 696036538 385283012 14708947 716075897 987585582 243295168 961080986 240772919 116870239 832100119 462045685 545449554 699138146 185396894 526131746 336278638 749265780 218399347 115666081 359292153 578866452 861506713 360836738 654514280 731962638 45025310 319312073 371045156 227198892 353762897 451101000 884637761 722791356 284163313 920954479 991107024 602379762 357923885 202149237 608969021 466197801 854794321 549661467 821402132 355682632 87210092 76037635 540005683 601319864 925678686 533487738 359905767 78370068 489547256 346226200 820830359 833110781 817160597 52379175 197148800 83 459490070 379995490 977207958 784028419 369313914 955072257 279134347 624777371 517203595 376070175 857237737 478543852 911650619 958742577 799944398 583983321 16204348 482667540 629780617 735847260 557626796 665629305 166364685 679393442 900926097 638583897 276339673 993476954 773509474 531633726 628084670 529074974 313220463 415600458 578451294 234839334 900345065 789453176 423264754 101475751 739187416 824045482 386572572 413598606 151155993 829120444 797754372 476254814 554080320 311716391 1354959 823668195 143821478 123276845 755674526 326239153 150553781 470257808 678050560 641433740 649964780 583390135 169012556 932691591 343753023 656679756 130779665 150858894 397004043 339290494 373658286 784450685 880598792 838941037 175055214 615666772 571528855 32170148 5384655 145263586 65231630 206006880 130673093 58 568186745 878125908 374275069 284118883 378583032 422104729 195596599 427706935 775385851 380074970 660630337 808366664 428437028 857770294 260302961 815021406 413986766 19651396 475408580 893123033 325258713 995804192 976077059 363160369 874848789 72262823 657455228 207877214 692355595 659681943 987719840 651012731 4544008 493394390 458086518 439013699 913359190 513694850 898161381 531141235 162241557 149770305 492477762 685796589 641915700 584106782 268907493 8735663 977711114 303742084 17006293 618978082 756725965 895712247 518326282 180038462 807925614 483136187 62 613433223 868479996 705543743 950125173 656902701 388885742 616801511 301217243 214237062 249027710 103640343 944245171 638997918 807738280 356679916 35280062 898043356 625663002 677646767 38901818 807432006 99555738 582604042 774687131 690743721 385377542 277579330 524207342 309540737 419021604 765544624 989013841 228667819 37420747 906155710 861101006 429973177 831715831 135768217 742384431 790108116 613023409 562371524 724616646 429315690 774125355 701915059 664292273 626933306 519870826 467767047 40693475 66911305 882193568 98744710 466384146 546049730 966063866 926843489 51421998 882523551 132776305 90 897838538 777991919 182441982 322652319 276685808 333660425 356069755 326849358 478389497 622898928 621837471 145232979 674639600 454192838 851020855 275729730 6811871 628186884 304660326 248184796 57614744 285937587 902459822 512389038 55127232 636261743 75231715 213553979 843799635 204243019 771456747 750039833 935976299 248052218 251471777 233424109 567465881 721071790 101828243 748630900 943521166 528312872 222074140 34962083 586314789 477100650 692307418 522121943 796125130 667573372 157198571 189915964 311673823 394756611 900496351 125862889 319603389 384479353 518444471 278432092 148340745 147400184 7058675 770485863 462858991 125677449 767050565 495233236 147342582 101060122 459468061 104102763 972244967 744827115 589983714 706562398 528306790 27960687 196604934 785455355 357242286 510872900 538926755 395804339 217350486 795132108 17794604 998230734 386823551 509176647 88 793517103 396231600 89924355 251969504 206863323 241481502 65995917 967648797 158687530 935304012 965499010 31880211 298165564 878376652 678390531 358810871 272977371 64597816 415107817 535555995 832206350 996059393 658892715 770845712 576372925 382712453 92431453 263122511 820370411 307989485 728205155 879424001 975982109 380656757 498418104 24847074 610098611 511736947 724737995 989489646 48146786 257131591 469563150 202020210 911081135 964610299 846714069 47151401 567801955 45472586 793656704 209277780 533972702 860284154 551327873 883708471 386544930 147290280 987005197 544784529 421585923 802449846 985687747 190002737 198809128 769946365 953684180 766930191 575254180 91647642 807393808 251528679 676158041 779024186 730263573 343495694 621500715 373495579 877008060 995217146 243797766 652094966 819511243 428740859 648814948 327121436 198207615 171458026 88 963510461 179261065 900916151 809810616 126439107 977543108 778530870 670248554 197911532 614182153 39854309 543646743 208248938 535242429 223767397 630959355 33394186 720363818 128694548 463749373 33413121 781842383 363593046 204121906 212856856 375813393 721768820 852055093 22052240 72067970 842853234 723361478 187457458 439343339 121158940 1094072 691460892 392245586 954539318 448973189 867225119 473123421 330484834 628116948 419323978 798525273 166057611 573908909 321984485 459290578 607240132 255585677 140723579 3411991 839931331 812141275 323533980 383392776 58510516 511812972 46089722 436743759 874167373 106294323 620602151 236700832 320133760 674144187 727836738 199559648 489247580 919768343 565065249 578609747 457200991 721648971 246228530 743888046 416548110 752449441 791152174 276893686 862223744 589567137 807055582 198420832 582386221 509136779 91 818760684 425180492 236891234 659383926 211745031 391871931 265987548 69689193 566801380 260244052 287806889 222968905 547759741 423769140 541496611 948460894 744445434 353010165 417872081 459393929 944234745 391032841 710667901 893527503 742852621 160769193 909405078 580980751 692175023 998861470 146771693 712954494 157026210 678837506 744468209 55168219 38358505 15104545 197306993 99287159 530081449 435154518 961127401 713430900 849372156 113165648 209896407 120986111 258314437 760551240 653306091 66626730 942935609 431722444 27517731 588851339 313565598 708797675 164075897 855122490 225075938 66208336 121239537 965492168 365773808 689965718 307810829 834611200 624080570 178066169 850961306 345189498 42592102 929385098 875886197 840662464 217296300 876345418 462485920 550881703 152662911 636746944 427312367 673376909 380411715 52461377 299391737 642223379 936885085 447890776 319162564 93 64222791 506183598 570084545 952075828 70777119 313618569 32553089 468568526 295832016 800698145 413923753 823595204 957771564 777010197 992351394 444674781 197832351 625795523 483134440 921672320 965926014 711180752 43133970 856070859 464479246 609428110 85691743 911176647 812494327 518079089 614752076 778578640 879998253 98906043 365750451 59298052 857984758 742343737 63510837 977289270 371000742 877215112 167693986 986585441 49752917 980072333 606262789 352639430 548232998 497172964 65557116 361990135 395037162 392423352 323546474 778339 41245731 129499222 593988730 341324066 718380422 449320946 400897577 993090458 407095479 773585984 750151015 19876675 332351940 669126452 919716112 869882286 704742375 292539144 896594297 466471316 3460657 998645558 295166528 776633453 938556753 374084233 952488678 269838607 927632692 35545398 365174985 625000463 768417229 677668972 427953468 455747669 786023470 54 243529967 67020795 495214023 415250473 99593245 72968360 19054500 679194338 334766695 377220038 852027992 809979251 130677375 25357978 37417221 253182817 727767567 354155925 627146167 676475420 365311528 936157728 227839556 23525557 477744613 854075728 579255966 719439102 362306260 948500530 259620296 321895941 565623678 473010925 537381481 35959188 998825863 207657248 265505569 940752770 569765602 193616657 878842660 655178234 750371048 26846514 656173267 497876332 25850490 325273025 224030372 779432477 162993637 124567228 67 189793033 53549178 186428590 18776099 325722734 901505471 55603117 822506255 589526007 342605144 167144185 578223594 206935740 112771897 690847227 610764458 732382241 967288153 460923370 885981606 963852556 125393677 468823984 855016596 376523087 23206607 826960177 26138483 174824905 652615499 839283392 404523418 232052493 913302112 80882662 367268035 209716048 986362387 359032936 781135319 53727841 906052511 472208504 133895063 713637409 525746255 440438223 584438713 784923631 153000341 698664941 59722361 714157299 198138455 481446662 526589894 681980065 503154513 890291662 627586459 675188599 708656849 2102555 363027060 22487775 298234392 575527279 90 576544981 735718372 328616599 578576026 638062359 381624188 846793698 346512014 195583783 498077903 206328067 138512659 328399962 921126232 337868989 351141355 954353147 270328695 844627018 355682523 600207018 682656395 319599281 394663516 169963646 583061625 329291096 635930348 338372729 310674072 292478337 714005688 424305972 189354432 768343798 225574265 762334761 935361751 415497508 41952914 296686425 65882170 36008416 175149113 117143740 118967643 851656469 948120499 671489589 552412438 936830080 113363883 601972225 460141527 553259926 878340545 398179717 860404120 817413475 895371442 590711690 230431539 397374227 629574787 34226201 460392513 151651589 611750794 657064573 811527847 169605872 812243900 366255549 7181614 749515614 185310086 97286952 442742846 656826779 84577541 865892217 364800542 881760032 342499142 72593016 756830146 802073652 126606390 766925357 491058708 72 243665161 812569226 549720560 243409931 134156057 33455450 965698248 130191752 270408496 802468219 177487559 644952817 650923293 430543764 338596305 434413050 136243295 578375671 707955578 484337819 419135521 537314645 776435228 55818868 903763231 646113437 930899152 827800020 542451570 459874291 458842337 122231933 751785765 918202046 104249493 474754122 864264829 542430197 244125147 86867563 30044080 936499985 557915375 819851812 164004230 227430338 488003865 639645987 629269407 761267814 548274833 542682902 791346478 35282109 323362584 928661690 134380707 955897793 618834581 52319646 745531871 783321632 553736113 859276520 321728135 416169364 168282646 229423835 674639440 443989222 797695827 291699066 74 807406901 518326395 186177186 229390783 629367977 14640016 101224788 772442455 403628468 593207677 803307989 811473743 332813568 930303829 912416230 336166753 918106424 505614119 764222900 907533760 925324955 743568542 430580711 70500719 408527208 579702777 449645830 727363182 332120814 58068354 366330127 796096886 350869759 503767483 303348979 304866870 54666486 13396475 863819713 661780929 410285752 85333982 268123151 153732466 947327664 575907097 976309501 571719315 281306119 262190480 535171591 478380388 896091402 376088343 483604402 266824748 139727399 345500606 786710808 749353456 908714216 926156475 746315346 445210998 407534683 8362613 566122461 178375548 68030895 899721129 259169278 162670882 719046059 572374519 92 32662739 216834239 339809311 823805034 745538656 674477324 454637813 56650564 455211290 183753163 696196702 491799673 370113145 913743647 930078298 795973964 272519285 492772428 140535844 359938412 673942426 107093990 356728164 151760923 599313615 853221979 959176652 541273272 943268358 885501390 796588930 980039309 194239061 361949330 369695759 949622210 486126397 117160987 275505940 491442746 591704695 283200883 974786536 21315536 137375270 154907774 984521444 679093976 416638582 620339496 140749480 410127534 114774568 605929385 732479284 39708590 29135860 832619084 303020341 589024146 277143643 354284802 657276100 847857009 435747478 988696470 663749830 163744493 10546039 833768313 463054986 247040486 260479230 573409924 922193445 935144825 407429970 736839156 445884452 109910719 632490190 338972537 554630399 960130695 662447475 597316726 440251993 597316331 21643792 859637550 104734030 514163783 81 529483077 899744286 34463536 730534145 257412829 598812700 354299085 253738757 277082420 49034916 370837264 148687404 411034334 399423242 129219360 997114411 322224386 459307125 193545706 798222610 712078515 153092136 883282125 579793662 82095361 501402959 664056900 195951398 386573088 667546487 260684427 109206664 695253913 261304666 560554681 507596988 875064477 851480644 540243289 354484245 356704884 267712616 695121182 192507571 857059148 86431503 37177489 161790728 477045679 967027321 64031081 232836357 157147052 870884891 908224536 923416236 213600235 443079934 283622654 781052363 608889002 617511848 364710109 982563148 763739285 559854928 769967624 866058801 977119991 795326194 460235254 492015166 758549860 839262954 256120171 362557028 229021732 997580884 11804279 109264795 694546259 84 143947464 714815395 229483155 902018061 105896845 367709824 870785268 596481284 572822322 806469118 873505532 127169623 435436735 466215605 869745827 797895336 868001696 475191419 902714767 914078409 85469565 272209718 178841702 718877282 618424052 601207106 51761625 516953648 761095661 922974887 367620942 620222092 149952734 229368537 197863062 983452352 786172621 970758027 827174142 119088727 318001352 770683780 132461157 690857124 885826446 776102923 343065053 674810102 308067492 400295765 884720723 32280733 346914316 762899664 978703826 919197004 268348279 194599678 958879955 288998711 873481935 434205001 844251324 538709044 303197694 717272566 355842929 347798094 414291676 729214636 111918519 213286505 353934780 791299651 135214531 742778656 938576229 655595182 83943976 439228356 391137300 960788225 105337926 800473462 72 288821628 273722285 122574477 337359997 285094907 270404148 348402772 398460045 297860176 417635848 397299334 270943001 678750085 419976021 592429035 845883157 669837856 498824724 880164722 147515025 838055624 511066556 257985959 596865304 350895802 34021344 112833472 542964679 591363869 616939542 235141966 44564202 940773299 274312409 405968682 77443771 128888472 448430407 886104645 891715519 305125433 949021599 905149425 408917580 682925985 498488159 795798353 350558681 801883652 333810398 794601764 200666878 378621742 579961905 481037422 897117910 303376174 256821265 859313181 2151354 69823098 422601393 36514659 932785193 699818498 757779389 268396367 512857125 554540194 559155058 502703711 870515830 85 55258069 495344521 295175719 258075209 257581465 796802002 537331464 955464586 437961589 591219634 848454352 73935860 338262460 909604248 134324751 820223914 329204284 272306597 788400321 853199784 3189282 962693840 569076764 910175349 585574511 722834151 775985789 993644857 699568407 302840686 406597754 341384156 654418236 227947195 675272662 105171648 138324789 405807642 94240379 721842773 652447617 66557738 663240489 312954533 907316770 28356373 512067100 199234830 937171206 229019712 462857509 65144618 600024071 922513549 979991587 243322037 138867009 175171656 354614052 808394770 195803927 398947588 214084471 665842745 116586620 363889831 589815088 592831669 264541733 45936860 944281707 966936048 316430366 279491056 29546327 673414628 279680479 321684615 206062078 533335550 53741465 189764458 621231173 325575131 342305783 91 783513038 986145748 40798050 660532564 425413858 70337668 420318214 335799238 607645772 423426406 960918584 279521145 953875394 18992245 98097099 881370382 86647494 775552852 28705767 129677720 444085326 492484140 716482859 449465099 647030777 762358467 514256153 881420813 459606387 582330390 691018788 331803182 945892155 884912615 937191946 930898783 373717891 257298526 314825824 638962525 997476094 942760781 612423484 367268777 322285668 374893592 499483510 274685618 646749517 15472500 660296945 963714990 194990820 691756600 597142003 820548690 259996632 524451147 251548408 387108639 235416863 564658934 652606822 504396805 655350741 926104608 572670637 104700485 391149707 780448767 185655090 745940847 218311433 290997057 97443714 676583609 936466397 254003675 598873241 9200742 690716013 269338123 451549478 116828043 559492865 962463427 36010087 406126974 352794692 410479733 978092746 82 847433510 214753433 928861408 747606912 668875435 381472210 574502632 723641869 194292371 670889540 193536556 602879959 279055216 516977785 696315799 270287978 959474304 192394429 145761372 745559820 607887658 408638748 210419694 576033140 508258639 717831325 335264407 334006790 186390115 629190671 27383580 769185145 925871509 588849220 845874016 533849779 223681222 135974942 617392378 423479703 718246007 124863594 708705643 157904787 962213136 274430453 611887068 174069134 794442061 413643217 540225993 66630234 850833426 421579103 866520923 692147421 870001258 342551099 135129970 849238514 681531706 817243394 844242727 250133910 819277937 482135309 100442536 6786528 942043968 409635025 633215661 625937490 215860534 459326736 768996983 634502060 186001127 649013598 721340347 470106268 987456479 896072392 90 418212816 20080326 238879605 801214334 31984221 332164330 504008770 984099813 168728646 383785074 969412129 766062483 678634658 956257278 733481335 34753077 891468000 27617453 819858542 752643507 659971041 697412873 13974199 906773704 782751030 859057527 655750622 377797830 165999418 701736759 380761735 606768286 435081978 999063633 301972263 704683519 909451172 179499908 308070553 449747173 200463764 742118449 472618897 818451906 404989132 655578648 547448818 392377065 783561647 358381904 382690764 722122448 645212384 131011501 233445073 458340271 225675398 415468935 33945132 84825044 22030571 656375049 766642133 216208956 338181003 6854742 535899248 752851308 205339624 707500685 915750305 414235767 488284074 589857881 368389989 834326861 786896824 272862581 972031617 342964894 247827522 890904142 538308222 403488722 402259947 59523182 604863087 700399002 895195747 246033564 92 918209265 514579213 791844957 963574326 343756270 467475667 144488819 577959937 911444874 124170467 281641692 130857998 75031370 431060530 470188597 690656232 342497900 116236758 564735804 743678065 179828023 686187450 714406288 768746156 580559898 920408730 499602960 334979346 200315162 225938597 503903459 594303113 866591573 532259899 190993852 592529177 104491286 490271119 833596112 160680713 827581945 328222793 985730787 305082824 272908785 116902032 51317454 716894325 681159307 560097824 587914609 233097457 765019581 655210003 225251156 678142991 489973169 211514165 796617977 138168545 213964013 679944963 698874407 557103796 401414430 758586749 910165287 458559211 153656888 970681524 26088807 379837457 262593358 673936774 258418274 135859692 533039853 203908604 127405233 288649166 784998925 575172746 940773536 231774752 715205782 42268957 789393 39689982 743639641 820504229 27233797 938073665 81 707138975 111506828 619800676 591952991 139138104 641388665 306276221 814769349 695956044 63573341 882282012 490598811 746144103 976795830 462309116 476303855 643477273 102264549 409973856 772219788 807325839 839277441 498793402 725935638 973458906 59508680 60444644 764753756 534306927 234922366 272629641 564909929 238472754 776720344 231837164 233696302 895055482 855470805 737601048 338224514 78652687 326786054 545856447 266370860 728677326 435379494 510914301 534910211 529778361 836855336 69893876 568357565 151033359 892334613 381110632 56847620 886827020 884975587 656645784 745964273 723028791 464329558 813144660 244069553 174414794 634151934 527812770 977729997 858663356 689536579 334781577 488290313 76792050 69811528 853816592 548423542 121044396 993031929 876158966 521188199 653655733 95 211088715 89912826 319429386 271696178 617915732 737087368 996921684 79851363 746850877 284739214 167897634 629392883 164621734 503400765 685741882 10771129 616015407 305562846 16701714 886312413 862978177 880550992 653940856 830105543 761152938 285479543 380148954 476267240 683870578 835253069 162650214 323603588 243846938 562814255 196017386 333392674 463551604 304904884 339022309 616980942 966299716 899631661 563266362 694719499 339479796 91481688 149479053 863356513 876222047 687858755 291501600 207796420 274492297 22884773 900147563 348251426 531290986 783243670 617824246 571610961 220104170 33957660 578840485 26848393 127892308 745095647 769627109 937533247 558489055 822168084 927039097 40810854 118266715 109903667 985353077 474047591 557346848 881777593 606431130 914806827 635813045 769204913 60757048 330062159 268680132 217762750 810716068 817287995 328485453 984753177 425508988 827684248 541867987 464454739 391730173 78 494232198 542464892 740192843 5919216 657370970 890687765 208984075 928684314 978195033 909464390 507110851 942178432 184984688 834607419 891660488 577584620 820385601 876689267 158004508 841337092 85019104 339097590 513667441 779321118 92400120 766873562 10573734 733747910 875359833 657888560 891346272 463422635 351425463 862754146 888262440 538093806 963052631 403072265 89870039 972873122 249765232 409628798 448511860 995948493 621509875 879922224 929904923 43565410 515593106 943940656 613462904 570525380 780450530 312287160 673122844 841096081 498858483 749821396 794920304 664582892 9120087 133460241 306471769 659741708 753462721 22260290 319261946 516325802 948784454 837364844 488065089 531809752 506771448 8487932 238142997 146108076 695160484 905225454 51 362744448 510750039 401493452 304382676 224464924 430110029 818325908 471048331 178290979 358155167 639220333 897711477 981308774 617782515 767004168 638720831 273601870 681851107 980809848 253900501 678713924 17962468 400762391 605275505 654053376 471432390 845239661 984358118 522534905 712113125 14174805 268372903 637334503 101258008 882321005 21722697 869417970 43540940 479753208 42563208 520804845 418922146 370968109 778631481 500134836 415851408 423827476 584806370 785937636 645664917 204749966 57 307981984 179326283 911978547 933114299 68301171 565017935 862769028 115495406 862648325 586079600 208814513 243106356 387002609 712895851 114323428 959913993 541556411 451239472 128384233 947097295 745062632 68303349 538383601 791641672 654708445 752784420 404466161 417551999 597191854 230894351 272595151 435515169 234282655 298114560 172807036 970940870 403990804 581759101 47142082 561539656 777893575 353146812 298298239 405283137 911768463 655558415 444421483 661299936 377264558 519321530 485015011 388971527 383191024 35972636 135596174 298739287 513480829 83 874998755 783429840 53205395 280842818 670422627 521689517 616826044 481130305 813766764 709649294 958032053 910331502 444508546 817107714 1767157 384269601 501504620 349559298 233468038 351994982 775547036 313700562 911418517 221045817 449316004 32914092 963422557 854803054 552833127 378964968 861335204 674559971 192455267 698837505 793246510 330053607 64706907 421651219 345033837 940420902 568311636 987966232 319489354 922181285 588878641 572416670 652493480 429732856 373728135 127236639 109594724 781133371 463988056 665485379 307745924 616645635 639174083 54334637 194330864 79920506 987514750 874090253 191081732 745139073 706840616 372536038 690766687 824648948 427240273 42690524 111330631 148724144 751614130 948286423 265811281 520419470 167754646 150710678 823958831 389182707 848767231 485091640 85218161 53 537586957 151697457 797526592 592379217 148020870 693244519 170839710 176271117 327083985 272974428 482528498 141939181 178928062 490739518 237114609 505947616 269575239 933636003 918410761 135075976 216219838 289178819 335369973 360998776 530468388 789016632 728709300 672370998 344327000 921853301 760331472 757344097 728679896 706173626 63973034 62476894 192451673 816374334 602142905 533214572 564687354 692106858 988805001 391078525 969524125 381990831 112345627 614350417 176783536 596594880 829436603 886903512 834355619 84 617514112 878503751 476783191 903418941 791309110 807931939 118636822 190103062 605041814 356204870 20695363 878459920 786168605 596646965 164606493 49190764 323036512 586737819 366387095 132492159 258869435 693560506 688244073 186593300 935990969 822362726 742800628 712404484 244448372 203803230 438305663 659067396 222129752 477884683 345096165 310522586 301250932 549119774 929278579 675169860 677271396 510424603 462722988 573872437 934638824 121381673 604486115 28297681 135346876 383237829 312517585 225584681 682889935 952557898 618300617 598270942 533262251 24883699 239167920 395342193 569005651 958536751 681947936 728757037 683600182 351443769 188863440 349921451 491139054 29432114 512387704 956568899 632092908 857115951 519175062 342457164 17995171 599447137 167043713 968188377 578544421 443122508 556838138 348327851 52 21300128 591611844 684051757 823661047 423743685 769441702 933502690 114464812 525203071 850212303 926185937 855525061 530472558 864039709 410172675 15890869 473378494 426018468 562336521 178777794 673759597 635173235 476078685 793241416 33276820 548228713 778034857 612654458 617517779 921386114 832284727 625870624 245672645 294361703 851401899 322177898 465476821 400885936 398976985 780938702 693273049 563885190 116479364 429628831 628505038 335651643 76106666 315630330 92721025 484053139 656413512 537914872 75 321768731 287595182 34777268 139970889 819327549 454083435 577754468 545242574 409400209 315184101 447954794 842709902 481670019 570627904 569925788 234301740 879598603 968655053 675965053 172245054 653783562 505850613 305218130 604063275 417793426 229175464 185942825 706648337 940172163 821622192 863163092 958327400 963954003 418846131 383949208 721607926 404298707 527818110 147976583 393258296 499568172 328809101 911700056 73589864 925044086 8161982 215616151 215397149 956776163 271847698 401150736 742475235 309966757 249401188 258309063 13549532 422558386 50869819 418010736 849799055 24786937 559255885 435820654 88839405 626927468 609630628 405209576 483980064 608141926 481670746 565914656 835931960 961810137 928204215 64071409 81 320356796 49434597 82991294 852889238 32672062 136291979 603867048 304192163 842100291 386561371 547275276 61538599 37650911 528682417 714109252 791762990 821741717 49527085 476244358 780291587 62040522 361532988 748778579 483582839 439341017 323366598 222924848 313674442 516132898 777714306 61555512 322049190 729433147 617093259 769644458 742809740 634880123 402622108 504809221 940072032 423571441 719040042 242306821 427501097 435478198 856051945 414069082 481082049 233307049 156749209 985017010 717418875 91776147 408060434 208443772 871191941 733661188 118967212 931577187 300988825 310692194 302418031 860815185 908240634 117131785 163374879 862955289 573715034 567243490 126185582 105865530 722074389 762511857 568369005 82623068 437079989 214956807 931389219 391300543 444936441 374056559 75 218847132 649388166 814588811 676071686 2449787 642663101 497400985 304841449 697677907 103003033 603072216 808729286 214687839 999884824 240612795 727030279 510749893 556322501 381606077 390146155 152374804 614104692 36190281 979767954 829180290 183621546 637880288 300315070 18639614 259226318 283841878 857389553 442009075 864626375 559630844 68926075 998088709 157883120 980198705 722319335 131876263 677814579 379538162 803897942 578985715 631627308 467013902 13598673 231718367 137502199 30718795 989571546 884669383 988738650 553525820 668453649 904631828 682873111 831075908 605164291 330829513 144067365 27667777 238509365 974614820 366004440 715756745 446155155 462022820 577669776 202041230 363479121 280515220 329282401 592663164 59 612933559 845102830 941170843 773403677 172280800 912738142 964844108 300919295 565820027 886101535 400077016 44433633 947292274 135757556 220236478 668231978 590199624 349278980 952854700 413323723 726532436 751166282 84717699 376316450 878340593 817542257 304176900 942303115 567334175 103684298 729028975 344767485 950528183 874450894 909808816 68162363 720859003 935914014 709179543 64844940 210265664 153090004 55185419 644118928 656419954 374058950 851438372 800857113 396622626 530123753 40195773 369441385 15113739 255896308 151011970 331946384 590579849 466482026 316770734 57 169413075 71538307 194850191 779572474 157741262 972547378 325141263 61687729 289041363 712530239 595794417 519685133 163437516 349298320 894795394 70107863 579701524 78897011 850889964 882878318 470071008 884502161 365484084 636935771 260806247 761131297 585239634 769678467 374249800 699085717 703402694 581680488 976743390 552990411 836629726 978404444 854696149 880644531 703750957 175166519 607963304 777205010 705941303 624107300 528671771 887751176 770287992 820933629 70872029 900603768 399332483 517242321 603992118 453398844 653628240 173864493 934359219 74 863064179 147276725 101747251 523085691 164856424 837944291 265383686 134831623 754744459 571588891 742392927 656683909 693411384 751293545 377100692 870611459 826245015 526599674 55672375 790325197 686896415 682355940 142384749 384497057 320020267 394191681 378817511 125792212 303479282 973969687 23994696 546478410 505956132 148402942 195559209 663006965 507770269 41830523 986682910 873819229 601018008 546684542 320437387 966280951 313163702 806489514 272035502 390955695 400084774 97240508 474703212 219918927 564310707 254082184 436645756 62597147 372715302 748533659 390111646 894263825 428658251 166342272 569929099 363305154 8038472 394523251 961890686 689761120 279681742 30033200 745465095 176201904 417517863 36829137 57 636252369 808086460 550236944 74676225 51473032 846386437 517694900 973341440 805167189 773158377 694201158 978353439 99699695 230135428 160345795 596110013 305545682 995647764 600794796 549275517 109400847 202337745 282502614 47458525 203495725 475643217 619295066 160161319 287173066 164417971 765187505 667760839 55834057 935814558 435285763 799863682 284568256 149117524 554439901 170676090 890207370 877182501 439495941 725895421 846710595 185311232 163993158 247381564 493024307 113467034 168484213 656041006 720852920 350296293 765573914 457430233 590057637 91 78706807 312323237 179136939 813955706 367220179 326751430 766462558 850431893 47281855 795079911 624508294 244549125 266270111 110314305 705671557 319275037 569599675 206321490 443273211 601026135 282073554 51604938 674766689 935953766 359258311 381263538 322953215 668104024 77436160 949729688 143178114 132109901 200379980 67830628 946364878 934041753 125413871 53763407 236065735 681688007 85588056 854258688 855288453 290094195 390904438 561346446 255686794 940666721 943828583 665475034 527608420 531353857 234689409 336827815 488918406 235744409 229365600 619541564 210963869 414080229 818549500 784015373 430553003 834148862 782329123 997803056 646791888 282380254 850374497 835091882 102788596 845725840 562942018 971625279 130440809 171303110 554453400 579426817 179079355 734491058 845340105 508846728 264491814 89081280 709946915 81446807 839771645 123708982 342291884 289087355 698544851 51 433516946 283127516 69965172 573087158 25532250 638028893 964465714 370611925 761151405 11438834 393912325 59822013 385673965 730691070 107610236 749735500 160562739 64324311 106237064 517207464 684388329 228001568 768221016 426546574 153809048 895275022 707736881 592957887 823452753 795432829 701494738 730824315 62487391 928779482 367071298 85766576 742893883 521012104 696401717 270327519 165856629 443249406 68407081 416171996 871592176 604260707 848909215 345033692 173408013 394643876 358833439 55 656418191 795733452 596323215 88040322 948854129 344671337 152516979 941728602 870529812 995838375 981359447 593808043 908219938 485216912 444432257 259398548 998600348 502543938 851923801 988540266 232135808 332651352 675850912 126045918 41291909 459360876 712392256 371094453 490416557 848814459 168791473 618930682 43197439 641062404 372645882 333547416 957016582 101003794 48306280 134748022 465121805 174218611 468512861 944833057 787891755 946646562 878251404 288252648 177406519 440365712 16678628 116032292 392259236 185175429 745955 100 4077659 657604429 722007394 247372408 232951341 569569463 821467962 454100174 439070309 875475807 285094932 754671736 492904198 516644302 580385976 840455317 960089180 486046758 635129547 196292487 903429319 326447461 398767908 246160049 713061448 449462245 66449719 368521664 924980318 420820708 202651221 358485899 764832980 17483212 388312918 195168573 436937590 704197878 370892973 936769429 810163867 680766256 138744644 700925107 109547938 176331056 887412274 117788251 820244747 168609091 452458293 748617023 862215838 549936699 436556945 513991587 88680639 717686575 844245914 230117250 918269022 315112043 706586997 189816121 683883641 250171510 197288509 700614894 279230129 851723861 974902040 975043045 722110611 439884843 961237777 618528114 972062198 459824959 471516386 620183901 358844994 536928838 992485866 956352223 629811348 977227921 159574706 863879380 303811211 160509310 719530832 12787056 253019629 523262614 611901344 35410489 467306361 818632776 499697204 162932193 96 889492422 895946195 747528685 685845066 384730583 624764378 411370433 822054268 838966127 761867877 414593685 631104989 236469484 433048833 967750435 219526891 937578264 385896031 26114043 471393430 314727725 776564672 918645361 75990293 303417654 433905391 456256733 363743514 908874273 235862544 426962272 389840733 12402798 256230614 319540255 655183146 558490821 251907573 504215016 978152822 464386792 134866985 248720372 522846674 516132706 787843871 258156665 48460851 572079396 419066749 679006038 196352583 609730015 251682411 5718878 525420097 746405591 472332241 870766564 94284301 924399507 236721458 351547297 588345371 873925994 150166433 873147673 241363245 597977569 468122639 495855218 880550868 221834716 577856679 810303602 326417433 376461915 754840787 149023557 644497632 953179246 113110018 267848713 896588189 924386297 565452286 514051701 102302711 781341591 667806770 701973366 950392474 798474106 893003672 352718610 718891305 66 165523079 513999134 27145605 454863010 296566847 314180835 6147034 818238683 962907570 561414181 374213374 196825153 961083254 455434619 28440175 439278793 411316793 527836685 924720092 940107389 727898457 411929756 760677608 656032430 597733085 235526069 824537989 989213147 71393411 929784169 997091671 509726777 99777259 198638066 735840598 148325900 378048088 709666583 972300990 392465051 259131023 471282682 634050444 437541346 75809155 765920993 50391456 386612657 437707845 757912755 506756450 336201467 518532435 93478997 476655168 48650449 815331639 376065172 629452739 831285449 852981016 175997798 78210726 202595952 775516110 45274073 57 565778892 972541121 596033400 196388959 39463950 293936811 753243095 658296617 177430075 802553635 843120617 14575080 648744666 27102701 13093569 252439162 959863399 475120493 480490424 969110692 420243684 928393699 674095885 916442266 467915986 663905298 867996432 847123808 623967001 800876554 951846242 188024859 59570553 625344403 535226349 910886835 385116754 765399856 955359146 324153603 205334725 2571847 898802696 246773976 506063892 302219548 229174361 562039817 811499289 939836438 28336399 686570544 588400194 687602602 140173567 333247836 61190727 60 140251450 532124357 550200808 423651040 431135659 349889494 790824323 239671349 405842123 859749198 556712757 166543875 719556582 859308878 459879850 601686467 239676751 354625612 472341750 237831010 934440397 793218539 287867265 466077260 207408022 378991098 979018060 606784473 221980530 992719849 56490403 243864135 271243237 676758929 720768152 74100333 379426991 301044531 869207807 636260887 446218084 173661768 656199138 437673625 717780135 109393956 478855255 978786128 994514884 570258326 87406724 18355996 965173891 950247901 418501106 242411441 454945576 589387906 666604644 722477577 74 646664197 456063333 275218730 282862957 930658018 390089389 995975602 493939980 342509246 168640121 635269794 21105124 182361741 87686568 615201815 688941185 846539812 10692203 578073815 307920975 269404996 655514556 99059700 965321278 831756409 598921277 286875797 343914846 761731246 322034375 904171629 297540450 862530387 688112521 172647105 85404039 106847200 424773453 299991414 833582254 292056893 437427384 189407328 135478573 434572243 482456236 820789694 585784739 352674341 682826518 217496361 96127485 85227218 232137991 395134527 765304705 679479797 436566107 784077904 475071535 628068506 987348744 438731417 66371810 983713844 828984015 6755919 881154549 141702475 874897920 662636321 366656856 264704488 739737497 51 528905808 680317210 885745814 875537683 729609373 966622449 975766197 124064833 86943460 931302559 428673930 541635945 583875412 881286939 614695428 977247967 146744429 453123830 71471463 895220696 811813474 438522284 629671552 407625366 840628333 587993473 119943755 883231188 658729620 830851123 430852004 615458250 332994357 981950663 644246620 399281515 145225674 9209917 730710161 731812752 630525864 221019632 617542335 665994293 72333505 676629673 174383540 526966047 229193169 622316879 656131341 89 88542183 192156860 191007143 269831229 976019295 770880895 613829260 813407719 815177856 723765008 361676062 15301270 909122346 964568924 663619133 156159863 891633746 412728529 174627132 636891623 297641424 592836181 68888066 198626140 225355809 138335047 45773800 887201688 869107639 114527055 635731653 291811351 261814168 712339564 923962543 654975836 759386854 675505359 464277808 588595339 701071325 10496015 887748752 797032364 71285298 976630520 44452130 521806526 801693281 438632795 929942459 683764200 222355098 573384537 764029674 763555634 86029526 86953506 227317649 577922791 766013303 625067686 622984577 537282180 938698835 48786862 847783102 87337641 920015863 874937511 141275842 167108430 845130610 872557472 475495630 752605615 357507600 342750926 588417163 411304634 425382170 741267395 618247500 916542456 637254792 295172510 59751143 636836954 753530948 95 228697342 505262928 775851620 197844204 858774178 512623602 813597202 197136072 744644629 556319964 844667701 798987727 225645185 179084085 238611430 803405522 715719631 487956153 905762906 528213246 790160097 369559674 314359691 321460097 448137304 597165783 31002757 347284454 594909575 994906570 302709974 698207436 909949074 888829125 360780808 109776371 868695791 972309343 934293943 432076112 533235626 134899292 177582173 602310011 982244449 450120073 328555115 466497801 357092080 919453791 650672284 315532 778410423 359839563 59783 44021331 619971328 588859443 154741281 100535881 212367938 610085813 302509262 347677143 901400509 207341166 746806097 751433553 736290020 253047776 774131704 943897476 154450762 665113547 853169406 992153335 833440418 278658389 187040345 353098916 5702241 439386192 836068468 898135605 925368789 876110012 310013004 357036653 394782460 304204297 534032103 309006100 340828133 604764951 656775012 89 974828743 750579430 140302979 726079506 868980329 333959589 571916304 319175317 849480320 689106131 749619642 2239551 266647114 586636796 740217770 394635454 185010259 915338140 178417118 728694690 240852524 177732692 732078310 582230390 808413143 925963868 256523109 533609683 117391791 443870425 945104349 262576892 187584127 111398363 157426579 689697016 878948537 216781215 247871818 131831303 345281500 263032354 163633311 391243758 140583875 164283934 160292894 674821962 352263592 432089383 514226136 198871417 954647637 149680020 616846824 99811264 373434393 382039926 222843219 994795731 383011628 297962468 831228638 173921728 845812326 148205642 394564780 246246876 60378413 244093584 537728886 233271031 41553771 34656859 225834223 85492452 498652865 889367692 437539152 330427 79046017 911705432 837191290 859336101 394778994 426319369 824880152 727173288 799489825 73 970913202 618612056 759792058 878055189 383172929 273825609 236455462 663424875 456655040 949754020 851485921 99066799 695968706 817763764 163877615 952415986 722010059 669590503 677874371 540802799 715210924 77374171 379650641 735122156 11626318 573083570 936551128 422805235 735714228 340094263 50138814 452972438 12462500 550194619 655244809 800799501 580075896 227671240 326775024 974416237 363355645 43696586 798618556 180435499 508480512 860996364 983964557 663851379 720990107 670209668 412892 478576608 693649324 366774135 30343614 128516995 631892390 822930102 485349478 179395257 864856097 282425219 576675903 377600997 470972215 278584818 289428866 890239274 199756381 569085675 654829251 578148495 154993045 71 727657339 679246267 591170989 115232227 22058934 726835310 345200297 388211467 541587649 601359711 851743728 481150907 803096007 353909527 742675194 999731781 284247664 759359671 817425310 510060568 894724264 481624203 588938818 155808337 348783833 664015397 4701418 95582995 530395213 236641098 203919827 489968512 114910143 213840270 722617030 647825368 112009416 215594686 90539336 949273764 902752778 615353072 445057743 4623064 251023531 451531935 925624400 493152725 688517208 527493239 63843138 972140009 728988645 486374395 210320464 874614780 287005150 368621116 698787502 276186058 458236096 338750615 66656090 642838712 2132424 431153708 520991681 225956722 676378648 424915631 829506519 85 507829535 581851641 406237285 831214120 561010068 465780239 265262528 408949618 280168933 282796716 189539993 360406551 273833982 515520236 653256732 694368653 282826654 102051594 292380896 263660459 887820005 35875383 728577370 389556096 298837700 153861446 905424260 372918115 459667557 895812444 635245112 965813785 897860699 430038762 394406692 977357970 48792440 643747572 537297267 915790216 29417894 432151793 120395355 486590336 922161971 481545837 233740477 809424429 924091370 236123299 543500484 516017980 52263492 672557275 498531559 436798693 376556353 718584306 302957095 723013426 721673475 309028559 609149467 90050620 783848337 887314504 599621976 852749986 902202000 914499713 590806904 713550818 987133150 127438240 204759524 861071961 404298474 363162233 77619794 854812834 244547126 788028456 856589456 174420184 152075269 59 347863919 851357372 212199667 719811534 156740135 979094511 692452399 641660717 811445753 779545386 104758350 394297599 432940355 918980139 759990979 99640107 713281030 883852020 910144514 703492885 394778934 179631382 752140350 859699665 102311896 968525430 62709346 599888796 167966641 177632887 110559272 404785426 471694520 260477783 331258610 477953561 504011076 947076386 277167794 697903537 132178100 547018948 208491643 401393532 58149948 771665117 831200916 156902587 469678667 945914321 578906352 991753699 202951502 623599023 648090964 918369335 972421404 302311986 658240887 76 97733819 253384832 768656974 2709918 647336389 287642955 391777881 656573244 652478306 446331753 85739808 501325312 428091672 445153752 312004462 483249304 865383182 832730237 313359512 261559329 446941979 939232278 823805180 892540764 714125562 761197584 823106265 350110428 376557735 143057710 209564487 155993502 290527172 130463259 412013759 261346185 16711145 136373490 901476007 893774330 713461958 757166064 844209457 391193197 638061 550771702 905374131 466484866 616733328 856874055 860764779 520605922 630042811 827973531 39302791 96041351 786246066 650517425 136832575 952154118 726320737 894921769 144525646 314910455 415754427 529935381 464588078 120663872 447249654 9088016 132012971 916173036 878027397 971942571 27389700 941546953 100 324483114 299540609 130179715 516817370 283831400 313437755 537814986 162695517 100646420 607484168 179236777 383180356 658676122 791424494 181876755 505301116 761075420 966272374 126818549 372090638 882184184 556311678 45474538 313805402 777771483 378827213 602434486 573698315 643279612 207280686 33714533 423220028 615476560 858584023 215784316 941310904 251326004 500517725 77803636 760088203 199111476 165208083 549374261 381487441 770755083 700382851 193638876 619081474 983267399 676313440 978027682 602559829 220065686 812311420 867426203 5170546 663431662 416760625 629993054 580216232 371271009 124743048 449233291 858631379 548250709 549054309 328584546 253866611 184965843 80758286 226611142 279046802 764387136 342713611 932768292 92099459 932127731 998911169 248068188 765047102 410776801 261450892 795677075 555983837 510108155 645304638 698595807 667320850 857363701 798922908 956778994 245797855 243674941 435690149 349279200 908385675 847265901 696683652 13623742 256373767 95 496369592 115229487 717099365 804919644 24778075 255478655 417747678 150463430 427107957 687599269 553710229 542913494 500079665 871952597 496104435 648167745 466848218 280155953 442143580 203656485 497261799 32266523 201849936 444148280 69924165 317853769 954201300 384614835 44243885 737474451 480370936 459621334 525056120 768571838 789513222 800992701 251725777 639206777 768958705 36888941 556864183 296681489 294800367 159341541 540971726 925717981 396579089 679325322 990466472 294685163 202120243 918936121 208205525 944489933 489654229 325191619 413124796 56613579 55921373 538434059 570910710 714484571 21745799 77853509 936832869 434700972 590264215 35589207 141685659 773647102 18353293 872191183 587034206 937687391 325072902 649163200 558950838 482963004 277216025 80521786 462599252 870608024 930998019 208984613 741555320 901977496 356781062 717621741 545954741 274419823 975439826 71111990 664412699 137342977 463009622 50 297970041 910649098 330087098 671469214 640740822 761203161 601634502 758848002 951964217 906537705 996836208 49694147 365421413 23473894 594700181 124203484 96293572 514263181 939126299 549264611 967386462 74444790 838652330 94302802 280828101 90945172 732537599 418555560 213169595 865792500 247879938 767416942 918314051 294580560 119234585 234793250 988396038 750123884 116599686 525229666 542842448 685116922 52592552 533860382 295732551 183295284 760011807 503057358 352316081 558048371 93 686991387 388225621 746991158 899240311 135658484 487595532 304189931 639022485 857481717 297629895 654242871 396415229 488140243 527668454 927020921 358522129 801832301 764845423 398102406 100310408 702285932 485721300 541047256 228364306 224932809 232517678 561722068 215709050 592758986 261918710 66788371 440727635 257389095 72722937 66826242 708908957 727186092 408243811 425713711 751626785 588761831 704110186 44104479 289360131 830930660 591947148 374914916 878686677 242317879 2188143 528145975 784491172 909078635 897946377 879674429 91471034 806193860 256233896 838647955 742274737 477339414 293042010 789193162 918581156 359704455 511171354 426671349 152048174 679862662 624282549 647067959 766785551 117021031 168850135 92179444 873487517 748334745 357812837 241204302 618625855 640267520 348288373 600897667 399119296 978495159 839536685 130130497 157219493 914401981 443297941 637681251 633000284 833096220 53 727528539 553787372 869671679 179134274 759335355 396841664 309996633 18273558 511143779 637521367 995585175 473782468 318767851 568714253 928968054 677199288 139378386 133602759 665712295 720837970 591162002 95519482 847538279 228217413 896921788 488890867 706020329 835744161 918787857 33693681 927289874 566559994 787055006 630929433 321538386 818810155 307185693 384350046 997722939 438767577 571133180 459276612 357675012 634160609 110336438 76717009 175433281 394613986 343798509 205387090 15533228 922254802 426861799 63 226331295 419792813 241972221 661853065 666326672 451836374 133253460 31095409 863444888 200259653 322926870 772355388 417595350 473375985 710244980 450151875 132416671 242479073 76208527 731547616 379931435 760845849 814446592 248161140 501356529 847146804 835603188 230408396 858770196 896996585 826549120 434592600 752690835 924971839 246987597 450550014 418718080 999848926 491978010 906047622 104922754 744007665 284446758 873770169 895781551 638325127 400395951 128445582 157591387 140169090 904151655 286778429 627237138 65106177 937137051 736888223 601396290 973071697 647190408 60767319 554020394 984702787 889349561 70 251591045 111493071 843344640 931852027 567585695 231492132 857365910 928958492 218856219 171383485 967577485 624988654 181382369 229504152 557157279 759996505 343036277 731500902 118596103 715969515 484687473 272245865 954578540 742001483 754430223 480612163 118395074 244730026 105368858 357749770 850503052 96465996 139570119 131114232 869204461 790074324 784846703 792317139 146780870 82491462 258998443 333201651 827872324 581985036 898641892 801795153 131405107 814190958 692396159 500302030 39753349 809928071 483477096 984656416 884988764 409484750 730302479 938412786 932942632 152145505 142515308 735557248 553266906 877113505 748168465 50201547 539677214 489575 216314988 730349970 54 536834458 500562135 1131128 56719530 717271132 824224206 632284126 279265782 135652238 830500946 344410681 291160912 38109000 358388675 814757581 899664268 849280176 619958502 261354749 195940147 74834442 506365633 600759325 708311850 254292333 352950839 730623055 17539647 600903304 47051114 955489225 853375647 303736124 584102396 869836712 42225252 519240592 789016073 276471548 946021850 219987153 217142568 142875918 560538688 676235330 26729732 139531204 387233313 902909511 310356468 645966287 198917220 457570726 995752664 68 650546049 593284935 704089146 471211466 394358648 833261942 524810257 107098356 372857179 182776389 796669660 803010942 256430425 645012510 179052013 830434479 334288370 301671379 413871480 370767985 381694454 221528915 609988673 934576306 921846739 771963211 72929303 396011546 937647968 710033191 898270365 191637406 653920354 197501157 494874002 305230998 823790975 954271028 609329178 971828416 306989516 734536070 419432095 117948965 718065872 562270637 107455681 957329213 944417008 267790125 427274817 196716701 880876446 168877425 715071453 306000682 397329881 119444721 428314597 541501101 108117516 53179788 509184321 6309026 780583323 255172917 495601389 417313698 97 726054119 190199741 596468784 151054557 675835529 153089962 471436743 802457389 157152052 421348909 908472568 838811588 693024028 391167565 996155805 412656133 422249509 802024116 987476656 675737978 702282709 908706293 540657389 689254035 856589237 200414036 510536981 639198562 789327031 339927291 311347441 658582192 271860695 676745457 621348143 730180865 573235568 848611944 378708863 681911787 596372722 524669522 15947693 976219208 83905828 593372849 276988531 217241024 495522418 234287480 237935285 703312937 41465189 488203370 250049068 18884352 371951958 203944450 65507245 106519852 901905281 796359434 720808239 634826949 790742883 181423379 606087269 794748454 259149573 213676593 920785026 448527369 223501588 459353337 768279886 484435936 769711992 877735290 159587420 644255420 370620172 339798095 885485692 313653557 314379273 731784434 729601083 908744255 684998284 145186031 513660291 749371495 398436972 533850714 982117415 96437539 487330321 55 99441120 632044053 413536306 212135092 76620688 405607696 540816992 604936437 354975117 289905633 301846585 6311719 822416802 868826100 272486589 156751341 415911155 113899829 983495234 74629290 552870455 111637735 807526461 437451065 7022496 655600040 84903139 64972773 62908866 244463866 503571529 981628283 353723178 94732436 728529658 230084585 488250294 318959317 60088160 872999969 261054941 784927816 328008460 600084867 121231922 279291974 403763005 667759820 241773858 230589996 727917148 215788410 791949360 2547572 413985606 52 382893353 249863484 636287934 711867456 252696418 863777232 788680462 832338728 481789483 604071862 494503072 33202636 595391654 728622323 279114582 614813801 181876981 372354372 604005757 258735954 29280031 347673767 690109102 952481128 186415354 606615977 768171677 810851328 860607658 824832459 817557697 981437040 156452430 528445800 960291711 995874102 487137084 6385613 141001438 817054415 159405553 44515851 454726364 664241627 116136707 732660253 737417963 701739518 7534965 606697957 609733739 109332971 83 727639426 468786049 965795696 170667964 536246301 452689123 39879520 297038386 97843194 288662822 562612238 524380959 70343181 956760775 792182803 752176685 967208803 678873687 424678990 836225404 718645808 643931104 962652624 852312950 637854883 890421996 960293557 161949418 277469114 501975288 281285982 944666450 518338556 470565955 438092118 289973229 682093198 210549670 433668478 679618621 792834259 636301504 348954648 909275625 258525319 55646772 367506326 392393403 128823537 885450482 972711486 5380788 591947928 545038569 985544855 426295879 719876824 493109043 359412172 858680520 448746038 198627230 706443957 918353303 227770735 886536716 771002779 593177859 960078617 388478121 869122851 884615710 899244420 972252793 234321973 551011879 128109683 183409390 711625957 94797264 42631072 274750539 309815547 85 358187951 833277163 240678991 281498959 965479259 374773328 357082962 610182760 224641372 203495912 810462360 606040682 323272483 699511478 853793796 314552200 695714017 871494955 122617131 472723852 327488986 166316269 667536626 926109971 639305163 666182652 146819848 844386889 15513841 814859940 618902503 36993096 365045630 410204572 677945074 109260797 65485581 324894950 194633451 880503985 339856853 43287584 719275099 354692251 173551758 179320728 204190345 799488572 68927071 461068289 514825657 197625399 708598169 507477513 699389031 243294024 886898720 297374808 967292859 944070676 403662912 139453014 789672964 918614250 387091411 596445219 424157029 306184271 766564249 159587323 164190721 148030109 473337992 537126988 918370368 480317166 666593046 363637520 535732018 667833524 121109362 160418167 750128954 702961287 80486577 93 713409768 680649423 390242364 530239333 714118296 318087197 74354978 468805647 99315550 934054642 273286353 465672714 314294103 886993973 816449072 992056663 427200470 31384059 567245308 562104725 363002195 380247888 874644410 965126296 672702761 119709856 539935247 877341793 954239982 735876579 920470508 129254523 662323912 823750100 512240342 870338247 603267656 140385960 168832750 218529590 534316709 785219604 287894928 574854981 458966310 804036121 357017881 735419648 886794727 192962568 145644643 758162427 747011064 399563437 870873470 77655401 884715846 595790672 881227583 950382838 950653725 828156818 316163321 689643628 502907596 437754564 382072295 202414212 248747441 33907296 522191321 845949773 880466075 240444184 299905467 603961265 395726124 966904703 572345241 86740245 654348284 383401645 781226896 686591752 410146506 381714248 771652891 697430037 831354298 349620204 761359175 800591530 914665637 60 839052823 671023520 102631844 838394008 536696557 534423547 917759910 723221613 892188062 868410002 688502647 77418087 606395387 434545131 711685857 840820379 828583352 603653463 369061230 571797202 707869560 582599301 415653253 485557312 22376649 311190364 167887951 878456711 782274599 66800641 355900044 600946924 185319813 577643256 692668761 245148954 819944185 715414006 686032488 696805544 942144281 595720352 980495887 794598668 541886001 357500169 839952041 184858069 836990505 484899904 997649448 905553635 440254242 676111248 167357303 661196110 193730608 701791603 68042687 370891135 54 327951930 233879084 615508123 234352596 881546598 548624817 811937363 154887541 257776943 42085005 772209290 783431037 755475057 43267390 955523042 817835160 365851969 996976317 736820897 846341554 748991496 667620796 589203527 546557947 902467676 305148002 962074844 794235819 751976539 658866722 863850554 4302708 139646195 845202785 218253509 10794578 544861188 660782970 682016926 25714250 109080387 263534307 150631614 741031660 346992955 110516137 135913233 590351438 516150417 515162929 593604003 74662927 910929171 875923177 77 696908704 293095911 821749112 819208496 413873693 785672020 803632760 544613194 576800641 851623759 6378564 925387679 138153527 965574889 171149022 590892493 697195770 132513906 544361006 750905564 813195508 682768311 308836471 601118581 350545324 355567487 276649578 811615283 333704949 588909738 304895234 278339667 326480978 625909065 959857731 201936938 169358392 398469660 19566603 603263616 70939210 130289236 345272333 990251290 959983174 486644073 422958209 495567504 854452296 762013732 536832046 943119368 428168942 331685489 378397431 873003854 324854368 330887530 529083466 91873719 33787605 79096288 778084924 558982112 59092653 346829255 704585149 788593422 412124156 66671099 107482929 524753107 387686538 796374454 829835758 986830678 567026075 87 226820291 321065128 996051907 285899528 840636428 671598475 215291543 846852811 67061359 559042290 907750787 183208681 196194198 762740763 173294987 696329895 57411534 404579631 888170652 984968279 578189909 44154390 439285746 669941126 173736498 762841626 64436965 164660780 382037575 663606363 891784309 915049421 19608084 7021758 892659974 514597052 774875839 423149242 140176380 30745754 224846968 734537553 789795527 895011376 144191212 694595428 293499034 176169191 465818082 927429980 389981639 383513199 339508197 786321572 519993264 194126485 503096816 919441469 616057918 274542060 450437836 8793610 310701481 852209215 145341273 354625161 782299414 560897533 516534371 637105886 436622866 581994113 194887427 353167217 872932793 508007349 197746481 163625675 526656218 538676246 48323147 233656086 264209921 70151046 217244366 812253948 850813575 65 101409684 2990416 840091211 429506866 2947007 640438016 482975062 908168612 294229456 592507930 533808934 341779080 387073111 205759917 703334623 179179762 537855790 685800148 918948608 384788857 291522743 636343831 215775316 817277495 566063579 297290472 16517278 580886841 815753006 813237772 518004422 403605534 199991352 538370290 851743017 322922631 836972224 67699558 592586635 417174076 234784756 846959405 581716205 249727188 562635477 315809574 924426271 694085097 368998328 493362460 734108314 827286434 225676177 278484660 846891044 988382398 878266038 384294842 885226707 830326390 270259940 843701219 363063412 634486787 833709645 83 783780066 109494810 200885072 158797247 884087936 964494241 411655514 251874980 431721067 918653471 683218157 269004120 372002253 298027195 587904885 85436728 120137150 792144784 66725585 836425632 40160651 622983401 747652860 63968442 664328659 153241731 113423818 482681484 912794340 84048450 677349158 357269316 57738747 466962670 69506153 928160191 55234906 784941275 650511206 319942082 540049937 27948398 813547407 565502059 863339245 311501244 755595659 477223027 548697710 906747662 358760764 15388148 998127266 603944525 409367037 964126535 504224008 616141106 44718537 400927528 484236897 90461985 636903812 809978263 311157295 240121827 929978322 567123294 716763807 910605719 589469088 435648960 407247194 466890146 916680541 596574987 976162062 213114456 314874280 44061142 457974289 678508458 432417912 93 158933676 71798496 650926807 410679248 415001369 831500609 828471533 121792339 324939954 882004170 813877914 719017840 545725162 89287425 685929788 640879235 927032476 76616444 952201635 804519894 119046363 354950365 400798004 790391493 492067127 150022355 836418530 29158425 728914105 927148652 687512539 80175525 288977638 301144065 968113940 393565126 563283384 261715995 150062739 862121059 85601385 526536656 684995800 377697707 274695800 487356130 359656045 372374899 574036767 682716504 161119796 840817459 999205919 815182883 545854516 451877194 153031109 333830418 878407338 64519798 381987703 185058353 208982571 125766429 812416416 466585618 800388082 801669778 971461574 610165647 545817569 233804063 102634907 433788649 362318613 265419839 321053410 466194914 675263353 310420006 450502311 356285981 125170529 423028330 593235953 421561281 427928026 359889925 542973005 259431784 948053052 662397690 965554766 87 452537968 941363048 52177613 904899105 670410908 347873548 516836547 416943575 211303898 407817208 400034657 722522524 569997850 295569683 26771264 463549504 430411563 84537913 146802977 79379964 487279281 786232649 54467594 876147329 960639913 414277950 368237847 239601352 329130173 278276208 282777329 757776633 774762890 391912088 127146681 909788215 126421814 637512398 953591660 69842423 952607710 432178737 204529098 819947711 544439575 614651677 823779073 142810996 451871276 92142003 119017360 266113479 529507512 213838045 469844732 545259281 129819857 622169699 553440688 608898519 467392604 790110963 856165801 475202096 821673219 157305374 798796299 91712894 532741719 602578843 870758988 21828601 215044613 59556722 818934863 139787752 281939321 447290910 929893418 907445456 258919432 773654040 915175365 458515760 637152738 591281774 73883308 90 633363298 494053780 413528060 55625540 955459993 862550903 379073158 814787345 976580626 153584099 139623055 852857375 242071276 387312984 131288050 752317932 42376397 307311465 944543719 567401622 325049844 784082964 688616548 381055656 474174736 139067559 304926918 493701754 569478427 335795267 258785765 474467659 6801530 516707955 166766450 377255006 756349884 33403428 917849017 725956354 761101983 453105903 805435278 522305876 570959085 760297907 952534479 512965347 815730330 325300428 647207175 632918067 270852702 537258964 666785348 72327399 609809768 823268809 233961884 932599431 799263321 271756915 389438998 678959591 328187567 444182298 871937218 752444094 520941701 728227392 560817032 694208786 45769546 800295125 696502851 207806163 566487340 235648491 288446113 440208340 67915319 157680969 53696785 401008807 490191294 539254217 875066493 262202301 789560360 999302386 98 381757621 365031526 115930346 948095182 259917887 763555186 212862259 829613653 416850281 538409826 266738287 805348510 537360264 580749691 766656328 634575990 802195097 969506354 851017975 655368495 83735973 74133669 928684538 131464290 133688587 84929784 625609877 157062624 459966132 926599722 417968150 857368627 101614257 818928780 159445893 29581056 515193568 814439030 928545168 155169240 785995393 753378534 316009015 827898375 315262400 823419372 172559074 703866428 184800240 533747123 21147467 612720011 895943858 461001312 927916736 926845270 702850925 725508291 921749071 221411804 71329454 951368722 324964270 90970436 644754656 819257596 897023719 991896985 243019749 759844447 859809845 232355011 31186212 33105503 372150000 286274952 560901060 624574319 346245687 827416353 142941158 644866984 589840608 474389975 18240174 412144673 758167730 319483416 506925441 189744771 638523892 32651603 42793099 674729688 121354369 208843696 158767088 162200056 79 292216152 535545159 955675100 421194276 725488895 166724269 948211096 753989544 448929848 5444249 781876008 87320854 501806150 716310334 278440665 940647145 962617548 380789221 534008336 422665853 692427932 363702214 106843887 653025194 502652040 181149128 946748974 355775202 308106752 942864779 835703513 113940428 45069810 424226249 28349609 681969997 419893198 202516016 764642009 43445393 738835939 87081879 104730607 85126416 41609689 837844291 887160409 557262962 269671 831702815 847654951 314836931 717099464 291329834 409499931 359616955 761188160 503876758 969181286 866228598 136602341 275260061 725538056 230990811 725296649 317383391 562853218 486212712 774005217 425791701 373871047 65052178 228337014 902478944 401992657 894194590 635349455 281830890 221991394 57 309416890 650793031 808932322 980328189 339607900 461788702 545190301 16254529 613789502 596229120 345614071 87105931 953205800 163518202 94284163 268303503 555787150 706293623 741820669 955790466 823536926 456341021 34067158 322599872 754529115 183867251 115254214 777943054 911606239 217169464 271192348 597478573 172185849 729089682 749997509 566859679 251634981 561685636 486069445 43379034 378876279 962260610 627533527 419298587 916064105 965887195 34241284 779439620 3534314 913763393 148233432 844342788 612160268 849214156 696318264 627401124 968061225 71 43856199 211052376 72069306 709606108 250890445 757929936 867894599 494344134 530134726 397675010 731717211 660107214 274638005 988526630 835291866 26065996 136623272 975932463 638978707 989586761 322981474 290057532 450211152 4689904 892680462 399697470 219189448 707490933 73200304 476194950 615491848 233291269 423572357 108669274 388661727 305065203 120253692 893404698 382163464 635502337 413681232 890296267 381533374 794522087 854480546 230605239 222661262 442672479 648452452 896572846 676846753 186063132 335509292 301421355 793141853 778365414 697534461 970183279 315660513 536615754 220398106 303394914 595053183 329982625 296041740 531713229 486903612 352542234 654167969 545948855 110281187 66 503080315 126703228 474229218 11895231 539150477 12496197 836821522 270151951 577663867 723581830 815964138 867221744 60936776 723257455 457418600 489966187 833878192 988930794 520662944 514688193 457359791 412347251 127946067 270177979 384903346 777972859 349510002 66429144 274598899 529437908 977610002 927381241 84272442 909205854 224691254 373925025 498791264 338413952 804097398 773807024 813935429 915623446 235028223 757007501 98790573 952062074 727842412 761088070 237273644 380206123 210083627 712409739 186614917 756919840 572337209 338518121 474437178 98381528 646073023 318699829 732774190 264984317 662963061 532345204 376488146 518410791 52 789949643 485601256 424808967 488896743 552830651 876611326 318134791 589483695 955769366 835416521 621045172 747726055 98239548 858557157 350339719 499766983 20849206 925445975 292969065 869277648 242763345 354196421 56595362 270693751 766475657 625035169 451169361 365779869 905115795 381825425 341766076 66524502 49767397 478335839 790684385 283235493 917073502 363895871 457514073 512424555 848111730 377726880 845067093 982278108 58864227 169999599 58361990 264185816 714231901 38350123 830138519 35990342 64 479311617 936376754 302313033 31469208 113676276 696655701 940865011 42600255 328447879 513327706 792546286 847487370 538883403 12229571 374153816 195630334 700424606 852371873 711050121 206169307 873303610 820345350 31781737 91981179 852036936 124673041 502779779 347519194 270346469 97381561 586482832 66553639 241681617 701293906 225308916 235035557 987996419 664569454 251741247 636569481 588723406 702803797 789579987 76177834 801771872 797953969 561877403 386546097 272994571 378182920 859257662 257010075 816527477 297437524 631260660 330666241 968106278 458051215 75829744 495169765 788761654 720414556 214778728 279941778 80 908166870 300733127 90485148 964024609 630368202 41133779 830643996 108564230 141255808 139851575 613827671 904421398 937310106 351930105 489714299 452791316 156925418 755660452 208126550 980811043 603575120 371885650 558520865 25568518 788468576 726326184 916654799 73132197 837692262 767898415 443215851 953821605 55636220 295953165 786516591 999136343 802842393 823400112 292403919 995312364 16323964 576456493 430794298 58776517 688919588 802301472 484950469 765157705 644026568 516618126 172323255 990340964 246963830 836021472 844822301 49573874 263735961 16865500 322903002 253854936 219261255 955643343 967960128 216283851 108565683 277053504 671863920 68844465 1632622 128142818 574126645 640713592 98869193 165982587 851002667 210568316 272583958 207734095 753608517 829424774 69 94550552 123077197 220526013 202589026 428218504 583525979 643483433 244278361 97712908 705807366 269305236 723065976 497557157 967165677 23906225 791957388 445849696 772573075 177489988 700652804 123111024 789322571 604090486 379410710 684513108 485619480 269760245 950468407 9618442 880144063 847142881 438080083 484613641 226385 870956396 857328081 973362356 962164098 611838289 313498418 970034019 434837749 328776485 961345060 416887544 742383881 612546567 383158616 863154374 747201841 766608580 604836062 866854561 961705460 379487762 326749758 871134769 147430068 134486979 397595355 356955252 589372970 670247906 281962202 310470328 19384170 575137806 862778438 782601085 52 893337309 832247794 582918455 298776332 774401813 497367564 150123766 430550394 994801970 754907089 395355814 206006065 351368623 762682764 429375678 144993839 481225590 454060557 166723977 112645002 763212153 780292309 304749607 228209383 72380561 959535907 658360579 512467283 275760576 600630139 182503419 518452636 712907947 714779106 29242341 874476942 264485880 283076342 141401610 460990432 960397410 444638669 408976717 355629158 759076323 753020075 303195622 408478808 934027804 27197345 608660925 275004398 67 124367283 769338766 977477299 107051639 336907297 809263655 510970413 662151816 210328581 661659025 288134729 55335553 477018729 949229639 877233071 431513490 37534501 69269832 300563744 404082460 872182433 706254632 803788994 330550520 155516274 225867118 835429851 882341686 692031545 489785792 825476284 74912407 747062782 276864246 917427262 945378224 234091458 894584548 416739303 440472956 336463955 325623439 843782152 50933592 971871638 453064872 502332563 314659589 752632900 901905377 635084514 753577991 884606230 134668349 352592787 458057950 689534969 901056365 894125979 964841824 136324726 586942197 17052220 418359086 129689879 565755519 306180008 63 433462047 458064100 893342092 702876744 601714225 938469443 205471698 225615738 738882770 175451669 511792616 302023939 663892767 326383889 932964052 778765659 578457304 484050342 143076614 534924573 559144948 460706715 90318948 650282526 268599649 723306918 425060478 336813025 184594458 326875032 698596639 789590787 285439917 304627240 303018214 847004120 765756636 85366207 914228514 730968168 273871541 521612493 667486785 315703460 539356934 748499599 543395625 552029580 308585168 953486780 105980821 818483643 956808888 854616489 761289062 407501913 495557229 361150800 699634212 557106798 248214600 57343541 775502351 65 787091450 141744058 801207535 798664965 34484641 353208427 52021880 307256480 347728985 868718437 618714435 871352550 439777642 348718694 191395574 329712848 675888581 675991563 269663246 654713109 288401974 630010046 313367818 532046959 647811282 899425576 886447110 797714222 53199348 111344749 725874585 373792830 509936071 284769498 768994113 785264725 933607554 902859214 251584424 606958563 947939373 193213583 238181012 157136456 296805884 391118417 326013929 15540537 228885237 118590012 747638458 202036015 93369083 640874773 932561901 771551595 612979028 544071003 781911389 945393739 339705208 949406424 585062045 128621414 653388559 94 270418485 890654796 497067318 925447483 788527650 2540693 477908736 285082390 871834500 161301136 789046502 69005563 524746432 559363484 205290591 490930190 497627999 835035726 73658273 220083749 417728929 761397112 245698080 294576642 102946064 837997065 35389800 946682879 755558569 691540946 388402316 101931069 344623582 605495048 320691590 337444217 756315556 136519720 346813784 98551034 364025885 404675490 710229419 94917050 406991449 96510625 238590132 465546829 574346132 474060133 530375010 480745869 256892306 871629116 15795717 744951556 714360704 298235048 108879801 341352179 925638931 754365002 878991881 597015033 693421190 515846655 473210508 494763128 131272805 372158260 482192618 457306204 586930032 845816778 531147828 60084657 180115274 453750351 157413614 624646473 503498069 773135604 879664550 798727052 532925116 700863785 239787901 590159822 394240779 489098250 532540221 365852801 411343114 638550073 99 412642979 886546421 347276461 564147108 248434067 349533378 871907531 863740813 762527076 791130621 336208048 300096511 44683568 431580420 409443994 545984152 280885448 892729756 868083505 250827741 107526813 617355661 363376014 171176111 708517375 710576905 725412581 927033068 267917084 511373588 26557633 887657166 330950067 200441031 62707714 469378817 673655629 123061003 471488818 458731199 384307319 567151930 828160458 782323191 713254938 861106006 668297723 709882437 140830304 293583776 564760507 700748993 815407955 350801384 836675872 271108228 943250558 260881617 487830411 108906800 158853633 358158709 468982115 835904401 17693456 674207819 323386752 419893830 308117805 679543290 247417963 829807959 723398902 542313894 900917296 867033891 711479223 285154536 146174316 196288691 276057786 928931427 886448041 667527002 168101860 787824650 264868217 771347930 606606331 360444664 644695192 321125478 128648621 357698319 179639120 368776658 456003135 536442031 998317339 73 935774236 415473762 331139965 792129698 736089850 402989476 461648629 270198973 2783156 879366788 316757344 631011958 42024208 392803433 685879229 331713258 886498811 282038353 977568184 743184352 208521413 697818429 835291575 492040218 934511944 862891070 614667658 312836382 591466903 337870621 321304836 42932450 689342674 450258149 28681396 886283816 136900942 962718894 332840277 961664068 970433824 888864513 518797095 997200695 5087875 849071793 977080532 464271615 665302703 351701823 252091835 82583817 63945943 570008704 742188906 980833113 697628917 482807137 383085556 86394878 427348999 745291764 812319023 59257356 202007588 96612559 414720235 75467802 493661414 82249914 889666114 575783509 893293123