5001 101
459925685 555296170 247245605 709935831 735045381 372363852 831305189 894346704 482697636 31510596 70759687 499819621 295917084 971865903 289261250 226882237 90759401 527548130 718233898 322408168 76819996 546769309 751970729 288968882 589855829 185308907 59045529 375337242 290684983 813529826 83098837 680319151 982123084 109459470 871731445 361896854 563360950 81688207 775677069 31117158 848237312 121696692 538689614 208002777 616808410 410926707 387746469 655276583 91058847 524106665 228196394 386715574 187008541 218868689 757611015 813568718 621372042 958921566 688051350 164505714 3167927 257884919 233204347 447814630 862462352 216811672 691307144 275323432 700988688 916846558 285493014 348721900 313615789 577672274 141335613 680021303 186858831 573017659 414664604 767209137 291347809 580116160 8321408 742838998 114361398 895454539 255577913 674311674 798170334 497923478 491997258 781961648 483654202 550587524 995877081 972074442 479434016 351254731 104921770 69288536 745360950 534496283 903829487 961544163 137084717 121439017 340728283 358805853 625561732 491316526 651232545 126859868 780835278 918039967 579555345 229697146 116521437 756005546 768015663 131022314 219833710 810158480 117795514 81203598 231034439 22906890 43135416 83614992 283563740 56167100 477775955 165997446 172844409 867465475 170891420 639364345 38869477 76175484 650088416 453946167 88349059 633237511 368554453 590406857 673271694 84495698 202646581 799828049 334852724 47403273 310959949 919067531 17777619 515475860 612152442 794030790 71052912 193049489 434057317 360978225 807068622 739916179 121760101 125509064 516425377 798667048 115739372 198603408 285104315 584891534 623935683 3376408 445197170 697903213 498952657 6852394 399460976 960531508 567921270 163828521 772546364 746442961 530105787 833380920 917494188 333831843 360843127 492879034 543394167 584086606 208739227 408800445 83478322 898339964 510478952 795446861 654631182 798794640 112205427 999061435 56009335 979483823 993355747 393546961 253715258 245027575 924725997 566713689 751484177 790949690 773870777 628213377 226047352 18721015 40586422 790222382 80994995 585021530 290504541 462418217 181685784 844379575 354851068 395334386 389358973 834939873 554469006 49820977 583957178 843383887 928216192 2543686 178401181 261838868 694619733 162134751 274792580 487439267 350522480 352671829 104373184 202636493 459675342 361468152 571397573 57395566 964473235 824660916 69894206 254510042 223065696 530385652 710774972 422876014 786208622 243547392 995715591 11210031 597509039 704943790 510397724 931143503 172490028 655305253 503922203 846980839 855732690 697032175 134507177 654202424 346650923 739600587 934694517 752191596 83622955 596796336 855763879 116133953 128014188 66044859 249875408 4823359 887964854 742555831 529473570 456771021 467006500 141819682 258409430 595953165 304659883 516643205 895856735 151398329 924161941 448563665 195154830 31925913 796494994 897283090 670041134 226306291 84285483 240064842 14689839 440054254 431793765 913832890 675681368 62596692 523125485 702200533 727216696 124491870 345928598 263714652 999880688 114277321 511579971 20442793 38389843 733422827 437320515 607368392 491957112 731178764 665181669 183798453 762295718 384998601 899919497 882095604 168707497 147386772 91085146 500748156 680369783 529255842 215643761 946211865 288244325 742713345 499514655 437168828 565482743 514684918 930482627 106946211 55778878 456933204 488407818 255288181 806686697 188827601 728605221 784603205 50352242 955729139 65358882 63071358 162347176 264832209 613501827 239514611 735382425 175133672 673145587 827894156 769720597 115149208 44468548 137615541 585869753 362002086 78261829 828136376 209398228 210109566 98907318 420212471 175132292 960000779 945195535 815021004 79371811 64655811 636998089 124490206 3480293 144469827 241617157 420516431 558749348 873659522 930994510 8819488 729119762 517846131 339663176 637703599 371320088 698223695 589738331 44394815 167998328 777109744 729651300 753214584 196241790 790303245 963900498 997905688 543401138 847162751 4684798 619558111 524518340 218393806 304693854 525797463 38396748 513619117 523489864 156226429 132582722 695475798 95583908 49815182 299856371 772662256 36277657 702128182 263359107 775800606 295497008 623016979 634554648 133771223 869450874 575657195 76779030 630099272 150916903 427814189 704627691 17385585 888605487 283944982 363475583 95108334 770453768 699109133 892764638 951630209 76147640 379917183 40801526 363068790 973538805 567853276 906677474 630045594 124009591 237338100 257175135 967217685 498412170 899992329 506116764 357887777 408355383 288938673 683789158 102799226 42942664 319535102 49074270 762397265 55345130 582397237 52628022 265925455 869503648 542228605 720504661 78157371 342422625 797873496 720904061 27972150 617404338 128137289 1004682 442271106 38577128 280838 531153664 356424553 382663084 482411512 861994034 63859400 181001630 165008265 202926543 730301247 626669836 80289194 906279996 148076770 656610788 773258108 378222373 14374760 123498066 109243775 541522324 919048679 81680313 255485409 90877634 115307997 32355800 33479620 870377357 805991683 962896935 333417020 683153668 113822483 671162602 513141809 842380890 196705708 650905070 566900762 311798632 203741575 389960262 35461658 208936452 241340476 177153003 419573667 121330472 152972159 135217628 5321749 975328121 829873797 384202287 579566897 847505626 835439234 43435866 720587338 931709408 276282844 143702840 690138408 155128900 979353438 724226265 70533803 975082393 71602077 987095811 542996372 641101669 193306259 111614217 53241777 418356084 635776383 615572917 862247547 799888021 729632818 576633652 599768571 81568392 500829 308815548 339812317 716844207 96140270 829590651 321415699 348152494 417757540 477135809 254735848 133278096 636379906 950290079 360633078 830782738 123235989 108796960 490758002 277349430 110169931 331522587 743898911 280057116 484972753 463079089 204268735 168059740 545532933 225563257 382186141 93672054 291667476 422861936 568505753 785235739 371802543 912591144 788337135 259044928 933767415 972531786 149536957 307565551 573768695 303493111 64392474 746105251 105390850 414650193 964884750 786791638 22221786 193879020 106393490 769525126 53311174 784508435 845557377 343377323 521913981 602438003 984578827 991700077 342005607 548105356 909313536 402074162 962283955 598327038 135402391 1187030 677195986 1038239 706374105 524115746 448983681 861471673 518307021 930957056 209380890 30961070 962247014 628717875 447625082 638787137 791742039 634049234 620595113 884713630 176916994 901588170 877459683 272188989 648066492 793092849 319620728 300087484 646408963 68867035 739395895 397768823 812112717 21642753 97986057 63903697 918786057 809999352 867864287 710554615 181036503 113233469 164329073 219515851 417113442 477012406 682586048 889810223 702512644 404470771 219541637 732983413 273631566 559122121 853392752 884986891 740744893 955380526 583147146 492935502 907369842 825373423 118990812 14329700 115361854 536882603 222359463 262044093 458062415 268701402 613992894 747472253 439241630 47904264 55904244 206986683 868604675 798333815 414987008 297805950 229134434 934649780 979087382 177281309 356720054 419449233 937801235 275989986 907150163 651725290 431730240 702029052 264764540 468080165 148712526 111514049 425917247 346781096 599564056 598802764 259145235 357555190 866595370 101010336 608065392 274192767 575440174 768049297 577599991 384599964 271716332 764250121 883756642 127073392 856133922 266637022 648965656 815518867 228381259 266085067 798960566 647456849 79537050 389234 492383421 590416720 918255883 735154127 417660247 601718130 194013142 781669799 222723173 826779065 91980281 731637403 835556353 190412033 755813535 782281408 983889578 591834439 714964853 203041426 660329775 377262554 237768722 684936667 681029409 397073430 305998039 144417643 282600036 196975172 160058755 581430272 313124453 295399547 383179712 533834312 71512194 62866801 225438537 60616108 330473518 75245003 867873978 439497662 359295052 166899299 228359082 830456154 610714355 881134610 629274679 338607346 482080635 298315933 885492315 330247083 267619656 657561959 644537159 725367186 768242266 872354626 673727508 91902162 701224000 679128586 468320493 690240300 188223899 444432395 820006569 881840186 510932803 538114695 51999578 556969517 216417312 343442873 42895656 817212949 160066848 236652122 550303480 703453730 554172514 282273185 975358997 162981590 948580438 284091939 217362940 675921921 719513734 298773286 875795845 727184190 49285276 422889156 567210426 735198572 666085370 270032756 886410227 799578839 914556750 59333193 152778442 798942325 53924806 734785706 225676098 164078110 203578875 620626118 418939973 607786125 170769661 609952613 949356677 571291630 554360583 996539426 948319261 568860038 662235909 185533542 20016554 333126759 145735306 673774901 660931926 329207881 435215760 628178893 866421812 861971984 90939503 20971633 857392805 87788608 696064132 114200174 706270395 807915037 496491060 106964091 577867756 330395768 382107971 186547883 95630996 632106621 167907979 32287832 390737256 689511547 283621402 225663726 199115118 103522787 486014305 971044961 474241962 575024693 301286740 119251920 388592612 780760806 784673293 173212511 766564491 221551026 67017702 94614943 692453974 782810936 809998045 85459581 512239029 425113402 23437330 588587036 601330828 563689594 252654058 996984942 774846346 92352655 605779106 250335644 428556766 369121600 433265136 314398161 746190958 507608620 858023640 210474527 185876317 906743175 668436307 97202200 58595618 718815622 649702020 854301121 361444227 435507250 78551689 677345176 521786057 512124337 78002327 283727884 206606060 84804170 494938872 761246842 757083396 522836466 301163094 99494339 43506249 963689224 204195022 135739268 451651850 667522260 6540787 853252390 840987575 2368571 330268120 55303924 608661300 901913474 399164833 628626246 428851030 999718737 739492564 885013038 363633673 798803865 150140577 910506410 489611912 87563318 74480867 879277882 214333547 105103049 31530196 82830300 84685794 694405769 821365858 457178625 374417199 978985798 913859896 812319826 477450814 129487818 599408134 895919254 929141339 722379004 655340480 611579299 632309419 447180251 244271877 976676488 842968975 457228867 14016420 773111229 334924084 371534266 253366992 185264970 107595265 674685008 354368569 41663 116692019 526322527 268757890 790537248 263148424 278459468 166924836 14443629 390090926 485344095 363857858 69323191 620119548 985621030 210720808 488674216 213178509 91491507 520354560 817681655 871609924 656749592 837987621 611629633 172355991 957026850 352744301 509144615 227961374 560378296 445425734 28876239 953792357 992461410 566630417 930320373 773251605 504073231 329594277 344553579 757446972 432074371 160047925 123534865 656701066 255038751 676326530 443891408 280970969 578242609 801138075 642875021 290662076 998701669 100451169 385542324 683625772 495961452 250621650 259611292 874689167 828597194 550264530 887214167 453933422 664308716 707711206 944729826 949204068 928680423 971291734 403611913 354696272 263141161 976049679 424512695 792713512 909842762 939922978 967716708 767398813 149188686 439202224 685676839 897494939 61471034 502408213 533046065 468085829 891230294 202215782 793059532 724185391 870435933 462744439 242823102 79895950 260936226 332545582 18145879 674103772 243969726 781301671 714932435 77834593 809865719 192101835 652251898 785667888 233654889 330602652 619134115 154927094 496668034 56126421 688053926 141176546 98024442 55877656 141822322 955490779 26168444 917187166 720580242 229599572 146898851 162773335 796737094 499729369 733508587 443396223 886241264 76392436 351976725 230441474 754632462 789035509 623256692 921936809 958805582 528430354 469258477 45599304 106006933 970092176 347899588 183684065 720763356 844480287 7257286 657850977 271302856 180890075 646272647 20853961 736654548 196888196 885282676 387376443 825932778 271193887 202895073 505575986 890972181 282043519 453362489 271640013 497189687 127004828 351626027 386972429 187770979 547323367 121781750 221098599 733978623 668194561 844544049 959087298 712692778 547659074 96608177 311564298 57666865 579871839 1000000000 217450307 640924076 115817715 569663535 870006371 104239856 669815880 988169051 291228039 137615231 150972671 658469520 144133178 424365785 518603649 926580627 448761308 575646438 928740832 995697942 653025043 949625035 346177898 886241272 31228987 242713692 900043261 938324860 322443103 771867559 640634576 637723067 58313576 902571830 25147126 121162384 117571058 84499568 473033678 622894786 232430278 553279609 101603787 610882744 414582082 550513984 818102647 447954560 615622954 614104630 448857942 529945476 682885101 832769393 167291734 722705307 350023775 395054323 240570898 869454449 251377588 158361336 854312674 719655276 174891814 385787436 538018873 62833954 241697379 49964967 775114516 35832454 115018630 273731208 785509265 237199771 286579292 506598710 734298744 596466166 773984323 417394031 536096259 700734359 58775906 453624683 764990239 770519776 801740052 975632939 528068589 421025417 946936042 155279795 730726284 800620154 319766000 693261625 672556398 309994821 540089289 740726732 944306347 359690026 557634429 888940491 9889630 961374693 325381041 718942059 516166101 847053480 685920010 934954514 263840741 201994808 660390622 937023211 133138817 505744844 185693058 323513731 37500523 194947030 222141021 4635387 676868715 164604265 734419010 638606589 199273984 48375707 841349955 434032132 221257983 553736371 155318472 113224279 665402270 162170015 882312993 131641240 956711089 881418634 935661049 830889658 94669409 822773476 230542906 601043799 41709392 923606577 648219983 955074101 798777190 785755914 49514189 850461614 480978330 285557489 229629968 995080337 542029071 349085287 780283144 787815285 580142175 82537958 696762432 727646080 895898288 186993122 728844393 259529995 540920943 517405304 465259458 924912159 324577550 392332954 364548944 249127160 810526766 409896815 203979871 603887728 837938909 257277731 933293175 639092656 2941783 816863172 274524987 664140914 864622458 717159296 127068378 824980020 207318799 209331501 967861546 593799759 84312686 204929732 281420228 774659365 305819855 269798311 510407753 98721143 565161018 855651560 514324248 552788399 21063374 278358393 56186754 206408191 124535389 980947020 644503199 204110462 764419337 576574281 520823749 295474147 293602222 26205689 410474952 531921476 209165456 363648252 386654073 155451236 772375509 946716204 165547580 315573881 250125007 96782094 348698341 613709356 417467885 398315185 528727456 450117165 823129350 610211845 108552920 284265768 252144802 973679155 874416376 625561466 997789489 681127497 515482805 82045484 974627773 561376211 132838064 275768977 66680021 485890295 181557678 120290140 55844476 332707440 640840865 609982944 731971367 896661599 206562922 96061920 8104412 786537596 991314609 88836614 524095769 63190704 418595557 636297377 800102350 588464910 656700800 264884891 59508837 77372201 48130143 693482430 386939919 36854871 561549092 765745087 475512114 348906665 881238006 456320946 361329759 693691748 187694216 561823493 881777999 845409484 865633952 408865382 814651375 387707000 134716770 250161198 835773973 78061845 242940390 287477998 781884457 413848660 547996847 983275509 340852561 201051216 563125220 657333425 64589402 257930270 506556533 549373784 799232964 256672528 45553525 961547748 526717071 407037818 8320485 121759944 145033127 279468405 39125937 467701460 553775798 797666442 307437770 769635128 950615066 63257042 743421773 689463829 528883266 397404136 404731202 945200850 755862004 724733395 468511987 786120368 98058389 635681560 840960093 883311175 643265547 129859716 192123405 802630743 411063048 590463069 267856573 647869222 290063376 239277245 595239378 501275491 675965128 654041638 755472114 724740282 682007885 427938231 187311853 581451676 676417594 659853236 199790557 59563326 457860720 578141130 368171308 82291449 429432856 84723312 966776489 295203314 981101156 993143110 897541985 410291312 551668388 411534939 751260016 372024358 969096980 916242272 365410682 965801377 646853945 289614776 331008747 537486567 74895466 53976752 266862784 822683169 99981488 840631625 779169237 234622086 28103506 467377814 820562059 256360132 195249850 886428009 960426878 929724526 142025271 428186826 601888099 486895268 653024797 135133499 653059655 835087087 368171009 56176213 395800528 548610630 123735934 525447463 227128909 47567007 393219660 463281661 846233325 845680297 296241407 700194208 861941873 684165802 275791568 576436310 920982058 917690733 741226251 901431351 192049101 265248925 654398036 98859032 831940837 388609248 772778800 865561017 15574206 323637242 865555214 172624120 159613255 419391063 158906540 316867153 85616422 273984830 345494883 606626226 545776339 815556916 216667695 252410185 103696751 968619880 824311724 545475303 192619565 330765878 961333740 708027703 774909150 941863797 610991305 140879855 421469352 994833657 191403717 872780374 650068743 607205259 450019959 600064737 270419839 621904016 740277491 67041093 392743270 511323416 250465646 310794598 764528577 242365835 482253218 681451319 493390212 905320727 526560142 200793514 872656403 451171260 397308484 487705341 390160813 564574361 430322886 517628392 626512598 6772686 148283088 284551121 695262678 675173405 430997051 485070470 246388769 373636147 234515382 467618758 525013715 400161242 513642840 372719548 59133704 165441414 165492647 547232187 627944772 261195655 63171987 352047711 802108137 901861383 4152570 620426599 688306526 964279278 698750889 494913092 891874383 825466825 905704954 645494099 658281673 537715471 880099682 526894647 65190865 953833172 500429439 784152141 19409957 805233556 962790134 246781593 814779190 502166860 125619003 794917355 610397887 124731007 712633735 540637740 141462845 302990339 651150944 634247265 36118683 334288771 525644558 255225092 292674452 208592719 810590613 814203665 612897682 980802601 32104766 464627043 281462113 780336596 575347732 326952348 2556973 271655539 224771424 678375058 693208835 928860095 45521776 694826930 162710788 236840249 544572448 646985091 751707696 371172505 761591145 673315129 22607151 372978640 872142780 831902084 238456403 442021357 231379360 700295001 30312475 634904852 433011025 60353084 747668995 491663743 761339079 258051560 68074502 2775950 769101996 400703541 844080600 846243707 738911011 577466440 808484007 81245911 288807343 326257562 533212026 892123030 389756376 290689085 841051313 943413636 380587710 182758954 76268691 347668838 380468860 322852715 913505890 762533673 48066742 706728243 256576600 56412275 390767277 200638774 136403489 348599164 687152505 142493643 291995382 300743053 784037989 532445131 511672747 823726252 525820833 452539215 856699798 35946000 562050174 643619730 685713759 506261040 883469272 913506881 693101729 671734799 999189365 858201583 614203510 231600457 981951103 704414566 617377121 839772067 845604315 999899060 189385741 503398686 472513387 12440390 419317610 31622318 409251660 612415307 955213313 954695721 616022502 641499762 934407830 97368609 780520520 435876302 486527021 17303975 596926012 235322432 142368081 248976609 71114397 907340620 704919868 377888422 532162303 233251582 480863250 177344676 55371133 527724281 429586136 545762651 236735294 203777 138951465 383744493 294412773 757599364 228598008 3918302 514696871 690866789 977516430 676589581 479367652 545696820 421448003 153431356 791180245 587032236 879626013 434465026 26062965 644210273 67799401 902984509 982313675 60929278 230323145 552537201 742454206 405856069 635017702 770647733 3215212 380445171 727978290 132227436 921214144 998377577 667438598 458215552 188409775 269277420 677067647 758406237 230494619 247888533 938769987 927378918 745111663 240724704 984490505 302038814 232120230 91903206 941597400 779747149 19861413 161001626 918780029 104262679 255026816 388724418 715790323 85116494 466028863 127405202 226553997 534698425 735740992 899921574 798871022 960171754 660554315 72883809 936895617 353367250 988694366 783276621 695927509 149682862 253280100 271100984 712029267 722169455 396229314 312873238 438387263 952455908 110904816 732826296 980616981 789276827 213149420 875717725 333153753 121202651 90157295 597951601 588127915 603745125 722716423 262098720 811692659 133327401 311624220 451949009 581815622 257640185 784165104 53637549 724523818 122217198 92130127 151252904 467063129 627178854 60995374 139044732 191516617 60136313 3098860 9631689 403581150 280460719 630157110 152333175 888838581 703603409 31381287 685223412 326996626 383993493 901423239 182672816 653943086 547046578 410402032 369846668 40838569 952418722 832308149 532764106 202742080 129167475 634927628 87218268 690597498 471080591 849684693 895645318 268061445 88877615 158364003 773277080 721508564 159219269 683317539 408887073 795354193 906271129 499860530 46276065 578952045 314302582 681917648 121292119 759210933 844072522 378343093 748820221 162108504 306553783 320282821 895774095 590085829 11221481 329570856 303840313 984014298 721833024 130378560 31617541 22180962 68272142 992759271 529245640 274617734 346395240 758337016 179859284 212598011 264857848 231035415 250288460 540856434 781766561 812164940 197056939 219764556 902102601 991297922 543692458 115262055 589618504 29803791 119805635 797753202 456459651 23361231 16993872 977309718 373135405 657736402 779797192 127852823 161144726 729770420 52437657 476152039 257850544 795886779 507521805 538733578 540477435 687612052 452227853 901464013 458379648 757402644 102220486 859636823 121910601 31153008 200796086 411417607 175631510 170453375 916078076 432826814 252517424 346825407 270331136 11554827 580120773 190590711 393157978 258665870 403206810 25444595 165120195 106887373 462316476 970365131 659020449 42105135 243075304 942445072 850374196 968283957 899144405 347740274 791361582 29178992 853917352 433564705 254136380 825299891 242173519 347996664 207996066 809330005 587541722 794017843 165884923 740390059 20109856 991417486 837787696 641468069 921693024 804758785 108860534 456678818 56283999 396399777 424909068 190967146 201955598 588237725 931741270 57070737 925657493 476371852 668247757 397476950 734239656 73796322 54087100 255463797 268987180 603959091 964155433 495621828 235153733 288183083 701123953 356336645 309664590 158546094 657218220 564386861 376995258 609717031 495509753 252213659 102727361 262922469 704563252 887271925 244278816 139715199 545932638 385053332 513436352 852902019 941221288 939132193 801658917 231038767 668225572 77989400 618554339 614173781 199320068 684016383 34026179 669557613 454893853 770488398 886005432 832839929 242763027 490037539 672730319 783922771 527123907 606443958 969529890 148504006 818263088 986786528 266897092 39824335 636372203 130614762 209355130 507441398 653350565 24540568 137253481 284040157 50559565 669253692 653586106 613894992 530941733 716079688 322145748 292452770 713356622 249115637 560772777 341706877 204672933 300985430 704557169 377301392 295630382 92544141 177996109 664708141 388994388 114689995 635066669 496114276 759637847 917698550 155790838 595538118 670407854 233829225 245445445 37968709 479583465 502444410 177773963 571481757 195808352 223572182 363770566 187036485 550553446 854617457 28841783 172127894 253747893 612512835 82342494 583585278 634321693 289922035 232999119 679515542 871263401 316685494 834449171 281848820 378519517 66596696 834087915 102867531 953224594 454321011 290558576 195192021 300809222 996918356 576210546 576969725 848124567 772597792 548892943 13407169 950843115 276388108 203968407 81405619 243519339 302745336 509073510 146043561 310145513 44703245 456903768 220026592 808947556 88325223 932785840 920094457 395085296 383771539 673008860 56398278 31475532 961141619 322532108 994144904 305942665 835312018 92444627 263165265 573954429 475523582 207922839 332668893 25659598 190757327 705272934 760847346 964539589 327171040 493469178 263962723 546621109 381145399 92969221 923728236 199852034 286750243 752858095 698680026 648600416 481601899 177863435 114899659 429393290 241137834 787085828 772271015 567359683 195625774 25149020 962671135 52119066 778461546 672285062 784073430 590323852 836284357 855997470 187889982 276932997 639723826 227527238 291165905 854330835 201969562 581943052 822234308 305793174 519998853 429655361 55236200 630278933 228265935 282067019 730739683 115631324 664913700 517977918 117332082 691375843 9962749 273406645 878675385 329521292 211118924 359861546 531318315 233463582 742837098 172449039 410740138 885472844 504881783 968413669 649814565 414228939 22959036 572161234 284498662 188493315 783811865 385052257 262335217 367489350 479926171 728408142 815133579 730249758 588772611 712854184 829931702 328864162 233819769 739436809 459701696 178390349 670571653 32142189 81680581 947388417 727204451 843154893 81573528 115228478 287097031 830598924 670957446 331481150 145940547 14245091 56122171 839526271 408004917 312468113 679937869 34872825 625492217 744837807 532934529 52641278 54299576 13786783 130975184 324723181 807226354 369622505 477696391 891876305 731726089 676995456 908416923 190309644 816028637 397890329 288689017 797158889 57198763 445757814 377538489 563801105 473178259 227407796 51937589 519541154 201008347 119315525 466480510 417891905 400425089 947455046 249026446 987322143 827177712 299827130 800615595 270621721 444736696 799777516 759151012 601798913 39182761 418220636 169884003 492456249 65721862 271726963 43998868 528665174 791375642 498179736 501748880 139835912 88337506 252272026 120334207 218355413 51196038 520427010 937471048 942177444 155182377 140741246 869898073 639458754 689140106 948620557 681933043 115701397 391167012 113542118 201556424 20623800 480646907 634040152 759115546 814051112 3859387 461874388 409438631 991023289 127210250 306774587 125079541 537460142 776469654 800794503 984252987 331874690 850675235 977434413 685809957 232680946 643733901 782086999 931485380 231688900 72854887 75959690 475206580 547318800 479121114 701435159 226361650 683528707 523731503 497888049 715301492 925422618 897217866 487509788 960486546 267721509 636358291 722559994 930872129 512421992 278220156 711269756 604208977 155032293 759057727 217132724 15013590 36886390 419586402 917386107 951022292 161407747 844917518 189516906 288053748 104584930 827709949 16713190 567365799 495683373 217357085 60195740 942793851 233173813 575846243 357993988 626418125 206910315 849607086 205157044 236607820 225752749 981426907 485957311 66133481 981918389 175024485 351388676 43934179 503451950 67229050 456629763 321565384 483046112 671616265 734169277 748951430 904489550 317575545 152507350 4318102 643150726 822428095 191317080 270091399 171648948 660862060 362289561 546689688 241088495 542105907 673291536 313363231 687740541 466679236 582388250 602013956 339366292 28537769 412164072 319167308 960448465 50159107 778934068 543757456 302310033 833393252 989243682 580513520 754066648 275540928 797226908 330732978 224220318 181837158 131223496 810549499 467528037 942871780 211395476 284790053 434679672 854079721 459855385 450159882 393584508 288716012 242066182 472279058 277252319 101612523 103290393 566337745 236607671 151672443 776345901 812169019 379183402 145862803 553213535 123544735 360336206 479827638 303238726 688859239 342216048 769025959 423995133 837631839 455760560 160613192 738546906 445514195 656905386 448331539 656856722 747591065 562832499 295461336 485645834 199901130 701585556 705395192 877950804 955882383 321390454 336257074 341505420 407880468 733895510 267772363 390114461 830923443 340900850 340062510 612552356 631744782 53219063 220225847 385399926 812147408 668877772 374272695 502553132 318210365 935771255 987459700 147946904 40485746 58663965 805056056 386298613 249463159 957282570 622302036 934943662 274165400 641323029 103095663 421204373 360719397 72606157 11611439 621510724 201755399 15720319 521227244 520320608 316801134 774177623 151704841 903323772 90625069 661416584 788285083 12233860 102839370 781029797 829736184 76066505 389412947 308207585 826427029 986436234 482617844 79910279 960009836 736085950 908882235 366832773 16610125 564652129 144081931 255729091 168128719 638076060 322104048 154666450 990681469 225470953 777912474 472440486 396736838 403028628 367423692 158027495 759634630 719696434 140128804 381034603 856304880 747805281 399903916 451817218 350317293 204437464 375287515 960992505 324667280 688552620 678683701 152970061 550457079 823733237 447778023 861388710 193781558 683313980 803135757 498516908 657741763 211231355 83161582 827066720 160203013 510284595 390727218 501353241 814916374 408304135 826465135 287296117 437480747 996896779 808986893 932507825 457462032 40737518 244575119 845337749 81435813 308861032 742189021 591818957 308031007 305446076 298281818 361484604 852073761 26270444 483522389 1 217809463 750236798 364414885 465903023 520543353 396424950 223810720 976198112 653089219 421692399 462755045 496712060 459757022 828729070 252358043 913575983 983996024 753070563 713846912 180112578 615945034 628938949 259154414 470153608 355722593 210561328 957434741 403123128 865608605 232116554 598594382 52782469 258445408 207470579 529358525 242566022 239361429 503059102 56287099 431942020 421554320 908345834 518994070 793005001 614475470 915925534 17959819 25443950 551780701 925642596 724924135 622638811 17128815 86767387 192829780 293177651 904193705 300524995 391272766 120863558 393777824 387243199 178267358 112793767 119074813 907138220 660308454 994572995 306075632 476320758 809288482 100325241 124215988 774199044 834630339 415706042 164679513 654499389 137770162 801291811 295712824 798503079 193443160 956619755 764631232 66762153 811227342 466454924 428472964 31406711 897444879 582052035 13626101 485343541 210739761 545089357 467260612 492759701 204898260 385650391 46143164 877142267 883024609 372315096 22187168 904484425 142216382 727542894 242053536 891792899 311787343 766056557 986478387 967129217 883665031 878927987 991444246 135719793 319151279 923783589 548051433 637356923 410096001 529977801 791699136 335649508 709487969 16505923 535454552 598097365 325342780 111745701 57901115 927042207 706377888 186293992 196863928 251356895 170365706 114756051 588199018 659688789 2466521 442438023 844344733 114198505 179778386 135811529 803743114 796313564 723289341 721322337 387815889 578456117 950753113 719452634 945513016 990920820 593509230 562052838 838564885 491198081 930141274 338663790 470473267 513193717 168479929 403304693 992277741 786766709 307338156 684855313 677709799 286489665 933306660 926289480 785021202 431085256 435672363 701601583 265430605 450586508 279401387 787548643 43019430 460881524 216362885 980403355 457558562 590255282 77497 49891691 244238758 448222290 194090236 738798646 162394333 774432946 54917212 198700242 875327181 348927887 635449237 373974691 801344831 154063875 551606205 654855851 953789617 936910979 953601366 180586867 8695628 62740244 764095033 507723456 903120649 321376105 534844890 588327365 921937806 86272048 687662274 236638755 969246675 885300444 632813601 909153836 77662166 927999397 285866543 803844884 215158243 510910441 550046079 991240255 341943929 58266989 10068884 183403604 971645706 767938719 524134481 940509119 10737439 93353699 907190898 632657050 447059754 596920477 675429828 223250332 988440628 319974188 40793820 20052850 220384702 269979694 842819738 905530369 887942666 510643903 699750170 39057255 801959047 917175399 8435561 678614782 286785165 213859143 369406318 967066978 869418674 258834706 842246934 228339123 169584164 656517836 14977345 592959030 628716694 769601253 343944660 750431327 184926832 575055413 937916075 244022122 213975054 217055863 474215015 50823916 68492856 180182698 20125647 48770115 446623407 649547128 239517986 92284977 517762764 375694052 716153497 772755166 225747946 487602595 721288209 250018273 863733035 481565400 71799339 626753845 825190451 404962569 327574906 259152611 800473901 725853228 567716906 883231074 800570689 363776896 52785420 602823226 376335432 292855385 782227289 311389259 58568232 682526363 528152818 500626494 45589190 284860476 848086095 539636865 526334697 676560664 643069766 45043569 603785104 737222666 240557383 363473063 638945917 762859066 43508867 74603619 534914989 420449362 887990942 851393852 963524786 609903086 172072948 100968522 505094026 221631184 2168335 127913607 417651362 313738405 355579820 787593641 897799141 123068581 234672759 932324627 465758193 119771649 798835972 697922574 477941405 465894083 453868894 132194891 531280868 20395190 620379533 344100353 264124026 113610030 602321783 950397370 166100160 247871975 30179405 540208790 511075610 594672833 726057036 42487276 888399344 105264154 424394992 797961081 297356629 404077094 100637569 434120606 674674173 7735115 28761980 879040275 81869498 12177432 600493241 528351438 552990601 622673026 813099667 614843042 682586437 96250306 145787959 640398141 903750752 763002135 85698575 710302565 70945111 606348681 99457272 273111358 260997364 934741913 43344143 145013594 456106477 846765263 718170213 450606849 932072385 313861387 935364983 726310579 900507828 261275838 569401663 227911725 289801681 683418951 858960100 527110705 850002158 741062940 356499089 166341583 292665 282580675 60691641 162381190 282061861 793058316 369085264 2406683 85709969 460450917 129835396 862642203 407923921 776106742 531933962 288204872 748860029 557316336 329397849 40122022 999757033 174392815 772871500 887603756 627014889 518891053 784732013 325453119 97974651 911838557 419152358 908286705 783929282 901671828 962206363 113819983 929437654 444733274 813130051 738592556 918853089 590921000 63049884 700471545 209644488 313886672 30989921 36387962 445499855 651650052 155901342 962269361 672843133 993561470 593701508 557349843 917773269 288644422 493377235 245176211 113759451 294948127 745635184 348980202 631899015 392589176 904877396 817176715 130239670 924674285 433415536 285547335 785201510 26380111 397719503 11230229 329484513 116509690 43155920 625773565 43840757 838661005 632787588 866847467 410284849 839368547 168031486 504680680 6746668 255312327 941165726 65832935 91518751 187687875 626306973 604997741 841387442 11169203 891012812 262058857 809966117 258152033 887274277 761424878 345057238 723545296 665122124 458852609 57044655 379476927 377295519 236018064 749674509 468943985 236655636 146424591 155676362 968141459 966621578 167785001 869660595 420676728 805219884 733078986 320475932 638482966 692276850 199536432 783887034 319636522 648473396 33908731 287315477 131632906 235027101 867670705 172643052 724927211 477969530 436775484 171852578 417300630 820016175 201058166 707354369 870584258 803649746 755548012 544639327 64146958 464974746 157492237 152913566 797914779 515169555 103936396 837154541 674920902 840775707 290170456 892592065 68330581 666815071 438565833 354612883 131074334 299488947 588594140 275086494 556133764 242666276 224195315 268907994 94204838 138414646 452139596 155453250 179982125 43686706 681788169 934743579 738460675 526635300 281494901 948135225 719099788 805463109 212299662 70614264 570445086 344160401 399761666 71306985 296289298 566602295 507963712 11648733 98795932 393129036 246767986 496990177 931392652 696646234 642152467 480916977 639813208 60862264 340734803 615957183 746955083 444519076 617437478 61203336 537443346 212617949 389575344 358837149 356825605 634254348 102085485 166405384 357467407 734710825 777873441 873979008 160105586 673477327 288522000 422011574 321039410 868447871 480877238 756250479 141284787 812662340 583095894 20093219 853243861 294582696 208506336 29118857 674114857 103336812 210875375 810078993 486644520 639328684 361634094 88570807 206021225 941967472 660242776 32786788 949584851 620366208 223989943 114455458 984013446 293790676 42123765 607645292 365556270 726709193 442205803 72566851 314059175 704421407 282833389 310199273 40913638 807497058 246973295 395603543 593658581 364372964 490723864 763910751 239723502 991281280 308066392 787549134 227461129 932143744 3816417 226302956 258080006 144915468 470245888 522667744 98586964 358489876 320131416 191342757 606706238 107148534 915010195 558059186 581196968 663653127 495378853 411542985 485201895 874928595 84911431 954902297 527975945 566226552 548699164 642176504 81960377 830776531 518618157 648856786 764284988 359624432 192277346 477726542 267629274 286082102 742707676 823975373 927810887 625697920 134310508 270015003 89902203 655700176 97550581 267191448 171709330 475971243 234322929 383652201 540897241 433211506 422471487 432607804 943854841 254532329 75587234 374249485 917989533 772910211 435159152 184159474 579064227 371863163 468024008 205737164 361349580 92734930 66081718 178917732 441029962 209506595 790516056 2832498 388068272 332188085 284221767 39925730 507759761 394788860 347960069 238798467 260602908 19683497 357553165 541428183 124174907 302536919 366977276 106421218 502802952 424434864 483574624 865180779 562970402 538663959 776513824 938191443 52667385 969919035 463065544 216236481 273231346 290771759 612431737 821475926 562044850 463719192 193699340 273322745 600033563 217231615 87578436 230702624 493122171 404061807 22380684 256274525 928937417 21565445 668364451 297635518 870986567 315758775 880652750 539141374 362457423 67501775 121355107 833117769 412835917 538638760 656158377 748104647 862090882 529733276 423208705 401211112 124852420 211334301 443293164 347375225 937593596 833805853 559987132 1506189 739508187 673274210 687036491 168817026 892479610 226318570 123286287 462308756 8437464 413654431 316322128 598723372 404523681 974871928 775683216 283122062 234532351 971432943 533932178 5194582 180528132 230715743 182705625 841248232 120090034 227062669 569647233 271690005 126310115 822779181 522327464 464442955 768438975 934339445 704288452 512978498 238029304 715165623 650583946 311758152 220181260 69545145 470635746 353538215 630287939 744201993 822107415 324745327 663009119 283484815 67740955 808755936 295782227 111692418 879482874 345873588 849327742 562790336 593850515 203244692 476949780 932859300 383623498 279589699 38368415 151001423 564491480 637357051 319372758 95774906 345342198 740328399 403102352 873480568 338673569 369287321 324126409 979162799 862077702 318851270 5626731 933191455 275287446 237447463 808834214 648655034 262425754 323273716 736827460 294659454 741106356 819094761 287037285 788562634 596915918 722947666 409737375 89429051 477161784 786991535 728685262 526455545 209948715 412260160 587214395 17458150 277970185 751705622 153504387 871220254 418011290 560287329 318777519 651185712 734585745 776636265 998486830 645683975 766348752 574917752 201200011 364529108 249319163 191159406 812659507 313286131 621633120 440200332 824575647 980574731 989272802 121660058 840192759 818578262 135331091 599844990 753252723 59951466 463126584 578642750 869683388 425535450 471769761 232409780 336613860 23664075 494707870 865415004 605031401 387031705 830887281 104436983 816273058 220116165 783009393 457993050 260939689 209775194 208794343 108866029 594523867 207982989 51694056 435714259 248738934 705996931 737929915 940276059 731169645 99768580 297063207 589695702 763246681 224969621 488144668 705609762 906948721 844189862 125557999 270042585 566875731 704862937 634378064 491181032 28515176 912679401 811220308 885448874 77994960 782354821 968615454 37150359 221602170 574507688 419587793 31999939 896587620 745090098 93242611 239004348 354627940 927821302 371886718 308671132 609839026 310663172 965692466 871729769 251405044 53465219 702455257 747796307 303007278 927766252 630738495 513062804 677859465 19729650 245969546 414075834 472049962 946260070 20978194 808526338 450590947 126204754 259591451 223145375 77601258 892800048 325546122 196905233 960320635 315679354 713958813 4128860 10110355 752438756 677572804 101022807 18011759 799256024 236676800 836321348 264298350 502584335 914513168 927977197 329504043 93404693 629769180 771190006 119215439 32313196 962516506 354155234 217726376 865434054 365488550 387878565 925999553 608442512 542998278 566364606 907344891 7744383 492593967 109914095 541620659 177158065 268675720 958464899 16798526 845486536 823528203 475811918 616733251 509953959 400644401 36522068 341198593 550908525 250112481 745924328 976016010 355467026 106253376 831530441 538244804 719778535 804254523 286746479 656089118 216849731 276303110 315548499 752800684 148828518 541395115 309016832 728893746 442272386 290939189 527292790 75117288 336886497 348348529 645816817 536291894 147169386 644769517 659538494 381988611 493946974 54924727 893615716 134950926 738299292 1923268 32343488 784216669 494131998 1980213 269929072 285654360 615079702 48521308 721884699 206674812 908851221 199362220 868789882 743851681 557914507 88948269 704916789 413093523 339170810 776184316 6217811 434103955 202078831 230383969 21528092 877802280 522291774 176988128 57351840 815395748 103702631 788402842 313377901 11218003 770195373 2453661 196969641 610517328 361007945 788395928 102087472 342281523 839120965 443693972 23781261 570628267 964254852 795026612 424249665 181612970 429995453 453202851 618930047 821659024 338516036 224484846 116705051 254952664 304323819 584506402 917596617 507015914 617141086 140726270 190499719 279137583 578207403 587503453 634676119 101245964 840950350 327232378 5709264 958290194 805611019 111873597 495319379 499643327 24674236 72708541 705124296 302272691 174919208 847104895 251338691 310149430 293910469 855767893 130109838 46494633 294150786 310248635 108453319 434157772 296670032 438779442 441495503 830480084 600965398 220049296 698836772 104898138 785744560 578522315 462151756 321086014 379803033 961071469 269379750 457674847 259456138 87999393 726268438 232642266 200993938 46546303 379117374 762894089 754685072 991377471 979438252 253244104 543740087 373058355 286587964 59654545 522795393 18892271 16874526 427393566 87975883 526359496 898157380 663784526 707913167 167622107 200086005 199385036 591530769 185015776 840471240 964521324 931688964 644655551 160288590 866363920 2492189 61484475 183428653 77365424 916705115 641470220 280754801 676421422 32145048 546419820 416091460 566158913 41966337 223362141 875132229 792579954 211527338 635407227 756388357 957106799 570105871 150070155 868284656 183358800 266041582 472309048 850315966 686913654 350536443 135236447 25622656 726145932 998122546 387589134 503717229 682640447 406103509 751611302 598140338 759911665 167774354 253867608 551868502 314647968 116498556 154835014 881494745 356082781 849540590 275380458 346265902 279362305 549407735 608428998 604639901 430062349 707261562 70539211 661729441 701677197 548777627 779860983 923330126 644333688 771957590 190580335 832586808 28466439 972239935 250690502 674520627 146653784 137558450 263043808 693118345 484485909 420787948 681461077 710101247 569949657 852618876 24975655 5902590 107745945 453706714 413251235 127182831 398765255 837238986 318969925 66041964 604547910 986605974 131155927 657374208 812820333 627463977 269155499 32039835 791178620 444275241 125724944 395859897 119182126 164454904 13080768 287221981 932798288 441285183 368141222 4010190 415685778 951392095 231924148 514201139 639390137 60335664 23858031 715158554 93045515 92940762 487532691 758025447 512369268 78771272 8709052 389274849 39417050 268192200 349022543 478935953 828185259 574054428 446842279 147915529 372693480 803173546 50982367 658986048 312438134 811073049 495794330 371416124 929721745 135256466 315292918 182972090 76725821 279362669 620419352 199964048 661862752 949174495 29343458 226080617 888590696 351054558 106806453 964374876 590019269 741154927 753565436 479906825 844639386 541323561 122668686 637904217 550606028 257025390 898732719 753544389 944019861 122965882 140588188 853189183 575880144 277187385 230300669 475666810 216719897 723854298 189877191 858198991 884592900 87787908 93609908 659320255 512377600 575273583 106137125 677985727 536014713 568036771 177499569 489972456 666504624 982719827 147190898 105093040 828900846 302248074 181528739 33113551 188195442 139509301 787231941 221479105 681918048 812584267 185198649 56744546 695994441 343837893 222552661 762227719 964585515 544630537 197228 770539246 915152848 554941708 338213424 806662739 36723833 138264390 94887345 253961573 967820976 890679786 954222227 950842009 632165534 299584262 336832639 623226729 529831462 208583910 962126370 580458831 243586767 449953239 673926695 379366639 661155534 510390064 197253214 916784738 807286794 735019750 846056346 103097282 174138056 503096482 197355923 921818064 140399418 963101042 908855785 842708010 113524047 51599596 789090999 537873591 314020567 335405811 720167809 843935567 569244915 633904761 728376650 508008222 39554154 284826708 554755650 505466311 138644176 198908484 393535553 808531753 747895022 153893591 133164297 28711984 319683586 811017040 567571888 434354517 28593697 580039242 129928348 174803615 595917206 229786648 444293346 791890571 776476673 23586743 229762143 512620669 335625555 681598713 263648497 311279063 145055452 91778893 155345974 435659342 284255463 759360866 778210768 656873761 976696586 34273401 585511188 729888488 897858312 578261093 169904781 56501781 167800226 10225828 841263089 918072340 122282524 283790049 500591527 973434539 51709049 567040024 788746327 819603382 754837389 537671935 291180618 951564143 210300162 676660673 677598164 277471607 810052950 838015151 320427339 972637061 897522556 891141861 251953774 92219585 933632262 672146679 192984467 717190072 426791601 118262809 145520774 359057351 670411747 933136147 789736459 400958697 644557375 302517967 323386599 585847970 877802035 734487241 42079589 719618910 125766949 429395524 279829524 838302278 914199741 105006000 118694442 149004822 208480373 496723811 554336108 521718859 506968880 563665806 359060485 275008795 442249201 39558055 295607798 943774304 190802382 119493120 142380602 178049141 59754749 517776992 349486238 884923561 264223040 772624555 689457654 219802633 835380508 175791951 258228593 328940390 823891495 272934213 934296336 440248578 691929080 172359173 340766954 443556637 123621174 815189691 103148238 448168390 917734980 515533666 470537692 801352276 708407591 597041243 473471998 318926645 76976754 869682873 630089103 264861117 628820004 461267366 824005117 966636592 397456299 354684563 673594483 311067562 140380042 150373164 211582193 624383082 455044542 218832793 966739082 268845250 909186791 216504224 916507175 313425665 13479139 840269454 952155260 49372250 317826093 763512139 331919361 262332790 520552340 404889005 384027421 914221005 595985007 900924997 264642669 486297234 450358757 756104908 216732456 405940381 320156327 7566513 709935085 670664859 129823559 144105016 779508732 739126091 580999670 192419827 667324692 568519165 230449725 270084734 613029161 227374616 403401354 121431151 549694834 192929935 678486344 341594872 932284789 598050310 30696517 383927127 36373286 519490684 739345026 124670212 662067168 197742744 191385903 769866344 620905402 545325505 808644924 160634098 95471536 545287960 934940042 795245685 136409870 860861527 624643717 17406544 239384676 734514769 630314868 910394714 575184466 736655000 566135451 122437612 524563485 935647789 990392153 251770598 693982019 753059729 19702691 661475605 191952254 347218108 223382982 132308127 201996601 950299406 907447900 569939379 638057102 212991235 595292515 443157871 903291165 63491467 468784198 762906345 998839426 837567779 15638249 340638058 208604547 208984135 497283622 805079615 701450843 243865546 590495649 366319661 412459172 650521851 360346885 961995844 27931565 552324872 745183123 448014147 810918887 175516867 176075313 524923700 69692977 64956688 906100685 434808608 253733667 692721462 325838336 168688054 101831741 811720316 876074517 288890662 45623569 42623940 784362108 613285648 319417155 991588169 711417809 940695182 237782942 260191843 326474979 432387126 756363676 669324286 283856560 943977381 813163830 662716339 583281666 302381564 449251560 581034350 601791480 542130600 365356798 648127674 590144936 281726541 532438856 826206807 866557142 886742370 114914932 297437461 700010781 907467117 506150188 130749966 196487514 122268608 425331504 611101672 258011758 176420335 960770308 51238894 184569027 910286806 233035384 184674354 402313976 972123696 211706914 136706721 156911168 659225059 104488770 825418143 787143147 498686485 122190135 358274246 313511874 31075617 790858485 421313985 139893032 236781529 229609561 753461708 214485569 623136101 458553018 906545762 835796070 158867393 822150168 994100706 260168137 177235574 577411443 506210695 88859413 132035915 224715800 831242085 321730496 610434580 851590797 850374367 13796373 796526610 90769889 623153741 104346266 271001379 228203077 394162899 531776769 207612154 270645410 121692238 741335594 937185026 249908049 967773989 80556468 938014972 931047865 351684672 419756660 950289645 392275897 750717953 27818329 862351396 958443072 139331906 533453003 83733025 445135641 103248933 216427704 757119852 420833109 841596634 36246558 364476005 677828524 875941580 992911907 452696768 722339805 41576829 576003469