5001 999
299728127 132697032 625319568 93665377 221796659 9727812 534527799 134659002 893961557 418184710 148478573 382331845 357049842 987247359 663355751 132427073 21547935 247937010 874168844 165383197 343017877 625119946 83228487 731475082 788962207 912319498 647827579 779286384 409871102 686871292 670279594 857176479 942970292 805046107 226125297 276972887 419228054 210147245 967722889 850893505 469294797 42762214 821601978 171034529 540149662 53319515 538199667 721783240 850506555 147858690 909297328 775775592 580733238 742541138 383742765 759740472 846457801 744944056 162296234 7746029 742313949 522154195 562689787 500819039 101382860 150584999 687107400 6242034 648447340 633028475 609639586 73644419 308085620 764468479 316792262 874526676 675699823 880524171 334925240 62953523 128862638 359384979 783377111 758337049 621327142 275341979 559454765 868357789 966301501 924795398 158532859 193311319 592769934 68132254 727050002 285147092 853297321 867555942 356913493 926994914 226095432 934344132 119543300 982598458 360787033 515050574 439190826 262501215 319898310 689717155 251592110 912522924 654250599 878536767 286101147 542936559 230914964 563381080 598315973 92808809 16380913 511678078 861980316 265560797 325917448 743432545 94402684 188655424 969471128 779980222 539507726 191624515 496587440 209616136 947469711 315698271 773094281 147674692 750466019 431601310 234785308 187368033 579593339 929579471 589468848 19503261 896571749 989990990 658191529 160579276 195597451 503375856 472927431 772752913 18418449 421481484 788608715 967482395 834497803 564479885 427814456 119466481 488679923 767344217 127772108 69586149 31325903 108249668 265346525 18200366 387823093 362968770 98709518 313999799 511634890 464528264 576651576 599730568 675700250 894215370 944637671 91182743 792658718 916896522 848535525 573107538 793926185 632638210 434501270 654061016 4205370 164593174 104110012 16157268 114789421 716823593 858446660 264104811 315486241 288536030 741659605 942789046 107396796 285960116 106392190 755845361 515324735 23347570 709733135 700999403 86640482 993135402 478627389 489886370 211161177 947649814 385306216 854414206 519466221 23705657 572176680 550044794 107895988 177077467 440966154 652918069 227337757 954296461 736677462 696825013 707851936 621398698 328336816 564833283 457419207 857980053 281202376 581593224 322856170 709401636 165169330 811308336 152088987 750173148 338390689 671420595 820696373 859533702 155327507 456364599 571551551 305513423 929023570 801676327 990127667 230127124 423459759 604371765 816246916 21977755 304948533 76301228 717698174 20641375 623229773 93840388 618289340 774105653 448333993 562954425 47941927 898833438 697349776 511914164 535046943 977735246 12348634 144179045 910752267 99976205 152692795 276624212 335387056 850262982 439564698 736659593 604953184 767407486 31123304 181179791 276138633 429688236 521304257 13986981 540355510 344384154 550736004 521349340 181708256 157027999 125854418 670414050 681799520 426184037 203085861 240949284 671281222 866182883 55264181 234073884 209997861 744361454 946627539 102587977 206218619 456605320 695175424 359291082 811762330 576423551 488413114 120030618 824019593 679338577 486351879 20413537 233309832 866322182 441957251 182233989 53308749 417107364 335787507 722155538 909087433 939452680 755607923 238039644 735527471 889606665 376050853 92446169 224572139 993938567 803777677 380974621 633782942 276429947 842262496 96580316 17936445 593627102 334153803 687382186 931027105 403712373 665311466 929573786 824545380 760528817 335308909 283310814 574365853 394131858 59044051 413797930 193886075 374809284 667044260 131299668 681132969 414738418 742977637 404310111 658427281 537069058 872884225 667156205 239980357 714560530 437631520 400537579 790524875 778155148 880821229 964501019 13955537 526029891 897388257 716625679 32805658 431352544 470499591 371183183 871192852 188848317 730244031 838021779 882804628 681022424 438324034 696874599 24066225 243688616 448191945 817754981 966208165 941671182 21882513 96783715 309432491 892058511 68291556 370210700 219929418 675411455 768029975 535213015 1894210 449595467 870321301 225352602 476258471 393067018 895005819 494208103 604431952 740224389 988594066 581229517 474094372 913699372 254335590 291863858 82114727 967500197 911710540 140812511 89794190 421594052 964054455 226268121 930008691 229409326 546720783 779473997 93600974 477868314 106131079 912803560 435630261 229395285 555080960 20458155 162462331 271236292 231514587 331170696 520757360 811777603 236438497 290788219 719649526 780114679 42243721 45645842 618781244 323448537 105339108 393481265 938797478 254388211 291448674 522410842 810537871 44861974 714473526 649946364 372170945 739912755 945511405 227599283 110677893 984839639 754879280 259834499 920860744 1173435 830902527 161844797 999644587 876126075 926631009 952026740 345080321 91372736 691799612 429522629 446178893 335042955 108930557 713670605 330745999 846557390 935361237 809206629 671193745 30858950 469453648 413831886 681622328 532824052 148309277 476565480 62964816 53234021 229291919 577657344 149267952 8414804 870914542 121012141 117830148 679926270 815288281 884642958 264489536 130183490 221597452 435557559 684182311 773868923 926605556 948945326 559091443 270598898 735281735 623064222 289468188 224627540 981168202 553288571 754487245 669044886 905435856 383089392 260016718 11011762 416951495 384367367 867754514 779899514 414763961 909904854 944380589 815228545 812128128 154817970 550069484 594327537 617267865 614260369 34124739 307678393 236381104 849822586 720091913 561696885 975481018 71667337 251421411 310774209 3025485 104682836 351343325 136383458 45082600 719297584 869787950 351233334 340684139 923047256 723161163 705688414 173817000 102578235 175033168 647128588 693030233 931935613 866412818 876597273 139542944 347016323 993270420 164396789 425808550 78230391 680125556 14155073 591576514 298310099 1172595 377640141 930656029 234295048 972576119 605084051 709456362 690994550 995964549 678083741 124607460 90828283 330644532 247506183 152250255 240553176 77141722 611218844 784158524 340771616 579306957 793499241 502012310 615228518 510378119 100085870 464453079 325943908 753009325 138097215 914984892 664663436 592289457 925176275 259411095 133827615 450476759 464347445 246513752 957837685 215697457 921983306 323220360 836208320 342217598 55373252 658475550 178559630 972677794 636422905 901794448 173963381 290515598 309413178 679504409 290141220 930028469 258332950 290069155 954665748 744553378 946946111 46298624 740186579 666403007 690055488 801274706 390894627 683250079 778813775 879297505 856333874 675022537 223584810 284615744 220241387 992476363 680504048 373817505 657119897 294088817 484642457 33834313 80024480 458251083 435751931 169110595 401256362 379202655 207865261 435513951 870407280 445138960 699228197 578962801 922679139 179736189 858847864 911223002 467437013 866178955 611491083 402289156 930140409 873579862 54140513 157120883 486483363 496361042 744953671 576985468 181212511 323911063 806002793 574650145 609127139 780219627 543699648 253670190 682563786 495643878 600891375 380340809 705349361 340796216 173805614 322315951 330039380 596661261 631517707 232541248 985368574 315572460 277975392 770557683 96278557 602217002 170279584 296693949 224557467 649002657 114132611 264772498 400610454 613640746 49001459 3849533 602743883 535281296 815262486 490018581 977321474 180943958 577100916 652249670 214236952 859287329 236177180 83163651 503538992 213500271 928535591 273942507 666953658 533348927 391861111 490298560 536023132 988985363 215208712 953013919 124875761 361157041 931395561 587845765 694047654 147319669 237729445 130516635 971196432 426213260 3894218 627231793 90147976 864552624 477415798 431074328 244092357 484788442 663837976 155220204 795168535 155458832 462097607 128632781 244256956 363279354 234131679 320440522 532563319 653620826 213316527 376128820 504041306 101521724 189939498 61320556 513701433 701024949 528519345 75979708 17422330 167012093 817984591 746173486 420100773 230808691 152616987 736507422 617131129 368754866 50622629 15700297 769793147 34130418 349417978 625510710 147359506 681778603 39958071 816264036 143597370 388278242 738610511 931835099 706236253 414882776 809475912 13998560 654811142 304781725 580795902 767128823 382157900 257334650 789501807 110512601 74836199 805603112 883309707 160792515 654808110 694760196 303584354 682149129 63218360 488117411 169812590 231284742 991420667 585788383 690704114 432451652 413732362 339712453 620755113 349853637 67263256 19186590 926305390 702886123 256985554 376173649 915547153 121649974 191875346 318449443 100043387 633970242 709812031 8875042 610328794 697359691 254731577 159659138 453315472 19273839 584550014 160078746 175128088 490509664 578077040 571867986 368869538 49854410 162988634 254079942 909301656 570064110 203165709 939964363 436896724 653662626 261830386 626919363 70289273 765749909 877084522 688523580 967233050 638479153 97537683 65457304 151713092 367131703 45074709 286956816 193652968 156191261 904719301 466206309 531872950 499687395 310053553 842709005 922214169 965821554 557413894 967243532 92670144 559097510 767785004 638570924 489300502 496175898 37682281 294999141 600669578 370264011 32094992 620454374 168091016 455151046 9406404 210723426 122173397 182333697 119403972 501831762 521725226 224210130 831961617 283381574 679361335 28529906 365495316 865136975 618056720 664752030 490210754 620084603 846494910 439796400 792091154 570930205 380394510 934796891 176726499 251004957 631078728 207574382 558874192 770639132 260435780 477962161 755182127 924719724 802031158 841801628 514640694 957682502 313358876 615239852 972377579 112638026 87381933 973367183 221591672 788246128 27831751 789471628 918034417 806111804 944875345 897481886 257129113 937228836 770796414 263825543 442953825 675228967 934966367 87829952 908399467 773674537 681235621 915413699 530820117 662020726 917482036 172063769 615065237 500730210 190175134 587063980 69809371 738006259 938129859 147981584 657651046 938476819 39985998 840382499 592181916 360798810 228716893 164036402 471004962 266333360 771331714 299626566 444905114 246975736 176264026 66951180 674958398 253677876 621097166 907141388 708030523 653693415 564805450 572771430 737525498 681460968 788781838 969470299 569321648 944680977 247847652 828278858 97849250 776151068 944261693 16134924 542144365 939326602 602358423 872366013 790841344 106803291 868437140 404266226 794822536 601191349 465659461 278302827 494335680 268613499 209057473 38827544 262649827 961751265 226910488 520262654 648673593 306284392 238262855 927653848 872365242 47863179 435034805 754874724 179822922 439527417 433588370 814224499 532818393 405833600 279853672 839957541 901487478 763043524 575309548 735924208 466712830 178687780 652742750 597573058 573650956 569307076 936107900 441603091 210492224 210938723 124645127 68746039 894761432 727237617 952444267 348474529 363432138 739787481 737273387 154349663 750879193 827933197 252828605 58503259 917017217 604720706 486958512 619373039 754644024 23054065 94744420 729957325 24088141 115982235 569153239 680440943 677840937 547660634 434003927 517066847 501908089 646780865 127552702 494448823 777845971 233931263 162728233 706459514 389988634 406992216 483862149 205415289 700289422 959983719 248117790 625388623 515391655 496502827 690302909 123310485 98972405 484369615 132300702 284024114 480611320 857900149 80909061 542578119 310868120 653730664 66635741 321633968 692477023 848548066 184579614 329404189 657072665 682048561 289790401 681580616 182494962 78596204 975175560 556767894 113906389 157130303 135873871 146406093 698448607 820404502 343526066 939101655 805968921 922979002 105712827 127336692 167524636 466013999 437898244 437893671 669774717 963782961 294881331 913774363 711385088 527649785 834495241 665703697 134551633 480914522 921588894 761196425 65073305 38814351 218290439 458784674 323057727 904488943 6394050 230831158 947416248 18859436 406959081 262468876 938842380 137949534 668042349 350216198 201868422 747375488 520846111 459288826 750019740 461880553 796155892 338979989 61368439 438437998 593442492 85976392 27529125 908552993 242865360 609043782 498176116 360763440 310305170 395168502 653896635 930256467 58362742 529716778 194539622 45751031 895811976 84618641 729109773 308279649 98065031 911886791 311287020 497844336 723957073 330691919 536516352 936636018 173489332 308087232 653666758 503246369 242646728 740956764 600813305 185751464 372584049 489370202 466793632 696510630 506289999 157054767 181811261 895296882 983726595 419388715 549748573 122178397 275876570 688546095 101620431 909323041 452141417 501128059 273014814 769474397 760129838 188568954 130470988 627083154 575117655 507355989 218908587 582083042 670904605 824279506 7066087 210784436 237222545 946014257 583075475 11289092 479065708 382132430 2739801 235443564 215602818 525631666 59485123 405753701 586048044 488029502 573031043 471207003 226206380 923292311 917409019 395970535 325920566 871780490 287116566 769627144 538607562 635552570 984985220 259419169 727941124 48628141 882743099 279226134 181300566 204021884 218098113 353906643 319035670 284348243 387611932 207307095 194284603 615722936 142798788 525362550 534043138 42842097 20091594 813983066 754230628 560233313 629103615 194783354 266591671 340252714 738223882 877546814 703378819 815579875 185617085 509652207 191321213 445308217 573757360 695662935 374355157 722802132 561057061 247344394 244419063 374909631 781069356 829829858 652550603 217921830 238541063 723129130 852888515 557488409 11121318 476296352 309851111 192952160 363348214 182765067 205342905 669407546 592856962 75030083 120283526 406470573 811143874 380536594 197337419 445761666 862122525 37540780 250213741 357802910 25929487 21181778 16503891 762799366 764635965 134481190 542713742 704163677 361775557 192297017 351193888 395321630 427804529 105945592 507985393 92914803 16985074 712328877 988202036 282945 299998229 287429217 366386309 753765291 895546444 160693462 621601371 289751877 434329868 279417456 462851713 456078327 98035986 122862429 664695215 325173490 273551138 536857141 242626866 658650264 423555752 822619969 967597965 852527765 494741119 463379496 873269851 218907650 608839025 102246087 584394308 248292562 130524793 963885456 617686674 24112314 141458989 524359753 76901393 955034606 121483566 997545777 816114461 225009547 705059149 841222913 371799355 77605978 982669153 53429486 943808636 4424799 294900413 259060036 510175903 650349617 775465316 8556457 589498538 226763897 830352883 517159434 933989442 524936496 721753386 590391099 196363525 555766015 57134793 37368662 279475195 279547623 787143286 561651514 751759718 26714194 697031785 647396951 93580996 620312039 259162019 223047564 912494054 482281223 31006465 138987453 985240799 625715702 571596742 583239457 551886830 811957552 863476810 83139455 281754143 232095783 963515199 391397592 60122218 709315028 14376890 739794533 169569643 673459093 427521387 790896896 59828990 183812090 52333885 900854454 233107000 54840924 906637168 341514602 159676740 978570408 33826366 388867239 964494177 990198665 353303877 398013386 337642275 814513263 952399826 147596646 18386099 526269766 959003780 131437682 329779380 715837348 583951798 77574212 465130745 451001965 63675128 120909320 91537478 503212690 720671818 872465859 907894339 3462244 745839905 524822055 554591989 280987003 55507132 137871718 149910266 594330991 388779279 698873090 363123259 196987943 868964521 327389471 694863463 799607129 544493463 205532984 163842184 79736655 303844854 477851743 850165861 353626484 900415792 548020056 431809589 272523479 807763513 609292466 877686866 52621251 523582046 771521645 200683867 238708407 751873418 272482868 142932647 156745339 208941622 630268740 513295865 868956526 520661810 660825311 158657141 903984406 382982737 188333408 255749356 33546438 476357985 52477829 10288921 394003857 323994213 495833292 589169418 959164429 886528567 986363510 336460588 94137744 989343414 789439729 609106972 513785263 315210023 118279006 147879477 258986243 524945914 883098273 248533832 618580344 583445880 435421904 579047522 576739991 846075893 327184367 89393386 710410481 565511520 440871078 169365655 528676299 623587737 281874446 126981061 818147735 423820890 605507097 440895828 740274978 740371622 415665599 58221645 445280121 438668370 35787717 17424032 366126955 810706074 726589053 872097210 810518178 910057022 742468277 808656758 913383620 754725399 7596966 272463487 878703883 750648571 333535306 872642479 806510623 80268322 199124730 977547099 147662271 158501082 364622666 846659334 622922538 710199421 22898231 455381731 690977861 987701769 291869771 228960361 866624753 646688208 12606365 183993524 601315362 953836426 681776909 381400745 240209757 260213830 982104210 980902230 898405280 414399889 782366015 514849285 302538854 777043977 542506300 798265962 276404615 404165559 732451693 678288987 653411894 264623710 633736142 210461400 445869746 433676828 106511241 722310569 237394874 926196123 95692493 521493354 413524960 597320920 489311560 111324912 793044037 491278320 612359218 60338994 274516105 732057309 453675253 379683665 753715617 986622356 254324885 805942264 268107102 67451685 220224428 399382732 125200983 85348803 260882066 606476012 356038097 222800096 130737847 678355165 294670620 435383248 835454019 988684074 314676280 765884949 431842653 578448428 588083005 735889375 756779092 965597269 278461860 75898971 561495092 588203270 322607935 829034197 40446441 280018219 721763775 659057251 518123905 516789053 50112720 151780378 505418740 51444635 726620894 388959964 774243165 192256962 805159338 66216968 262910966 276963110 311585773 754372734 113687390 8972239 781355018 556228069 228500297 700267083 954067054 638267781 516401158 925788547 593565031 347882434 657330018 896625300 155680146 859525622 708276014 169797833 63479912 936119153 62731529 549254111 857046634 968138681 853116871 365843243 532242632 151349422 256796381 149462739 617861245 432538560 840980970 729067315 995077977 627745886 171979682 834779929 863755615 401253481 35598177 1889308 732053977 238589878 70759401 356692994 251243478 610307921 473664048 716798206 20822964 960242606 771730277 22982285 657667169 900453166 68126241 494849491 667022928 607890724 792541820 409510251 396880308 205181764 639172497 953781245 660573545 335803455 280755793 103994632 183883557 254531687 637783135 847688320 257756919 745068242 508835789 750554128 178340543 926213107 466965131 807653691 273398452 885072838 877252902 341900770 581131403 511431162 236907838 272335199 114414723 804243175 205833910 117965707 12498027 696721561 662018334 946060716 468336717 503063965 615198952 42731610 125397479 662608433 427521376 960075624 536708531 990751450 869437409 749564364 250814403 397650837 434643892 104271320 29315534 403525933 972305532 996437851 13178011 606530191 65594380 489564802 130867097 240898996 42057172 381291773 604301783 447619084 55396342 900908447 42730266 790221745 19551444 476905384 265523605 675525515 94157237 304279290 402282909 684897133 473383235 240418183 347653492 1000000000 942277001 990513577 227895828 517945935 103606871 420419361 559632647 487810903 249109197 118669362 198813123 314798649 760077911 280375540 707314238 941959787 609812461 893007548 345815644 804798655 968226400 800786654 299787479 933391117 84680192 355091592 7010339 971772535 330612923 775102420 590815021 383746678 912955708 126665415 316242659 198460976 629451585 228609745 245388153 160887358 741222494 801336831 632573070 747580080 876520153 630412894 669900256 792335280 281472593 136895841 90819527 28662967 254454120 346238974 491015304 327662901 338907212 256600599 943277844 187654369 544572213 446802418 223283837 31438022 764290896 276049800 636507816 797394733 130528373 41982056 962542161 107750561 581468716 640768648 530440255 615271752 706936369 18239485 795423723 940458440 189669063 593873036 513456647 676113067 977832290 171655363 783813219 67769973 456772585 154399801 112406213 172248895 133398977 262811880 393319677 379276953 294846616 31505504 680431408 241460492 53035283 458800222 264508195 459750365 985437475 717382219 907995873 642659012 602259591 160148150 297454220 429068468 657219592 526129295 182909774 679521939 373301931 745070282 515733315 15285268 615581092 140279356 4405827 84790016 785725598 927907136 911072138 605923173 724251887 157017482 766953413 354483804 522158654 459528882 736706114 121165797 62845231 490267903 522171140 250067067 338238906 892041805 50231484 336786098 491098956 271122226 703088392 802577088 348846419 764254567 627294523 683737565 187504774 903013403 667959305 214204348 972621944 563557787 373868778 31185186 53363104 806634477 262469163 595381742 826369285 765918358 333419084 845701555 644969958 153998631 313352092 63294593 857085269 213740523 784296495 165773226 695519499 723113670 993544074 963705528 148198477 813651782 979836702 163868928 835489208 369694766 13507717 852834527 437289183 109643510 316719360 344245329 302035813 92633295 455411204 344168574 410968505 984330815 381616415 426366769 289277624 900225388 81427976 799179181 365633336 30630637 435609128 43535395 470535143 821743801 594688097 311262299 893788597 553694660 822127927 967255218 330685012 128682750 306365651 346493417 608514875 636819548 905548902 509448759 298778907 775932583 682446603 243088029 728917498 772353782 387341322 992292993 592687750 437253983 196176624 753161517 387823551 140065437 795748937 57707818 432587552 75158506 948792118 384607631 412621905 241921328 677847686 893376973 755104032 34741482 641087901 742207469 246356881 428768858 604314871 489029356 547265537 979873140 373623354 262631204 961544300 158307643 409989630 254251867 480412858 102389468 68714054 261719787 306580436 291689646 500216029 774073962 249276194 718948806 502417991 12740286 917442049 331536505 641725856 281552941 507392711 46194840 308914887 956760879 846167677 141740913 790223619 650638823 871694380 314617108 853357300 568536969 825579510 476286689 830549458 436410234 423552666 555557071 500273226 482277155 13922767 972870189 584012334 30295366 393696842 208684399 560507545 395816311 409459273 409945856 81510277 395609415 387227838 762658752 450316435 969080047 157057011 200034528 630113753 609457599 294313370 284289699 420884842 629154477 92498395 704022456 935113161 310625580 703289171 894300476 331433840 341315711 471945890 957312870 114670130 359761798 679069511 469534589 3712975 190369373 782133311 267720279 128746878 230277405 838153879 379871607 798026466 6759436 485313342 606932938 36455720 272349153 979148495 383884063 31373881 523535706 683645733 271861524 288559435 97592983 862706012 140378491 940651362 426953549 453913446 791092267 76846178 297571935 360268016 61220643 835967262 299732307 394420961 680262673 22927491 249886881 272833788 187140235 668381796 480421530 916206110 579571806 188260680 128528000 583642517 178715075 56976462 288526193 23357816 448653214 361902217 66807115 76166478 235126888 287911831 876851906 390963207 593659956 255957420 17479310 968501011 373199193 262609286 645319813 541380841 919166835 737867798 421237146 652914318 803653999 633523312 46166215 369446675 18767959 608826647 203798849 467275416 581619111 375900517 130161069 189227779 60142721 431456821 37008499 594008382 352078839 709013461 431550236 196867208 98883820 677599611 186528574 550928195 665268055 261681727 814886335 511243124 811315508 271885358 755842482 503829212 807280204 153927714 487571082 901250304 347025724 241284901 199334649 866229621 320568598 183890735 640860081 152935036 255617501 320421251 174629224 824180450 248064549 185545078 587454717 615553388 16358028 916585367 994102461 667767938 938111473 687796939 880459040 971719613 226433538 377923542 584741189 830818159 257084196 605187741 276900235 453184990 249775889 353426899 14199454 167855819 631882473 8379737 487164343 288547389 834701252 584951649 900746403 295304925 220269137 133666253 795520561 995068496 516711442 384227383 215257032 830919410 305827519 738479478 134845530 467838850 68385874 772417012 810069804 261878287 901693552 6033843 625247296 707325057 210065070 918415766 45980453 259711937 587282254 111460046 128960763 415026928 200797698 452340207 713450169 55266995 151388156 282733301 16563941 978773748 456986012 158723236 67918275 721564949 838828453 55968019 990984213 372660022 139167367 888273960 7639265 53189376 505120247 788569180 453008409 828160880 572115660 626700170 290772008 795200729 397117172 225520231 330918517 191379736 47904324 715475691 113975401 531197282 89495270 176331158 802279205 685467901 548857384 586462244 98671127 51168620 318962044 861886351 992979119 270429260 15958338 294307545 648002837 744858067 653651963 168972138 184369906 789762432 535659430 366771323 942809617 809477046 89871352 845805657 19333543 33805757 885599193 694000679 914958365 820891049 446101088 433017287 700739222 471020817 97966742 167584661 172341467 478121311 679026938 6083189 607250430 125193241 251975354 779934116 204314063 305584812 504736333 997319707 490470791 641454635 173737630 114851869 430363104 494146331 605071045 507935606 709216339 963030716 745830212 651909776 412516790 250605257 445092659 489999935 669141745 891805082 19716811 832367978 733263642 310650168 385956800 653314310 821311866 46016791 325596000 736800868 219881905 654089933 329773115 400018494 522519918 593573993 969009118 272848279 270729270 248789178 103049153 855048506 898514957 453276039 645328622 243205644 877574115 468656496 247971966 41813412 139119766 48424803 946197251 721008480 627349668 818268525 852050798 199186630 434256017 86837335 449661413 663508076 363631244 49354245 222251086 229936037 145502480 40811193 106198914 83922171 835102698 722642133 607936499 799205870 321068108 328179242 87138203 469487652 18630595 713319273 672652538 912137829 54095388 621628436 526621626 389691984 26784065 773487612 474646936 311503595 167740406 467924798 766666193 492842292 366814949 591798719 782280369 360334031 807934545 201326143 598652100 661625407 140620982 43964454 855079224 636174822 675549734 945068633 489409648 902441086 181139206 461978896 815450769 569700367 473528397 424649452 433806754 103090277 219203270 118001999 955925002 493555595 516995677 276659912 425220493 586676059 73636569 699132297 180399635 262237930 270858106 881477568 285797091 575138214 746901247 900945183 134736696 364040617 38128347 905894291 518239881 483072497 759710729 985654489 63180861 586224408 862219180 726483395 298152868 866436546 659736054 496884999 174618568 194219717 691241940 40252528 607856397 592134422 399303794 13410338 490427949 194681543 697021918 613946782 569374853 55531933 995632302 278690086 481089830 922783748 656404384 803090083 377376557 696009321 109586088 371103857 210384650 907874603 451687012 790015351 812985581 701061910 173235519 66082698 340252160 941165140 516760701 783485624 669383311 132911220 757463916 483386728 126073278 506208756 948360190 360953258 961214161 641880351 359428910 819090449 22689197 662258819 977486673 474093069 538822203 776084435 6134067 932968057 702686239 842092317 425969746 632650621 218545146 746237404 421908539 201678694 194702647 915837012 790524184 532381559 608947803 852652567 605858859 986997667 454961157 655794906 544708884 919892747 167577232 377514512 154235021 964333792 779988021 788891924 213493488 383854321 406440808 95054815 41921071 103860609 149166595 342320205 84634488 50553651 447269756 58677723 152733297 857174304 4930051 354142024 592527750 431106044 738625067 453831470 513081705 171494787 316127329 445364263 795658024 501669232 467523661 761931755 501974070 930134956 32834143 543418752 795199231 967400304 63574206 779024221 14474109 849825555 912304988 224834302 692919512 28400432 217665511 42185270 801331889 38113107 954595938 456244350 241663718 729422266 22545814 956218092 187190508 100511020 963774854 973841463 932318864 688651627 770186536 355526730 883736251 150668884 954024676 225647670 546820006 970908531 831086400 588080911 109955307 536508297 931959615 128367690 173734466 634586606 624927721 175751309 203366646 317430251 330772366 429174587 1018629 813337275 846593612 69515233 715909904 437708242 556224411 121607642 738032246 322191789 150340068 919375468 438304177 388599501 912894512 44207215 329284446 958646051 74297246 922362951 123853547 220720122 294332073 557359975 965697339 86576717 916721722 352155773 79655942 895416072 347988441 250340628 732797950 215574987 108846549 855260798 290572745 79360567 137394019 247408047 822805078 855669714 569986319 274162390 290232157 856414898 366378025 44776100 468057967 104697916 468346976 739538741 18032519 85658615 524995621 438480104 258319443 875920233 852841754 734702274 790755433 44461847 300138126 982925262 770411533 742723448 244954554 220269189 747868728 911458302 91040357 392508782 655759150 873520395 196021060 110817752 581364428 739697390 906413627 39626917 821352564 8484650 598857349 277870135 340611733 726985566 95420414 722078036 730415461 29344050 168854238 720644307 61141705 883776628 579056008 871336004 70764950 142691632 113318296 800320917 893734243 686880978 142574006 237432629 514546743 587461167 265080216 849188106 305345958 793704059 360156243 942163634 227351742 101646290 638420492 372474800 604474781 715032092 704672223 8622684 709714372 552504309 757512156 357717593 597189612 644531653 380784719 410067406 301792824 785935225 121285680 924246656 152271666 86053787 922563643 534215606 406221138 343548014 677093693 623809245 398743412 39098807 255313610 254087291 529075004 232540142 281455807 47265326 670899003 609128803 929758064 180293791 820381665 988787004 741771334 354124807 276222714 262474200 513930259 573297137 246566841 206112547 586505661 694639697 806980363 798087002 414093487 563555507 804231609 664275757 57421159 312949366 20411656 995255518 593588146 568007498 299247541 725848185 998029817 465003734 921534821 424743737 750365256 764418374 558586338 726126649 261124808 196727499 993600771 36848577 801668045 49091759 246521271 540596400 849581973 132865206 77645636 190266558 677012043 147222525 308774564 406776150 719757327 664515094 2890514 981421029 865469005 468332040 578068457 47059924 954102790 739934328 882471788 668134046 124276914 76068288 60471874 477520034 60856386 142122662 122137932 443599467 491786267 263532815 215099168 580066879 297103818 181049850 182565270 144878703 394409739 471398616 191328891 981966214 332080690 728271158 929524044 538776792 267061425 357791539 105003540 466885999 834018535 59713044 643859084 40355278 649054185 592225528 142910991 273363687 284548085 956055610 165221675 473483497 873453666 387468380 408772216 732863333 402950710 803677776 155737033 78868829 411559180 777052902 201965107 761024429 100084246 650745339 474743679 517066463 125228148 113172527 546227167 128249311 483779528 282106066 55048542 627721210 34330751 422936250 542801363 241360743 162588330 992550817 48964849 951844506 511461365 923743657 538464190 79688686 688689621 189626804 490116172 567732957 275126693 312044036 767239370 407515713 273734063 69296305 555762495 439593883 232333048 689188217 113669672 645307488 552090146 167906100 464855044 292676389 809296366 609828481 754578601 853737608 813022145 606878340 916381078 404520010 346963629 1507066 948003762 706194552 256499384 671554932 622718941 738705574 558180179 250891506 26772862 156213090 625015682 908458814 953352709 263184670 749487832 619430198 595592798 435604627 386348551 300625579 639957050 193273907 100504382 611457433 410995161 387272756 91097514 5749131 247607058 1 781856596 397613950 222516198 321302204 978578600 510405544 615936246 191651863 284281068 347436251 60542553 993423053 9810254 680833789 715317523 778202552 94623069 83333628 534786196 217543100 668364766 275915095 121338659 693764899 349777172 738101994 222042947 217774192 268185463 501804537 441246254 750998565 144590562 217325297 389266127 306247637 899048875 568940552 677947230 986935792 862172007 757584072 166787350 150455900 754181532 169152259 805958175 408437846 111724413 233982666 262398975 443203257 670847097 295005620 521243362 170534600 778524504 679366081 183388800 614244810 871945493 279683933 784000388 960762595 592237733 959531502 65139489 719825965 812410397 503272213 9507692 170517252 230323481 244499103 384303929 703934215 450554274 144562681 245427156 338730456 480066489 192119436 345586215 783070323 346634550 854918744 335103669 852462286 825331535 682558027 177437872 549149657 776465699 448226885 218508237 832341994 61297982 809331537 14693290 671061860 120716612 36355440 574044081 109732084 852513059 336847015 866433571 746891011 801858704 212208074 141089103 55311871 83102566 516241995 612950453 611314080 148711656 748796267 810600369 662866110 443530025 164181512 690964050 27909959 229673576 584776899 366336781 597683556 298378327 685092837 121297962 472210853 806661968 328709363 273707381 378575986 641888141 421829452 248593044 793433382 545125696 323723669 513668682 810686651 924822137 543747828 912849531 770049351 708513050 618269373 61496813 233678938 786912085 630201057 939140832 45742857 634231665 653053568 935331370 167490751 677795719 613542877 757704317 363783681 737485704 329763465 117451489 271026132 149317721 167957558 1907559 20007189 201429861 150251087 173621273 670253285 467865519 206630902 278568158 14824896 858253416 17726093 491145012 630233259 726249522 269375896 212691815 669710736 609133046 382417144 1372107 235215085 400871076 569247011 53825501 807187548 801052575 933092936 132971703 256545888 169277941 458391664 846749718 254638853 744052690 601398635 299668221 545290569 420232164 290650249 37838490 200420570 187088373 183933309 660682215 907260165 553635645 950780296 205359478 148771890 422684298 90727944 663699572 945764243 51507666 713886858 881452249 648785743 419873062 955165612 282945431 958560314 286182779 501456257 887710867 900497152 514219938 978202699 849176902 353180526 270741419 669463107 258048030 619713190 814868588 259406823 513006888 395420507 993786420 485793437 417456250 545356473 472125602 403871748 291511708 645047779 277947567 327102706 373982783 175706416 423310616 131198659 715747263 790646665 643298566 39588386 867191544 434334198 684371726 184158461 213230897 162479085 479029656 290889699 704803339 974048139 999436641 204001824 205354622 712356745 550659885 23997480 881914496 71823453 161029133 114115650 760316249 426418010 681245086 81974609 269333913 637816268 569832102 782543846 42186550 147101118 832537640 35208449 583230532 658192908 549998384 625239990 893163488 60572283 258584897 947922039 152405954 785738362 826532514 346086145 469982087 691367253 668190407 310140460 118411401 560303504 254902091 169476830 169148125 173662046 467009138 19057010 231391574 172335224 171154295 884561262 401212559 685918077 781353536 311885804 358822060 743113995 526894524 495008756 284101538 70650184 881749256 711673463 518411432 449659566 812132970 34316406 545726915 191829295 558168133 6341974 1904774 855138536 162158682 80312418 29214675 11322146 928485752 34356806 283785462 189682421 460569510 266343444 126987785 446275263 991698483 587184541 420288688 987825026 369587061 237720667 122254873 192069776 148034680 741320803 303424798 443324166 693515428 20817883 142914424 854156882 639782956 835295558 762800125 590554995 869804284 588877681 414588060 804353389 6676974 903888394 580714632 51353955 841383872 23384695 402067945 670845973 144551890 195303304 141020239 53174531 536888243 809470802 677332965 760567803 45770179 38696326 94856846 811495882 379777052 234271198 754789780 18380569 92041591 488344761 500637676 193984781 221173060 719103772 145774512 808444607 21071023 913077665 689858484 187061735 950805217 669399991 536356721 597569441 763845836 298477806 167537931 658847434 804478431 987931938 468448705 993998694 906139739 361600776 254734738 896330046 756034352 384480028 650524000 594741701 988303645 754718087 983051908 54237703 442737724 815460805 741698258 767280642 559847406 299544944 705854222 321737778 195767823 896247292 380591997 173039402 628471335 908942410 858817028 81985031 304543660 101199448 741652153 665625457 817042075 713161934 473883347 18258002 210660988 224647935 828221459 748268476 458835998 860955177 179860949 934295240 217056649 985904729 520168021 12814314 959485965 79601513 56067765 701144348 715005630 706047245 364498225 934133949 392323816 220452544 190487183 24167523 3840692 72463426 93906642 870199743 537036808 656175244 252540808 150506471 119940367 594265953 271304923 767974547 273577758 476675326 70873771 29373766 81074303 191659981 873010215 870917983 765439272 258068354 92020191 364229527 920167184 635523210 968720878 418813996 547778526 440756865 143340627 525585888 883597630 150475001 92341166 966046308 893749241 426683565 183180798 338905653 641309926 420525299 693384487 8381512 427095726 636767219 526293042 506691787 844747642 389098105 514910368 635954711 762570349 205966839 482731380 594803012 137181466 358791214 251710037 382842228 606671272 523345783 340025617 919453594 631260641 596981685 216607655 627564939 312524693 460539097 66329460 758504787 547209037 830200964 152972739 114304048 548932359 153640104 883347154 479414893 644773117 115481869 40651712 149131479 107058976 387442607 870110286 985942492 356969610 236127215 835730376 794473924 27563944 328671048 801049501 173033509 360129859 767199876 397095838 144293604 418002989 160255396 253414344 687368039 697973417 903130891 882208024 452874364 942966475 705593022 220853887 565011039 132938485 563621077 453940749 349238389 218172040 54298584 614821342 124722941 369039011 797207436 932578316 294840342 761546289 452340248 647821243 26650560 773904749 523241785 773141677 755317304 83897854 566905889 652233592 712553704 545305238 957219284 403536600 456225495 755855752 694668789 206642555 172422718 62402399 879373988 267128883 332406360 359277290 840448625 911745818 487388164 976487448 913396079 943794714 899050708 810126526 699194584 75248593 626739449 488295777 356631051 770790335 482659643 935819363 183493089 881621744 285022944 106247751 607355073 412797373 810343966 41267614 169388660 847128444 359598875 778229185 43886411 27233151 648670968 913429971 651489960 972601891 946321220 712111795 332501492 499110759 328331313 478232134 343106544 214373737 349068959 856725738 119760513 179101373 33035378 767435073 266000920 55408940 406066731 626173145 972539748 99782999 754025795 508693648 780388528 123861230 668024873 212750413 119329277 591525327 312110201 977925475 175719457 112414921 892530372 778215896 941957462 955729187 589182938 999940567 665387007 108443784 563613681 959950964 509194926 295127020 844506304 533017815 286314380 381472974 716570569 448862835 214359801 547765759 867140721 310418158 887390086 17574224 467614792 315566430 968070628 274035885 506581280 593541107 263852335 120213874 988600808 675805864 685917292 975481054 308653786 400436072 534109940 705746409 467957022 405566410 652510221 795031090 133345839 497475394 909011133 169733215 423782086 799031429 337790126 231469569 460327554 617346091 969201317 262445956 275694107 559935469 170114540 213250156 220930869 666214209 447627298 630769962 120684035 361410356 32979 259199194 744694685 511467449 282022865 685458086 340231109 41238922 831942260 916477155 154039199 857340406 98312823 734195710 166986810 956595866 245868864 603133225 189143530 925612266 589432758 508175056 279487237 146940812 454889632 380631623 113928034 155661082 700808966 156645092 534305284 397623316 546932910 700395829 520070786 677007266 379457886 188348014 865233039 179153397 341648593 161588596 200027385 771668657 327479097 747488157 579868739 562848897 800955084 628797630 965538046 53360737 876986948 557122145 16134847 165460425 879186413 340947514 439184655 282855687 302401421 259117133 357911101 707826478 243500464 915359658 419436908 426861736 125145052 891902484 808898158 716718937 585130708 163514628 592116421 197938413 976524149 11307708 414931876 708570515 50753050 768343287 324019835 419646083 142576186 734245778 148083519 401748915 630659183 138975032 190021801 274084339 157926347 308005488 865770856 572164185 531043009 681606544 480674860 134457204 140620385 657807874 37462193 143408094 291604199 579666611 502112216 228744554 347960783 113311277 817031275 292315745 317875815 310035615 212916490 536519950 969680910 443626074 103479091 607942187 179343026 655768021 62438403 842099554 379305833 92429687 508866438 793587929 65880501 94534014 747086978 672340633 126385537 88659422 210663615 131471802 41832778 135658266 782892376 61181865 925874051 237447728 341031787 513464560 126097743 426223958 40231310 693209446 847969077 841606103 432097858 524468754 34909719 889533016 188525393 719934073 464722573 997497356 981570288 713883201 27205748 472195674 278687608 299415976 47787768 854328650 285813031 521319700 306044129 850898374 808684302 695792254 443151223 604361180 861008750 543936898 249584328 64697935 419407049 112675478 419821048 778104591 184173904 991220845 954241679 365930589 252975803 128945076 944692074 190494514 835397268 654778804 262990864 566932081 707111485 859626332 424391269 725679112 502951149 75773318 970196783 771658132 2163755 86407091 243472107 369687212 881886916 435017121 943056888 968670775 16307817 57695070 287697098 467921892 768262585 303071893 675909229 164675834 948137153 826171051 286960122 15474857 372526794 826686660 222582860 960608756 533382262 232460086 910596107 199295310 243504969 866363538 489013779 61804318 856769536 107712513 426968656 570453126 679262169 701894213 70898412 953485495 905351745 542905887 536379504 995336942 422522309 589016482 195721720 720504183 183216953 436308174 525873172 393210492 233034770 533972043 587873436 750962437 176176821 281230533 924549845 257550428 110998628 67915884 603100135 913924952 314064885 818308171 713193139 905975574 515467402 601266328 806409083 525486563 350425780 115148897 140668577 848522959 933142300 208886154 260124052 282998584 85454823 284915842 718494568 754599916 805535850 925421070 366162162 321740073 448268310 712903528 263550856 625678759 685879847 884096673 7816132 443729903 12655281 671933851 265998892 857567916 87576781 909319594 265495510 608669935 565658165 102824697 344309877 472925725 612186540 159925494 621009568 233812329 497553063 338080047 344773652 617234666 831463504 759150464 749328472 952466551 274892454 606601960 577930605 610156703 852005811 849901565 576142155 455647826 247526458 585980929 537489554 700536754 944607491 610136935 995052330 79105264 168583889 801303831 225549169 159331594 367084481 665896545 123548773 505784511 824022076 158643652 600941305 987577784 205822815 829384825 226633888 946417024 113345295 590924976 329208399 945391195 934484431 809357532 131646947 262201268 179965758 806363089 72009476 42609067 809977325 889618475 27978483 692264322 662987143 105703973 229013350 333841438 897855202 19720197 58793225 25877127 133705349 238381431 531778469 570354869 50050161 496262858 249468148 390987022 274577099 63449996 605450909 707178409 231563053 152060860 536017067 214265659 638583115 929232193 644589420 996072993 775029441 401530070 66191153 781857904 137008008 995657323 48805354 593932019 796756848 138051412 177858582 226366227 728163909 225617362 439539902 343563210 141255846 384999705 585891390 21362 820727778 157586386 581269079 135067731 160369850 402478878 895502224 223316010 817610221 312682005 823895633 391664934 492812068 40774328 267023479 369129306 723908557 272627476 65037559 895868579 876405570 81665920 286799954 496982716 593588210 252655481 820454577 863451758 673499622 609244066 294287116 662259871 907389420 10953910 540842902 70536025 714020658 306796059 789202364 161742678 333023159 548727118 786682044 371693789 21004976 132868348 262425046 645519405 526286804 82940785 817822739 197736466 232389578 208530308 555271627 61030822 636544223 123612148 801677791 170731629 809388009 768847307 804371231 571056849 584673668 394104659 532792907 882905955 781094823 968414915 903302037 568909869 215174766 745255598 14245762 58955708 710992 679403441 628532208 540046838 258472060 631748146 670548285 925961272 8820849 691575831 844753241 74262317 351499498 559422829 944102436 234922325 229424911 473297945 554981685 254366232 917769192 981268980 560737981 101805510 113321129 417079913 260938034 93215210 427149658 795629016 653678442 893020464 124272124 172337674 635810441 188736316 91066360 586269490 171751963 840845272 127284797 867942739 147296990 352607030 835302370 736168082 322191560 259498139 592223362 70655271 295919492 140727670 740295137 727806642 939306600 138160342 451431542 108161958 647101721 815794230 86655688 58073602 960634889 17251879 814668559 800648884 833933054 874730345 348493741 10036881 431422495 339299039 920540012 442638658 700752555 396165358 136325753 908058213 532782172 53732477 496664409 467367191 531560411 228245562 675187274 973142117 280737931 669004364 225982393 271662167 608139056 652429580 174570681 279677625 443536342 115636505 536660555 78653067 633217683 907663172 489776115 717182616 3420155 712315934 695855912 923001635 939553392 631355453 385180486 331256481 342207626 374337130 307845727 870671901 539624139 514073253 699740276 613536337 315422223 860237217 739328359 308842722 944284947 297151249 153502483 859301999 323130113 185337713 254006773 246451825 779101425 516706327 691386040 292007472 326767832 610748353 608411461 435015553 96304252 239997141 702206877 720234655 930779033 151361927 885384265 345081831 94087135 237724339 634282544 364731560 93362740 129526335 396142652 623896729 515829818 511780123 596735454 403742479 182192166 610627916 528607456 840394263 40615374 622399358 95514379 116248482 30266416 906062590 737958261 346354267 588662404 14292852 468023665 418964391 769634132 721353565 820340246 276478241 745992917 373740745 63718726 163071511 830965562 163082636 54009978 50709114 281288631 82141845 566675937 836333088 553022761 643917253 614514878 457928551 485167626 844970959 434149082 285752995 36323018 434813706 549383432 15772327 313802186 179975822 918051211 265287712 112988431 143916915 894239297 21613107 458889014 975963254 988114852 936244145 544562051 105406944 33573600 3764431 413598409 409914689 882452392 277067305 990106509 136322311 383156052 600300333 70658237 660640890 69208492 717075442 994041330 299806535 798619388 269582061 724825130 881163299 971875073 897353266 407413606 891499094 880070802 571699787 96044122 402020481 670741717 959043719 817756451 969695079 433904886 826828580 446861906 210078003 494175644 737295935 363286092 848530701 140488130 118770721 694013511 486131370 45981639 600750333 160418680 616509418 14256962 168588695 9338619 982034750 164325006 2043254 830544188 128492060 720471482 650408981 106014272 291818273 233148738 217332933 641037787 753131056 543265074 889106731 505933206 402562295 256941905 475377873 168639464 50767206 292045880 797735359 126624845 67893505 18801342 868606534 47634485 221230777 964600785 197340533 103948695 263789433 736649001 693644589 101047454 35508365 431934420 386953803 499038656 569714660 605704662 611120429 701709187 185617869 610846651 476266112 784892214 975016688 965028432 355584971 167627314 248432675 384669975 913326291 713958438 35076957 12385291 527103726 496690524 494019420 523476573 179544937 494059402 821085817 756262627 424930921 656529703 218196754 972196825 319471313 454443471 266081461 542421152 115970923 371235859 51998247 797591645 487658734 585803820 607073222 402896764 821850482 735197731 273344947 861884403 59179200 905632868 237461176 382381605 592659619 114288046 704793070 646341798 89969355 752902748 913694571 193824003 794881580 721554541 240566974 406586667 186310444 609396303 842674928 251983028 95110575 588520211 203594399 38784199 128492586 301805303 589635915 686205875 407993374 194307263 946131528 900944162 282908427 237285139 73083860 270576502 602785451 998668693 577157274 257650836 87300127 485567155 842085047 755986781 571770778 798351427 711593125 277257043 558124499 545313625 760184545 971581642 148084921 838498765 771651846 440331006 83417859 97271466 772960663 219201982 925926279 335142477 866570019 943629783 49535317 229657313 930063497 606852593 898658754 752382426 321457083 255034843 700364171 33602948 850350720 250214496 397177678 94853942 265257148 562216806 166728104 275111539 26127002 909035461 640950891 851279808 985353276 1519979 354256030 977484905 214601874 396630028 164434519 80854950 541976335 955778387 289654500 635163696 780312269 531293151 832221751 141568921 295714356 709768858 362899113 421444219 121064214 74523361 199889555 284443765 695487905 973324906 743630539 925187930 476146365 330297346 847202540 222273944 356935728 182429141 535510111 735674085 811438158 298483798 128341650 529643204 409274338 49469361 903821827 31777782 146588837 39634642 19132816 145911001 846823316 2238624 549678014 513465515 242636339 99320708 825973777 809382565 829214808 103670623 55729750 147727755 118373301 738675745 294222925 377027252 112659760 406968031 163999597 464205430 705266565 112686183 329155665 244971857 784338003 88712959 793296980 631359327 708933246 317920412 317578928 585066688 8892574 171861984 708196808 601980022