4000
407822338 399317255 114107826 433578001 133352055 75586041 744486273 995604807 399220881 456770230 241896899 963162961 484746633 820286192 556111336 953305075 674860445 722930929 223976424 113433915 301343615 760857089 948462934 42142773 771954579 459061720 782792041 474330271 357492232 159160171 625776796 220707690 83662944 721766352 147245972 533194538 858004680 280556246 538016917 645820661 10956067 223289441 678375388 83959192 460858357 770854771 941065519 40771332 711488220 958548204 879015215 625038482 113749297 111409802 847898773 979724411 791700481 589622293 494336008 65012041 779947681 529955992 580043620 109868142 53224346 431702432 658296093 941796924 5866926 835500193 265180506 205807803 860172531 853023506 953978877 743100633 919765078 417453316 939985575 792667934 162105317 539914592 995278926 961494690 348296075 589549025 570281652 694919229 450477778 140318954 304840327 949466176 382700525 954269889 157224064 819018814 449199491 995006367 569198742 222995971 589529768 292262314 267453678 638100971 670433793 65592296 188261399 316518521 595055023 313501109 163947676 439996951 785445277 767889164 568188837 882438145 430883953 237263847 101813533 177733415 338396038 732614445 441211298 782998358 975785881 904766518 62658661 349922174 27511950 288206967 278891800 906377994 648117709 448058819 766322355 292029216 659566301 789306775 864027229 101201075 886448027 27944033 104949297 284465533 101135972 507741479 968100988 106902761 781093883 623995734 591645542 340705035 500871880 783623881 544748410 391682160 328639636 412086844 355823955 575151517 617807750 446639303 652938842 456866153 582019233 426769761 363385920 490038045 544762219 434703454 716787002 576016828 535998912 940722033 996644236 467669820 318986606 412058089 598323212 645505755 891609398 711567291 679920626 375885779 184053432 170256388 847221205 771872849 777863291 460747085 652063746 618211131 534539396 937024081 75908613 270760174 826075247 67660431 477198438 547947955 341775406 895934830 776802822 458260447 554732875 146106439 193968345 40795925 317134229 930185648 481248929 275043955 161849632 825783166 804540875 590325662 877912416 772978895 384282123 574040448 249959079 807896541 294827272 45038966 661598131 145955156 332230281 6656871 165621311 888975181 608749144 441223882 606170069 364048791 263806820 134443460 125347464 503037551 135264082 785851324 657724125 858456603 225331586 943265916 982991201 3465403 692110885 483810894 312750002 759551085 296217079 961917688 636427964 470700337 968271403 51773248 931612659 526103230 701477927 132204723 566566281 309296450 671521620 146465296 677000966 577432477 793798292 876532258 943146644 843518386 514309505 834205993 674765319 189783426 528871237 352160640 246911010 724305235 646192071 714595003 407299638 169008780 943855773 714724706 585549967 732521135 785211797 262256909 149159103 461443346 768068705 690751464 899109865 414160359 888890873 886575512 145799014 445028145 300307748 187230409 986033990 150312095 582133108 389825588 474201630 452434697 333425371 549798878 181137203 453281738 378279654 248345317 681998171 19607303 88945265 94349756 254491826 685658103 377867682 108724755 389816136 599867620 683569211 186107571 208916172 976848538 716433308 276684232 428484753 19590143 439854689 465133554 769629159 74942512 216232322 728582899 939123839 860025840 589905275 47086459 385660682 493585412 628049503 143730852 735564628 2273408 215439081 787931803 795376383 602109789 907789799 591124358 195000215 316394051 772735864 265370042 711642105 362646374 832850963 142017985 56166751 11655513 909288523 486244410 585893616 733129965 549516519 566912636 823113889 848764333 350279674 150248776 165489682 86539804 291359296 199168445 985262127 287409959 454677606 363649394 572452650 973944473 348698176 934038675 680935031 762874454 82567707 320452765 295618567 76932512 816253317 89928543 606083519 585577454 543460729 676446423 731096267 521080019 26826344 238986891 644179379 435294559 853040043 515735029 400431948 401468856 310484108 797708454 276682975 514825892 908846201 911743217 222875757 889131531 192351308 958873850 566548513 82750801 524080558 493226518 846447844 165975290 250161403 717110674 536185546 192305427 782471805 676664206 661933548 936830966 367757877 576367876 69008868 2684980 374317720 218167579 707560832 325649204 763191750 726034312 758040340 979938378 873857539 309265163 184057140 732700908 901629352 401805758 996514980 300337634 268978916 93206775 6167198 608881786 518013329 31640787 25098253 894837907 646281453 509168189 482860880 812756015 615441777 868390416 617863745 860864813 708116481 996448946 159486239 32839491 958585716 88668676 829054891 87762230 930259657 219076271 907298877 254709040 550564589 510882068 311031035 91480186 496807488 310410791 369736996 891536839 216525307 694760855 320851862 55289620 13223565 936538236 656905217 1823116 820630008 287067411 18175660 442825301 500388753 698868976 771389198 852452164 220272064 417932257 180848497 338754899 968198829 931185547 531562407 466294526 485148233 336440319 841903592 229709587 634579143 91769678 765816578 109982777 812057716 591739530 64975022 47992005 83671000 252789260 717286060 337446498 804559505 107683347 820137286 684980138 758324491 666689172 234124150 846027258 510077755 402740695 485539952 394226274 300599530 936433358 61667795 134870239 797558638 426205285 388907854 390203556 434339308 694988215 236001652 809104683 612652176 521089918 333834184 261774474 739710962 711689760 731107489 857239204 448899716 330897329 831719339 149361815 599174545 643607801 392349555 293918650 899670207 153600796 80822095 330681090 498185088 312247467 745115373 244302387 305025921 744669366 172853161 487919297 74030782 898949818 379754765 518839823 27016800 893255586 204677375 912754792 383318039 895136495 938919859 225662357 587689729 665187801 453449625 775609355 369630966 546756819 782571846 303166563 868229651 950055342 874433417 535366640 877274191 717679468 181780365 531444854 391930957 985692089 962461128 804626678 198163831 267933835 334357846 55149787 819861429 267381542 76916935 736557940 335909835 833401824 180422983 702113796 989849231 129180872 180114911 241835366 222233279 956503695 964814530 493830637 19925623 491047894 375337766 734486340 59538667 150790842 154428038 449462240 25201111 661281174 562354587 778144772 522797023 389468631 399363851 407178169 930313717 544715784 360794891 929467414 367901794 755224530 55184152 903857688 854994332 789348857 557013438 934642266 700085949 193379164 306454095 406565458 109825674 277642190 634280672 521881066 779272875 348682905 108454491 877201563 953786563 40904846 258390243 649250949 308305420 554731098 244827563 250867065 974336124 629644960 624423192 486010106 47273769 317123538 20511400 404276434 519682843 480170799 281577967 178579067 846745387 290935196 562570580 516100101 225418431 466215365 548773034 477255755 641496304 871045738 509718470 438125574 453980109 298072853 972746228 365303639 979416201 818254488 957777169 193563473 735870971 52940736 105065145 99603405 406834985 938548155 541085460 820325031 483136329 736649684 261065058 519981728 355277469 300430931 826815434 10265215 271658129 17096259 582568668 224388170 490464205 218342245 237976658 131844924 344068155 485231662 635616441 734807621 103579873 889444661 717757569 632582633 126418692 871639791 878374369 62099043 827303746 674223657 593021564 496456948 31837637 66207648 112505003 146895367 274321253 293104112 722340068 434335234 299609531 949091974 553864543 533197941 52882165 620333154 40151632 201081767 135440251 810624942 474477974 166680875 744049284 686173563 562612199 319226948 779084742 758049379 916889038 801231866 755528214 785714391 133535393 644716905 120697343 688851814 132371721 67431012 373125176 269283438 947237216 348222269 173804895 557734545 848920626 341330877 152923471 552750874 611569890 85614662 342378835 776755632 548230131 403394565 534111182 639794023 743931673 706900246 722193905 907021163 496199694 550501798 494156309 412318757 581500835 546710142 403603058 99313820 692296246 809974036 222186867 537790071 399730210 894339661 133347860 95682286 716304783 255518159 457678178 919930103 554695694 612473682 252848337 223992009 471812126 500654561 713373570 743234300 480212339 97116759 85982959 464931291 323750229 158867793 622718278 891577834 300455841 940700021 410318031 64775142 64693508 449934645 482481409 405105563 406573814 520130324 292066025 541043114 230429783 812830423 353090555 672284099 991342443 337873528 551691140 878628387 448660255 476642279 526475665 973342534 163823615 436048905 743513613 1610104 229812327 367337032 728203197 385744769 6364941 941343196 804605199 964571393 609714963 457081844 782316879 281194108 623565552 446346353 585698891 135358829 404100865 907552645 194523286 106378187 161945434 193951706 360511500 81842950 117986947 855265671 583279066 89397205 520642256 741498706 77865908 757614372 576954564 213674519 928376858 237010624 279686540 813548947 792934978 86214943 944859255 726663641 26135792 613441315 274823696 584092590 774171741 949545441 137677071 622010512 201974247 419501765 803835679 615924735 611691998 868410901 273166980 5138535 165233016 131521690 206385846 893690303 183611870 393406863 951684787 380263461 612597731 828142689 314016057 726959378 792168129 704518357 964378151 196311801 807653884 757268132 822513320 911826006 835916152 908338809 834464410 323539272 514248061 572722289 612846072 744899074 245145871 56126289 550469876 46151899 739865270 479118495 544535678 127418790 579868279 198701022 558422721 349720166 955915414 248146028 374139155 793397241 473198365 247609768 975117902 845532356 661256376 825854875 57291075 794934649 860620658 295944648 473081093 45426157 368509516 625150295 500425233 529548063 421773589 652251711 959903129 890042476 280385435 337169618 446898503 402604345 653201881 206178103 921248056 473550323 429500752 750892733 368923386 441533902 456945891 828664501 987052101 143752788 158686486 607364483 225971155 217202897 187540693 843323455 16325179 615927734 679541328 978509914 21878974 403154607 312211805 407225735 962769698 293499891 168513450 697799117 817629190 652641721 29350341 5907048 393448949 98435114 660879812 55235665 206132646 645805764 329640206 203585969 126369496 731641390 84924085 848620181 321504912 388824821 402154371 218261187 801834110 385552665 447899594 633589234 239498519 754558178 796837896 70760749 190101630 845915816 881364596 815386297 536110708 838270191 389685869 110604631 326922350 425194124 943560672 828187926 713618456 858227474 293214849 750571740 567154711 670150650 874467464 719120581 77617102 50113034 365954787 687886850 798392621 175917785 687697196 773200878 439116730 454820418 462174019 771078958 758017538 96539605 890279205 61320210 431354429 312176555 357263238 545354016 829048877 587870447 927154264 556979747 456341551 927017852 648132404 336153300 846085099 65609964 614302245 317567446 14468455 524833710 413821919 971384736 177232298 250709336 449952137 73281951 198658540 961069453 455611922 698623044 584833181 799667158 522947515 387674210 537863108 274533179 606191118 399925821 653059761 44470637 286229079 287368802 393122626 642867986 18971109 259452409 117286970 278574314 269443767 59225060 112207045 434400379 174773702 79401233 697547654 619395369 732647394 497535749 956531370 200519121 84738424 187198192 540405108 242118565 455528483 357085267 503053577 294292099 756610670 713761290 90579336 906015947 406606631 467086224 193655459 237426239 420152185 47006977 385957034 503513970 354415782 840131865 781649285 4712990 843475590 301981854 977921461 418403118 288503263 659725972 46315217 786043062 120941514 365720120 666002919 201171249 755505237 875792471 392280472 662897323 128399406 897786738 192150530 709627585 601878520 71415741 751749090 503298737 543865818 755721726 329656426 990136977 527516692 858907870 168472728 331759411 336061066 789320192 704380881 144466476 522035976 830201438 723163474 485705777 681856386 991919409 324929379 388511863 277179964 292512789 761348813 153839624 453972334 939762598 983995663 478631193 146448778 411100900 990924303 242737367 107266983 267207889 3276969 867126970 240104692 617300931 158603947 528680729 743100060 242053413 111389326 614430814 63875108 661697032 945139666 969933265 186016999 476594238 184029761 230199875 26338163 739259158 414742790 770397280 308411685 808563716 990553356 160789865 399862925 400389060 191419445 119340154 351369925 145402200 671512976 312853929 386679314 738341342 456338558 656431454 571575942 431543364 49537429 337314755 746555888 12735323 965420904 364047244 387581138 84062033 983521535 903733295 488712266 181124753 895854369 191544410 438063048 953100067 62996747 995203216 502958981 117676692 441118385 534667994 124191126 708612214 745554736 699877498 175845543 284392647 494379583 486749916 846128937 25722421 222725935 661810817 624482521 934127831 708631557 234749522 982366712 582226276 974862358 545031087 951230766 62234633 186920146 782210243 941815607 835124348 843004152 440849925 492115966 369821162 437764869 748939876 225800976 431694544 36972956 715311631 556047078 831180512 485182189 156606481 900563332 147091100 458030955 308094773 777966345 686048711 593961964 927694303 849618089 465362011 506049200 304042778 482756924 404362817 660317071 948711297 370860430 79760562 246808899 753625518 91709043 363185715 938791868 836421485 770031506 109392118 685127804 669065095 1600246 45619974 908361619 935163513 269469762 412665994 507344612 197622747 141655778 17881767 744195680 82085400 31876520 217027417 383994079 559881238 852124299 895580956 660849779 540065540 86432597 805354728 421917364 542210749 201363611 157274475 59381759 101944812 12408682 653208295 766243373 913451063 378799353 941257336 812867510 636348558 974503726 88592231 267107388 743045772 249425189 257524330 84367720 151957256 438595483 627952161 981049030 856201712 399832029 554506074 480954811 257063046 780786531 174179903 777424777 277875246 388943348 645273893 58440163 303247877 420020651 709757310 565444668 627167824 30299357 312545620 664143053 431654232 954861758 841919568 108006354 434605813 780219043 769880353 501702596 931441563 467072038 645184565 206457044 457925329 302151620 864899239 683381424 619338348 120677885 314225190 447509365 719298209 199684425 886270596 418795282 180879955 81493685 8524648 973819544 465443846 955549062 937884666 118839266 69369072 408497565 160835668 564657602 630019882 509888808 254469203 749614207 499158449 578811421 102839751 419500915 45008391 723223454 684910666 224414687 65536913 738846737 766962697 985688743 314166629 958437273 585819299 87633351 625165411 596355502 180535666 677735854 941758255 609575604 218831807 811964964 195457329 940796986 78164477 343980783 206216952 914507370 649474290 207056146 911017655 305532783 81555473 658685392 983622366 110396085 109585407 3890912 431652862 777582858 598418697 512289465 978312325 259436599 837812979 88369181 456369008 30420 107974219 716793604 586535782 753287655 518776809 91295506 168216219 63781617 63351979 201620866 539947446 532510257 535243737 827496148 682566295 814361025 517493447 547428551 602839604 73753408 306281454 503072235 739189801 719607114 700885339 700273906 80558429 349393331 185574648 669351066 291294896 96699773 222659869 506610158 612766314 849690666 982181303 127813511 550340068 699014862 733514373 299871872 768488024 149027479 464495268 742298044 84779030 567815929 14921799 685234943 158764865 869290832 249741009 316300976 385721445 498828023 720757640 151157469 257854421 38048462 651344030 359071783 929877688 434806046 270351233 450389938 181427904 3740846 683812753 142360536 879171168 614050529 355666411 379392849 983784256 401416911 417008899 507009103 592320711 435504385 295839054 727128609 246856484 860929533 405312321 283202182 721300468 124661063 900519591 360373023 106226477 582924281 797668597 607677981 773368107 572815927 672535117 819501809 55093651 849122219 942343063 386211175 386454957 154553334 578776432 465441478 353082779 782822653 524641590 714875128 296602466 855696025 111355675 803972388 292056449 348696702 75941113 943063805 186760398 676412200 783432264 764226194 427472865 97831424 8960952 382716929 336476359 455503628 572881923 834227622 29856332 449348919 723521361 833265154 857178013 858624770 688913038 359438162 418759116 682497192 984394588 151556640 266326068 694111678 355827895 553245892 923426510 735068819 311132096 13182248 851236694 921453503 837218443 690758282 352032426 943341006 698187156 570025554 353909570 287525836 273331409 214599153 72965927 712419627 467956016 445499428 621154560 721711409 664236589 914356738 812980142 987954453 839674601 919849643 274229647 735884201 81358611 593058006 983971125 859853008 920313738 677856522 148100648 98953721 318472096 378022816 505959424 856127563 268136137 309679416 845388065 228182889 260290044 637177912 593240579 287336790 703777142 118724703 509445643 105477326 765796736 209692232 730675676 989751196 857374333 292264518 904701551 483735488 404263299 449905939 398414162 497740627 885160689 934297343 297125212 728702397 406303728 462495335 809955696 702285591 506732689 948218235 713029983 376563383 389232945 157830376 4469844 261466080 277498005 620459440 966820940 583062649 939708621 769744755 941938655 137985923 873011855 606088302 816693628 262269686 421139380 266721354 13822363 78145404 226213145 263297821 168402325 312513361 529665364 582638243 6091699 841874756 507990211 558970261 32079148 234278461 380134646 821343448 725528046 391288824 700221655 243560776 401061720 324757299 692683881 508309367 94858769 933339677 640223743 625031235 716577686 330065884 477060277 386570476 498633863 963153398 603391040 833086500 142019870 321490792 694423823 645611193 153452637 360154217 832873621 126326017 69802641 284260396 996009098 845377245 741289099 572624628 986906763 923414709 658432499 323470338 737283699 946372168 914660581 4634388 406307091 270868069 632678267 636816558 40113191 636349907 101799551 34083340 487451863 370983048 476250129 85573591 505941677 517331025 890701170 251198438 406323907 216228410 27269002 691335995 3757380 929036748 500237164 891724845 464396297 282473956 602629737 107405785 618759384 920207018 375245562 434385498 523732156 492189340 768232449 636114232 660564828 927877972 64133142 695551877 502940475 322921350 532469419 465154227 19324807 950248326 156460644 296637131 761816372 673771036 773282555 370017767 390085080 880980793 201112724 622045713 421562045 34244678 912332647 420915451 470364473 510585 375349385 385694051 455222022 659976705 813649733 294678183 340182438 706247538 143256918 813307501 470167550 879114238 977207585 170486916 706464246 969559091 349477511 448445370 731489055 785382383 634718248 258932142 343386711 444406531 659562990 638662447 410082013 314625962 446989795 686900373 974509134 3285687 104583711 989944090 758647009 388694938 432253742 19399515 960980936 956340888 257803839 115588099 769244377 957392769 514046581 586072888 610191088 741001158 361763109 689244076 37434382 240208798 628688473 455509012 336600184 357385887 328046677 457877704 734665241 496953008 945626519 985237744 388597534 65791870 960358794 196536785 863434801 533469327 885476706 641083272 88612160 311367879 141438525 859664130 637825560 725616694 587232106 100609842 436791643 695861068 785238224 883199771 890117610 303942070 235596158 540459605 969391483 387302508 449561868 838289384 514206453 704854514 795093973 950820649 709689423 971152826 661107290 557013808 30956765 625075863 354834623 447385475 321452277 154075334 131611829 462868214 497746071 201462837 858540361 704598648 759766971 135962206 394598369 191618155 485445492 382454735 636820804 818490082 917430324 712851814 152287189 679750739 583407797 845269303 439512762 404073466 697242973 899938041 138551125 158678741 495425947 872816538 931365080 52338808 160303025 291532656 850382550 468938839 851620940 592124445 36555855 846012149 690001055 545898122 158434922 257433268 417245813 335646773 89294038 872469158 359043650 474320124 674376064 64176375 547663817 688047730 394304089 524050825 311801947 534103641 546800210 138561038 183559306 746132541 675528728 410597426 447181895 441364912 991049200 811211654 111305498 102637527 909368415 607986024 233214920 872604632 684154157 231483446 155010839 715703495 462680944 707120835 572527778 710376739 610394669 637963189 362652821 531911316 200191415 191306310 773684297 526307576 256745123 66406089 344527729 695665447 550721846 21187207 524050481 941564310 54334681 589012920 787075323 731530486 255189315 512744510 551336069 122678810 195637132 867017487 102499986 969569236 876199305 890760439 237921381 44500171 739153014 677794258 149217314 432628455 819012913 157520577 987301200 494740591 437837145 884431153 447193602 998220819 188744688 842113111 180818464 335532336 387992894 223432509 47953022 87884632 627295159 164237424 216746926 365617759 214420612 400843829 494743878 133042137 709822351 757520450 552025316 385068629 858881062 902196456 418963142 751349937 574870893 44004449 491286693 246792633 787184934 372979478 433930292 511571425 465336691 372996428 694333696 50906313 643850679 680591365 529236778 59774564 256132968 562698521 393712139 440047604 985016710 983777742 617425600 131168276 894667971 980671096 575735451 711152229 240093828 400598862 858732247 985083387 504653911 273120926 727058563 85755315 264105291 250232332 776634183 786705413 931874541 979967987 639214450 866659406 78847654 845144200 241738201 865159896 17880832 29528383 762313493 9236563 795347423 994136291 170931726 263622722 290710234 900943924 862482774 449763193 475516945 890597519 744272922 500844804 331693548 64324004 423536672 27915829 158720333 448433906 532427677 274833820 9939612 719363869 987477142 677421126 622079525 10397445 513235563 489006923 737380472 346655912 282956981 276131945 601438118 165762363 215849013 121811956 749904256 813159844 412252103 709919329 52720331 760371710 973552568 641505312 359844565 220397440 313231702 411953172 804111685 984967155 288042950 128265868 575109575 982760801 100660629 362200400 940306102 939069543 958656573 556278897 158143912 611862736 815473966 906222668 531373143 629738063 244190149 702508047 36626304 917951668 578595679 746855576 876008278 63158490 145596572 553151556 883000523 103709648 274578946 284132423 733926056 223812993 743668757 332156024 610347014 331399503 358340874 543911729 209274639 529835869 664338649 552097288 120568425 983213330 94159998 574619995 827703228 83232281 942977899 576716107 928351398 596596486 645088926 165558663 574656012 710675784 543143931 100160395 171259330 97096924 725375609 989745403 965668818 537588860 108417513 560717902 969993394 640168923 986674784 88909796 243966106 213860785 650602253 709052079 758013573 812255835 261863640 650453880 702328193 175752977 913012981 190174347 279755923 100821010 478431228 614902107 84677447 912646616 336718112 111843711 669691841 890085233 615624718 127408144 100654318 819432278 751683518 101127719 597586104 440253739 365388121 247509714 209344450 346799537 83178504 513005065 738745091 398495851 228312111 584512287 597657189 679334731 360580638 233666421 310172449 8287203 55620087 266932959 78908112 815510878 313718018 997215214 897422516 807827494 152395498 781192868 945134732 129305427 234430951 46306279 187029653 85228607 515764008 953372965 611548194 477432827 220401079 625907598 829152199 240473645 861931724 147854388 660097294 567947878 193675407 864391468 634246190 324985893 14806859 644214425 140761041 273971006 826672498 255090270 552781420 250950491 975775148 585558877 754406846 183670988 605083601 432154667 143754695 121262155 346690101 652881112 937210971 560738304 167454406 442353617 713323573 813704092 611536841 691100735 884732261 368433328 461481343 195933603 304882367 32867434 853772383 679574969 708400811 980431079 82917626 30877449 908859881 852334735 559296108 8272234 769743334 796354444 3448546 542372467 777451832 832180084 46050713 482355962 458072343 253350232 928660909 997497241 848437888 14154158 942356473 465306902 719273851 876314009 842009837 842239867 246861525 443955074 878181194 845877189 434322129 547924024 444599530 201170071 494456779 70878058 374447921 845553625 836191508 725249906 592269099 246840391 424884725 944715001 414072940 650505466 676702506 728774025 728177531 715927273 50592247 529257454 34695449 741319709 97918498 225104652 52032781 262498272 350657871 393835292 270985978 214680506 148509567 81605724 770122228 945125996 144101096 21017548 763652853 588050032 335211823 679314533 56080768 861699488 240070483 14207715 53770098 784129904 551358880 270612262 933475471 423481771 801254829 341619364 345894269 918665629 618054045 682048520 410963942 510030398 87551460 391003896 821617432 210943548 795937790 111247197 520895935 516851649 126081786 599404963 809912560 109972761 822801266 28511823 772566688 788055351 364554429 756091323 13179881 832104643 932332909 421741223 558877135 779484286 28835712 382927549 735430737 645097917 623794685 613919501 61425785 41743318 301629006 669115203 762297452 234742469 936365895 804085768 330263136 537118426 246028176 685136684 64593970 296742038 19847940 37206800 108264294 278900034 655562183 280119491 652988734 330838110 638017783 42804340 714747444 347876742 66767966 335720557 445337360 811674422 421077689 58944129 50651672 474734006 4270476 698809704 726803069 810861351 686938668 449079513 305960165 919884896 566286335 857296553 133894395 904603330 201851852 913562305 545600946 138038516 749790394 489462760 682695650 13388424 349882948 382586500 699541581 132997267 882659238 380159491 128911140 540728583 30057795 406025996 257824094 625303840 470634681 178417537 139977081 492523691 795298268 90372572 399591596 450857898 353032311 879553264 909072314 990838851 138329218 725854611 691461511 423411582 735964992 533079696 400488825 887901858 761843055 591532510 127172796 31955341 102715179 657768769 763572501 498120217 504500679 130573327 220063001 908961602 202678772 819209472 285938245 840657702 843556835 506798309 731670905 553863176 302935086 506801397 512798876 515478130 363045365 917059280 650501342 670156597 887546432 899878083 462657577 173001020 402476962 551959267 943681683 616316119 901736298 649667072 77462010 247938464 464420230 636787603 306962723 268427879 688118506 680243287 390356513 133387389 323889757 971657643 321361795 494875771 891274533 391124890 277534266 421810032 490167209 657827640 416254870 102211335 738039861 982908770 505248409 600114622 886593983 369500303 523881679 280498515 151894168 762694392 19401276 773320461 686061238 27325450 162869762 830582112 587625873 150179977 74455176 932721018 226132738 886178551 325102969 406182579 372428390 71745657 536193391 246744162 840533188 545858874 52823038 456042169 278920817 235451942 438852906 317586212 777640095 981360912 872080295 881290282 749257778 837871039 460876458 3250396 472649895 958258060 924680762 71338038 166068221 232407430 783269880 410306522 64795313 915020696 953537133 47197274 667759183 529720332 461727130 363895323 196494392 948896034 659609000 793533828 279466746 722197027 462835183 180540683 497375044 847026955 251931184 235654160 480118832 367161040 594348850 695175489 400447657 641549257 627572461 7456146 961100486 244200174 324586632 10983389 170606556 587573604 145353385 827429407 639854648 196979936 101762510 169603358 780340727 276717508 487767925 428306528 608362306 727452827 338118541 139871563 230251476 972370677 494981413 370977461 818983317 664328421 214899019 416712556 500457591 509370609 838944890 527426522 321261443 184151557 441223893 224109090 680242949 864844179 835116344 776813128 339168679 421905871 688512077 495171771 174829010 822266098 781089989 572610288 232822662 235061872 126714928 554620528 964086057 573458406 569433496 450881976 803270144 374297613 102494167 720952990 950792746 231243240 371072392 369377123 941121185 332071874 151129122 230041506 301947389 184586074 511624602 195044865 413582564 156328626 410772972 702899748 776920538 238219304 632103232 912101789 644940963 965233642 77098086 508896102 771776448 64871981 732533498 762996493 519240839 389554448 429152362 93271562 756465690 198471319 350617427 136592360 31610709 298233493 37992372 396906867 809160134 966976748 674000981 878062244 991386585 96113193 535128227 767467660 788064059 763057379 509795894 940838088 680371306 92993091 698568970 368765345 182606016 224097440 314608927 360395809 427266404 57122350 512354933 381759819 141876255 75804534 971542383 681029147 929569859 502606419 42538127 263472392 794002383 849078254 199606496 451621967 819699487 160061852 164616931 498835809 839716489 309453 224529899 555421537 288601877 954131457 697817656 124731370 426983764 364565636 545948943 339339456 961868406 771169143 393852263 785255358 209734390 233207703 369782770 377606707 357710941 128452051 444819955 10381608 55980338 264532369 618393400 720012695 559359191 641489181 30864186 81465023 722190460 407247875 848068547 267964349 732173862 12540599 220942047 97449560 510774029 931767898 704726785 799693788 463241174 287338084 763188047 800398953 606091323 579735322 276621713 782532287 521928347 689514953 383998847 310082486 829439407 632737862 819795376 979269485 326874155 140036865 589321456 637160465 784813409 26378434 217958183 276785382 86911634 783712403 836752757 558275798 648319583 627618507 475988641 534465372 157419492 93004096 123529183 106431854 374401803 720376812 55331799 804087002 511375065 798625067 635232091 926404881 754080455 769025900 681539178 241485786 563631928 908332486 583543651 804587919 382719023 294255173 401655244 691935245 875146248 536523409 790482697 889104720 124286326 244035061 786042475 971168636 464891923 519647636 666842481 321593424 37149011 502101820 582692077 868121789 781007038 87761916 354585880 575015167 232164036 660163187 5190009 453933759 984644790 708739232 186323959 273374165 477337642 122050595 873502193 599418742 278563593 956512800 9128809 715442346 738702100 117120689 332621509 547583748 75296521 668562428 308176693 714856651 44107135 620857321 319424680 161190455 474054361 348514703 382915120 629668444 989039321 108355325 658226069 17272064 691419836 571969159 565192574 602810359 841211314 157108939 654776327 562539908 260087972 275726158 839339900 42585322 760353868 676600245 690058597 504907967 753693743 795972426 857370495 405047729 721546341 68438129 688418160 87988032 731386519 842533794 953930399 839628526 792679586 942982117 754850774 41983762 800344810 645208680 791342613 617758182 726534337 227883652 701017388 162438820 414222118 199853431 97526869 683939020 794433300 538658013 276642668 346135340 20382254 219382195 37062265 440335976 384013545 285934614 232574244 752236313 51216949 348588879 968725934 434180292 816841896 37785408 77084244 827602054 800371680 251690510 87151629 129120021 211018236 896227024 40455984 455482295 434265743 434122859 995005095 797041692 91395365 189372389 203072730 487006621 620813119 623176926 495563916 818783444 100868518 217284121 973408120 693543350 776682840 617920430 992307434 777774912 923387306 295959719 285518980 242012387 72461135 29375620 180475452 552306519 476552894 848714999 282829420 928272044 808692344 739044329 658531179 363017247 534872001 85457303 417078321 843653564 205122450 527332229 407756439 549634445 871166876 860002851 829294899 488478150 84505132 596423161 694581452 601579170 698359660 772979058 833658758 135120905 312175829 816594475 158619228 330122425 837505467 76477829 942879535 336785955 191634462 288111327 324970426 206042361 554890890 66208158 713929799 301923500 482252608 127135025 748365948 631163399 729363517 84765804 191343312 964651442 689626465 312676313 767538214 802963104 884740950 298949951 968267488 684266609 257106618 843202675 204036956 903305817 157139672 983122235 161653529 870914456 637955819 808326271 475901697 381828248 78458232 997856136 714686140 747321922 733970198 670922052 88181866 262466265 453945892 259508825 307090567 149914434 318420647 364408133 433723142 597693769 864987210 158722222 581063761 501386920 516960928 463155450 887989918 1566453 883481642 272304477 647991012 805229716 854757794 448918716 599387951 981642040 199373693 976300831 694386302 494239724 398257713 716229871 125367002 451668223 344220509 188829370 281549583 474454802 398486914 765656824 115353171 654261244 238985439 243271123 682924383 267061068 286888914 651579706 609878342 530486903 187460473 783140513 474887498 548492461 605227277 677229509 123652637 407376015 194765823 700526546 213841793 222211294 845716377 447271979 419995853 714260346 591764972 980373004 98058135 438750414 765000669 893851319 325370758 590976222 232771946 664203682 303698427 440401992 149777006 709616623 324630881 403986836 29528351 67105614 966976742 612396080 625325939 736318930 588692945 784745232 137131046 620442964 136600614 150197361 765225034 260496788 774153014 594430414 398491636 702344511 467939796 644189173 864423531 544688613 878727236 344387815 590506095 814839461 647697085 651972923 354489952 203835921 874786680 953553042 136126474 93939879 523470002 364263508 509067474 602665194 43060035 580995516 803678573 932508009 573149249 442446496 641715561 463755609 822081298 299705756 483814271 248960795 49320937 591371300 143496393 897086262 444009425 221751431 598515334 656184273 612129909 281030357 432723295 409515940 986673056 384814764 586680244 790859444 576780952 741567445 57163681 281428433 544357083 150601655 407914901 349136643 853862016 240496968 71942986 18490191 147713295 908842885 877481157 754469660 806113087 972369161 248442762 225502421 366552191 701563461 510902459 120875840 828135350 405356290 451656394 84943178 636148089 939390100 663890384 985254243 211415829 329987663 257739343 462152389 795032885 863733897 657842938 646532141 274884476 884172264 301098455 883780341 726387072 783027060 870145066 852150480 675122821 632332216 309338351 640650662 618350062 664456632 44134084 748217820 856104391 799124218 678122649 142424154 916802819 468101240 662441169 571799190 176844867 230719385 383015413 539184467 532878504 210907916 559766230 405340570 904446411 853035947 189583533 476517346 523939622 480459138 552690275 563541756 38017864 319260866 846750316 727913713 733896258 139623457 257180017 24699411 832302877 173424579 230400489 688619540 694585172 879117444 722823150 515185527 99963075 353891631 629795034 898241039 693585996 779339652 168094665 539978986 34314890 436055076 205341284 589213034 842544531 560506878 798505616 934299484 124588470 234467861 496952592 105254951 717851125 151230645 98992895 235160737 93709438 747349894 498348827 41771766 585079532 868294460 920850123 740107439 982472299 755278065 225942470 782621710 295587534 884103164 268837639 797513043 188213007 404248731 419796036 138821394 54536070 82072475 899663458 839127190 840640456 709454404 684505466 952398744 912313429 311430406 986236715 393740489 130415849 959084641 961812776 394173441 975448532 579683567 56295777 171605419 841035097 942261190 728325589 772193440 38809524 20990817 957247870 135722889 885348965 809936609 833081578 804969433 354075578 668753233 273481165 339864106 676043013 312818528 816926064 966511950 345908361 795457463 97651035 716126074 446966766 99072362 776606029 645328499 95591257 628596999 803221895 137865227 385387452 307639782 954167182 465644345 19410678 32282735 21628082 236704300 284275472 672768080 642421311 952618798 400443465 762935594 834443564 505152542 368158698 399885977 45772499 776008186 902624526 130481274 506329675 611371687 476829374 296932944 898891473 881500457 255554669 114181610 620277529 538324321 359511808 624036473 152779060 492406994 104229716 167696463 682153847 329414547 420995866 306032620 447149110 140685886 68770759 455386588 830182468 594539220 437821279 490805772 456084455 159435524 118750055 971046365 395098937 722641773 700429163 375194474 507264445 278018551 980623191 127431528 865956472 764717684 883664430 916227996 27826792 173608975 88283892 178818474 693153887 796390826 582482233 237379566 252548331 987640502 45201539 557641454 511722312 467626285 802637110 345094516 580248131 473583790 189772654 793902439 446484080 397678514 432491108 193836936 99937414 586103065 671660053 436217007 721923058 390710770 20477066 403253973 929820470 640724539 247313913 330642201 964874999 364054451 756401384 726506998 536263831 544415012 362895234 824675362 953696018 649059527 107073238 558093811 310406204 865659874 14082609 586503871 46239315 591320376 355729598 393179399 109808623 109856578 50307981 434507289 34313114 203561952 513070895 820657483 177665226 42850045 283659736 703539919 189318057 927971937 8398094 150749245 938265449 617787437 517539142 456917780 313462506 414077652 51458514 452579668 563877836 111304877 678291677 127999855 580617001 2826564 822556853 39116499 156423665 449372520 813881229 298916127 11507521 632972868 787888970 603949726 111797716 617963317 105474981 709109014 672316650 903167300 561534441 133151947 25155180 220301950 223501651 993602491 836855579 918653777 288314835 754574677 931272778 556513160 680363109 965694188 701979490 248907869 198177492 996481974 871139750 295660683 855466729 973169723 885779173 184670335 69877649 665410964 615395799 280538759 905034851 476398908 887037210 528112427 558516835 424946809 937662001 547612832 458175385 536296158 295993206 787666397 699806566 733385070 950926371 599690408 182457470 93044751 782426998 736237899 549200663 811822356 877026496 819020987 708605333 518106589 447758655 159994280 808380412 253684957 772659772 560756801 790826075 359313786 537106212 641063469 241242272 600550832 256500929 738784802 600529194 112865355 63361109 644833217 492707985 210690878 102278718 885925556 572950943 325634940 38483689 364150185 255562986 182412847 690846608 914556030 431471714 207033182 43211922 918841743 744067485 149748504 674746098 1581506 462574267 646320373 11328585 46994038 518517220 681091013 82713414 855077151 992070412 799982634 800225870 181277323 717785011 434347639 706306884 112140450 43302341 568295495 614396515 824613335 769343924 951795542 886270438 727495614 746982132 991401898 747407487 666715129 621449536 884305835 968372225 868237770 270180342 310964386 96520264 217382402 361649065 104169388 337226590 53346693 637640731 532731562 13592428 198018185 158873556 683931990 137799499 23872933 222120319 555429394 818222985 828724222 123888241 517869527 617065762 776953295 498108181 617051577 869478960 444352777 392586529 711549411 365915031 767159052 56644112 141662819 473473945 853769245 87800560 340197585 637916333 747539176 996508448 396766517 518048359 216002777 302159289 508331297 732466272 259675807 964396325 351123522 832191967 70539932 916610197 996172891 208851595 665434822 177926202 173582716 364810231 142207388 244347161 436382840 63202569 728021716 978096423 174404677 621608394 662856881 116495177 974954585 277101759 226523240 677579147 819556584 188362259 711784301 96949585 433438872 498011468 307590513 128924972 364890330 394947518 776475583 641335418 790556518 358995774 221464445 53647360 271933390 203152300 24837558 142361202 729885426 607277902 200873375 67571029 965453131 564551762 786661154 965437506 683512606 721642226 533505711 557119280 579781388 533225602 45892538 461468323 542218635 858127093 394230927 509794727 136860599 431136748 498067334 532306670 760144574 547921624 111630117 236750591 36333657 736866149 239827154 641772416 495614767 250384972 559554364 283917785 955970200