4000 999999001
101321498 303874743 334932054 743039372 887684239 33605381 386362118 730214991 922942081 706503964 353370026 538687674 188010578 207596938 679040287 449446487 723225938 680961557 195475974 914382707 165034023 252179735 368883130 163028117 825439111 417871872 299514295 613978907 633569483 595117939 982635045 604893723 510057610 528551327 817938914 123060255 901069714 235783805 809758047 263248557 799466273 226533672 702058940 146260400 38371258 925717951 223849184 501160134 396182892 610508852 299133322 913561058 913699545 110104918 851092732 970313867 214543556 20901910 155264642 27136902 985841099 840408970 833367846 850275325 4841485 308357679 890782728 193001123 635003066 952628999 359747984 352641290 193417946 834276731 607703924 360205885 154888777 155692537 670378190 326706629 37021837 548818486 629453881 901445702 879780365 859083909 452202077 465944692 720501002 147806406 396379913 878104121 652950642 596241602 952448225 31134489 614227624 459609111 108457134 470658336 867725934 609850211 650071425 279732341 298854093 289916264 648345429 642377430 355349761 31175458 992170726 198464877 118790186 280109290 192168949 315318542 318694857 379791783 552200038 443530240 733396606 571033949 66316379 820414562 941850424 323814487 853204297 177974339 529643492 679436582 750406091 550385612 499620828 955885527 962586478 985929654 687410626 632638346 845454629 285948722 340702716 224703771 502189182 859361494 248593199 158459887 379885105 885596385 305371196 501968043 702684867 196757326 903511238 566459575 285219738 470847883 232401874 198315960 376875846 36583152 248165697 299170434 744704381 800291942 54709897 529035542 724454597 731073189 291086940 275416656 316667227 927097818 168130528 72235897 786892561 85032937 261602521 837094188 639341937 176853066 289687042 31872559 568544866 919871644 780384648 978283618 847570024 772777135 729792866 131586432 830495398 81686511 103100081 541842184 593437363 315989518 271760596 989631297 872957451 84935628 926901581 238965284 770179839 127894100 996021766 494777275 652943115 362397073 821009424 543947455 36205091 294031615 902819474 917124852 608226442 889370090 919805742 671804679 359595347 752036933 39770006 967380249 272597498 78834529 625495173 778084290 59428933 957849277 684357905 665554196 561164178 914808349 874826602 243523631 304944961 670977992 314714458 223964203 115895815 201646800 777371336 587117350 423105816 65588988 721335147 109809456 560133484 655534682 477968150 59943967 149772779 630318589 766046655 287609542 597589039 227539363 370322669 354421332 470473470 278179960 188205934 883328547 260821370 46894165 53618465 720177888 936254821 744055486 998666617 278595052 56346369 818056669 187697382 678584145 801516544 887600539 620369785 923375696 776927074 305891762 271345323 289657102 181196784 11576799 575090297 215285768 801075137 727026297 100405279 44991814 593801229 66241211 908084233 132409561 302615510 317038037 651468866 236500487 598483085 377115720 971754988 156788839 768314397 861505840 907188824 909641531 335302101 498974504 648754302 827250772 495016733 572142006 40088714 500341818 218194751 687061056 560928157 953557573 71365181 266029021 584484209 976102208 724894399 876169616 680693178 414913364 822498711 498043468 160129239 33697942 429705470 932276497 648487230 137883870 851380460 714112112 137351940 883950391 774783522 329204472 40932833 992299362 19304709 516011169 840948350 448924029 904614460 789613753 876951209 52300179 780495691 735552644 288591110 427128812 102571550 87298292 672886020 688421158 711817820 709599569 51505408 450839774 203123928 976080375 246931443 466750756 736862583 566873683 123660139 913647753 872142463 403773062 840812678 71616239 307875209 369016643 154630503 355114137 210499761 832962562 780012396 433058433 234686208 207138155 528862533 994720047 206062109 870254935 895869273 123422796 531326307 184214957 353771840 722826174 524396509 30150585 551499558 962032592 410176395 139711857 184015540 713307651 753030618 531872008 378656253 677644256 564528782 475398794 980264490 554871753 839153859 404953662 710397022 317789004 542768885 404926412 290955820 954962436 605037658 762053291 776766232 349035235 275201061 799437379 67567154 997026871 161050909 861417237 699697427 593964129 612847817 16621189 814414168 644887935 977370068 832065289 66675157 786268915 736698860 445907807 325992270 553592029 677824059 947348781 178442150 238585768 850161686 645034706 641069314 9920506 607769426 588855140 668875814 690097397 688357565 497759965 789687082 223475563 948434189 796254102 977452530 375495689 202728125 119658159 84485034 690917558 146022308 981009583 496555656 857265305 280769662 255385246 594731449 21230321 74873106 432380220 260590842 599907082 931391823 421027092 270590901 984031913 811444215 888346294 798891069 793223588 940350774 529367764 655498262 66847878 88811024 488258042 909978199 982453737 27014748 903392689 792968596 620275755 654422209 389347523 43511265 37548372 175761143 116683140 204729032 105489660 646861211 664623614 516485464 410495878 227051349 147155906 67296699 957657291 970284890 367574630 849307113 979010617 878463149 94208432 870799435 514970896 204305995 996135449 131316883 28107158 620609354 443104049 438340460 343414754 263805532 620977659 400283252 420304044 841335514 478651066 581602279 972061038 958636860 881263006 96808698 549567737 863695659 351736836 849769409 33300625 600652908 397621468 870671512 212674485 279921316 200198784 930912184 662853112 986654609 107325409 209621743 409288132 166153122 426072278 829222083 125551305 340360079 337800703 626361604 312683239 328221841 556072823 444987665 659904187 413376638 484329289 720384687 61846312 423498639 894973978 107773724 718859971 707888459 888204052 85448376 837035390 556500565 623690526 325779691 184702026 392757619 949692388 644715363 810191182 102378078 470249790 280294926 852559707 661969427 221403230 902703044 614035410 942514876 419784425 351782016 673996425 781082398 94572993 621210753 270221311 132800306 966671635 472849285 187095217 270010876 106515821 899113579 884855774 161694662 252043988 416900563 469660466 99486763 597265183 432093446 128858134 1943759 190765180 435760532 666061402 469606047 850245313 271876931 44806594 793076484 147477703 193692214 543147862 745103490 318242245 219430939 697585277 830770182 401074825 766514463 707560400 237199643 884029053 676601779 282610049 931695854 158860410 477289268 438364855 340656817 853304590 712195693 347624501 327796569 383279042 529852004 713321750 47826137 394337073 74793207 500750661 709253405 107376704 794749432 377209243 470297670 311385638 621656597 439958009 260361886 721255722 720782591 692014464 303468534 196267677 410868439 876011110 297643120 595409688 390546406 463716356 617178591 314934975 808244739 792215925 74114113 493637335 305151800 710767445 129080842 67328725 492236671 132520237 261937060 35041882 636006905 418888158 820819392 531829599 211019930 566629866 671278100 32103981 687718944 497931073 597244579 85214608 879928749 369366628 111564920 387808807 68561189 134198766 290228231 765391657 794301234 690845166 307892674 587686759 731060900 356222568 432493315 88479325 905241352 318839002 570819451 516344129 216852912 21333138 636573684 820459208 161029991 436416804 815320544 188263863 862975279 967760376 642957373 29012358 324507787 554444617 523045536 855001392 204504181 50746265 758817350 914030616 64671773 495572067 405718761 645176842 200595802 941792859 560186353 841145025 331352230 362052230 199361861 350228419 334470700 156408800 56333613 700944365 457187853 356018490 275158166 960813993 898009484 912793883 731751827 712388367 787319773 668936675 326813802 359975313 357839499 357321627 288540640 603101127 363053379 870040163 681332869 606508223 638700351 61175459 931092078 414081480 906512728 987822914 378360639 874422261 176381801 629396768 70132393 33848376 519423346 283649412 907828028 814202912 184915740 142998153 360832848 809360387 272373864 795940860 488753660 985062574 911920867 740270170 310217319 679138822 161281739 278398343 93998277 443074437 894411258 179701562 938197611 268283179 859854042 713104046 91687150 863451857 121578227 249008656 856265496 668977610 818096513 802194509 956033601 643905049 669613137 358906813 919494602 373485869 492891512 276665283 263788121 782646903 535734266 878050531 919291854 431498249 894444652 398918594 679201008 200578961 102951735 164562320 647659007 960591045 675135311 288779572 533610240 612172782 878195929 264228791 1530435 424946935 198151521 25847133 598047858 296256231 932450522 661248779 99270377 926108917 842269684 23163342 494600936 102759301 297157780 867585173 426411570 725177386 141102951 48354072 814885388 12028195 998891367 338271899 786168751 480314397 75591443 971048071 26670997 132343377 892369509 726023758 508236875 763804827 510932240 963290192 629776512 669791438 510485215 282542532 476383181 604308470 439897627 512059081 359492343 608891535 682192656 985362343 383431851 530620857 359253324 837728896 469440011 297297963 901715782 500827681 826108181 16995626 853763070 773979351 842547465 582979190 616276815 576734617 175481138 875394840 98269469 597515644 396593467 15437757 623930332 915788175 645447078 137731 477086399 709853710 164884323 785678414 521571703 183213430 105865002 424324297 684531553 916090031 454575357 884007064 773792709 904464655 173411556 471632537 312333932 645794617 771039338 524887636 956641010 75954295 235072872 251462360 34020691 400123208 625204371 415160088 344401231 45741059 368505223 889892520 795588668 821976337 880707583 845080470 653315058 168266163 286787507 358972244 682017889 104425106 767650733 852002708 630579482 659223496 560608848 796559931 222255658 924677582 36538182 829208735 759933166 422720193 598476106 943847813 465839722 609744953 394748543 179508838 792417502 960018496 779140658 521540146 441477477 570876190 324090539 83935720 587073224 85123838 840091803 244157593 313974478 352843043 232406835 905276897 682775270 395935647 737506493 654216749 403306031 543938587 739414339 578479758 878415236 753200435 25801836 807616140 112645355 667120198 207967479 636916046 92491124 148617801 748473167 464577269 407314867 246142649 915089598 666496749 626522703 729499608 159980692 810840886 309280547 173308992 713586957 425402 418772239 412314422 882708377 4536096 255617086 186122118 276291357 509950473 616845978 81827155 364209266 176825711 833867627 208836595 321310829 78892180 472727178 461671463 373389586 491495234 200861682 76423374 235608728 247102142 409696060 320702559 248503773 811382567 125118019 495497358 319937475 859984268 322926423 30435664 295432926 509491863 141146627 219045313 478580812 996575748 820829284 459624269 597649279 108370500 285789825 95242508 218575269 804649086 576177296 93855433 560938328 744306558 68229326 697902354 749399705 827796474 511754603 869428118 910031284 370556350 139182894 41258815 722539971 296816179 563087103 951817299 180828846 740983896 871289401 76884782 668066688 411004776 77772254 764362679 459275879 616310287 160282510 574510835 913954602 137063155 6219923 17056458 820524908 839442943 528690085 712983521 935732892 303732095 804298733 555293019 105151887 466002560 849091789 845790784 630072259 7215060 976792835 495955777 418348315 348448032 267611382 542013948 24934395 226726791 48175220 718753347 552821156 864418027 705248937 366699620 676684352 179722778 804006295 465345287 856177339 898386388 406448240 642529672 328757702 758880054 516790206 829507918 814896687 150088752 23760741 57321297 708738143 324477714 952074694 910125357 713393475 850873869 411362713 130783356 139954738 205427198 54325213 89021330 959682944 779665462 659377022 743793656 517823884 5031039 332164529 908715512 934577241 618248414 67568176 228749557 140102657 797973358 836292061 22806505 962291686 545929916 638029952 709099408 977564532 190788515 135140634 510399177 700834705 749262181 323588022 111676082 61139174 657653768 854555773 566443626 603874286 832303733 197287259 649298614 785532509 13603049 236297621 917732485 795031108 208363444 308056893 4983794 436022796 648894162 309951573 948082935 847739143 979414479 371131657 617694730 755302449 201232282 97042598 838647418 926479736 736513727 152761136 176902623 362654459 53308602 229117650 29003150 23099136 626181451 382595167 624114724 396827286 581923612 30497528 498321183 694326631 975743522 367725901 130840350 513223248 453370683 473249281 83601266 397250070 624045834 595042686 563807761 511339743 575834957 497651094 693811233 402538247 241284991 553537108 43997788 263923683 516572817 130073834 445525693 873437477 103717998 190072859 635715176 962404739 814577484 931740438 81013476 403266198 889516680 685892356 929910510 938089144 520274018 897043828 198017162 89888955 744499897 859922429 50722481 915959296 718644629 852537495 313417618 525391174 588169437 548673537 655263205 321955326 141430394 813504521 653803890 814545698 586652251 926519508 356051155 863301483 780434099 587445574 840809205 656951089 361660372 551051478 901806856 537193012 670578733 45723043 388938907 29277254 129490104 699301296 543244180 447372151 919897530 792053481 552962450 208704356 150778518 998932955 317367557 366240854 668408362 426498404 613379700 973499186 728916665 572337259 680011657 614519935 102946520 812425902 562908236 819935941 932071879 269147106 403242696 446647568 434079123 159508105 826551533 210006480 770778071 259941837 637043725 789258720 215075847 997311167 936146855 889960 187033847 860366695 865810575 31359148 504914098 289246410 971008860 678200077 945776779 906192113 22043631 384710635 632823351 413097705 845554145 612385242 417088224 887813661 239396936 671755729 208110167 9609231 273887709 716793140 452188368 330302773 295614064 62348537 889300180 637956487 442716322 558365648 84641770 59056539 821789755 901369566 11362801 380073367 614384169 477785479 655268171 772604445 955364814 461341066 575759457 563372964 197853670 575676118 481955618 814025503 463428010 183902166 484953263 921127735 750077009 363306884 969276741 274672774 499370647 290200274 221198158 18883991 803699531 760856046 95575032 776112590 196500010 79535418 315153729 420277201 811617232 625201322 110015083 567241309 143780597 254718004 572062094 615074106 203029734 41021613 736840129 408936947 701833854 130346497 620824331 661759565 866076046 16555237 764270551 196384868 643502085 16767756 559833889 28321524 866141440 210527207 934746834 68687553 760865548 458145503 335353172 127456000 366990608 297036572 928380796 473046589 908230783 16778074 594630323 794891096 183360934 773309977 195550570 682027485 930395603 225074156 545724998 645550629 570573526 551493196 212481373 179468893 815405185 403769665 235794810 428192463 761082327 415821081 137558659 152039170 510680268 606061388 289916239 523027803 203070836 350721912 253591308 441260485 238847168 848520218 195444813 293346385 250339047 373667534 768608422 119236551 273408304 265387264 315622582 479221999 977745484 9781781 910135120 583041803 187762934 861877308 221249278 309672523 615510634 56301165 36761902 548162850 175702805 769487203 35920247 276872683 716974866 177030143 206798568 80615707 745011881 677463503 758858287 765766063 522261916 961149012 960006340 409180185 557144269 736940071 4221533 292434778 671021462 782325005 108551626 616668086 742587038 683583360 987931564 139085934 884753411 132389209 100222824 307149100 54907586 221660464 252694925 316261853 87469032 751495290 58656998 287058437 861013507 988489736 638732814 83518535 427077670 564091803 514503790 439639090 945212898 925647241 106464167 583588289 184387445 480556715 557575366 536396268 763785055 888656139 535843138 575839083 536438550 684841013 877123906 755203027 720726868 146065452 883472294 27650257 77943061 572632507 82469604 320237123 456367781 138509362 207825898 318792924 829405456 83144800 619123738 936807179 904101063 927729270 134063438 684334862 221322175 509527479 500954279 116403781 181119453 116836248 729191780 579370016 714147468 813306662 422076532 588026711 350432759 231954827 478179598 396475357 771671617 540264637 821705281 371923862 30370901 244337210 864370743 535472380 715460886 446820111 724462004 730980408 569113840 923380451 142393485 906217405 993604399 826497905 171295080 370690223 272625914 438734474 17214777 106821894 794531218 992466298 132365475 128854699 503045548 532141547 180197837 797413716 156404010 901723428 752536586 592132736 256136378 3276667 837600729 712459051 6597296 274998023 928880192 523580930 767390475 797173220 501213655 439979451 591611821 891617411 142049977 422600340 131119039 462908114 362964504 287974458 624983444 18986501 373282738 338954624 569927944 904379566 570138294 626552886 44355612 662307392 793800296 130704144 542152298 136518287 353701436 631867421 325318024 848191396 592566343 407628252 595440804 649041005 666890044 899105350 555787157 796470603 38273988 384292923 954059374 10554144 297879753 757703829 592780928 779551075 931545986 718731474 515342315 834162224 673841338 806904990 599607414 322146233 745697129 11659012 372678345 607778047 671215348 999079665 758158996 63665107 428022780 196601786 572312725 749725065 833759871 134460856 562981099 812502350 354898802 468827755 400161041 929174072 165359022 791861039 600553871 59210588 546691513 333938104 47929345 915221537 844205949 871975267 742958678 683934494 352923573 573106105 444282789 683586910 441751921 478921494 223892593 856874339 136510170 241624751 874964434 660038713 691199563 575018489 100019670 674475166 258718052 858787471 744993390 572695314 775600874 537919516 894238220 959953096 370503140 750635316 262994939 183610447 147954206 178050399 709120925 297769898 357377775 449246977 962584244 397363866 636035867 399993417 744384987 230781453 223376763 305717903 789480586 97175331 490719144 127180340 221543895 461243632 602229914 917465208 270534862 342870611 769373994 105634385 956031478 29603597 511728950 294799530 537401751 225232434 296949987 345031403 247228388 126055625 394002375 15437314 23192216 97298425 230158168 247173918 150294570 869945608 712553270 84128754 783108551 336308024 871504092 121530535 22342777 908846102 923162943 732687882 748087075 822339697 933758489 421941323 587024257 592314474 298393679 729129651 433704754 421663062 606881768 995835436 95848970 685036795 609275577 820977505 119614073 552038435 385273478 642860454 112999623 177452564 637688612 895606913 272311448 17960831 288925759 306261761 903176392 592990092 770857666 379392229 496446919 277113450 366604086 220600578 530879141 837106957 369572213 965303593 219079381 219125327 354980203 991876804 18545128 221033172 764951225 598593704 722040664 621803568 506760615 289084324 992282195 895194764 79678073 341593117 42451505 831310503 767535834 907177959 777252839 6268826 290510516 928582914 641506880 439145575 58611935 541139977 516946825 26910077 247311116 756043688 736300288 525557111 741752432 8749566 5598590 84052990 926976882 568993186 268806325 222886935 400090548 711198902 223736939 651365977 522376796 849939622 317924687 768561812 636910613 613994756 344930365 710045291 496285353 440271573 928754679 970054613 368186461 529079906 679208440 969018344 149147372 227245971 921152176 878027914 917165110 395621677 84277567 648599453 776437030 202302243 683369167 965534630 439041495 849562059 83061507 738172130 562997452 842048195 217641607 387789523 240738560 642212607 894528146 57923123 493286653 946037082 237360421 416167484 977947122 230928066 430811848 725459354 272473376 861995552 502698500 78415814 359655993 556815130 412000673 716017710 394278983 740375658 263743195 39866392 385405079 350942767 940284071 995018805 535138523 711505713 72615575 450060447 567348807 199661321 106730054 850193167 401650678 777259273 919946193 430699352 851913303 302824294 133155200 152093602 349771879 677337004 929097212 785348021 490891235 112703523 632543614 289111182 822706513 878670389 913216691 969051253 872726926 137940609 104667372 397571652 16932825 970410687 417189616 19344739 267213400 687142609 797287276 453968720 198203348 468385738 761141301 673169831 694883491 124970637 418453374 154991915 386817344 966319413 994523794 757923315 880184002 226198729 368137715 773880568 736303509 244164015 86111844 370528851 962217338 276430417 870175176 662176758 255557426 993507440 853414681 942815357 511502916 429277540 303516285 873160310 408293868 820162309 295056165 912121977 329395438 589148567 632801003 542724760 763121255 193197946 101886211 868278168 640628363 164104513 138816734 526528591 98853531 948718968 395312980 710549662 411374212 617842220 871600578 390172748 970290981 157637006 709676059 172555837 501407256 45762097 969090554 708967408 576485858 704243808 527989134 664666871 185356093 536152652 491982036 388078010 285170238 369897421 963320013 671803223 462975811 777852812 382021972 895943825 932905583 904732622 579112296 121213381 839651039 767985294 528405704 439770053 457667470 432647534 41391086 96478893 805512155 720545644 437050052 722911678 400785541 550667420 789836084 624383287 993594828 837307000 302171821 71299640 803076329 618167723 662519611 916167292 551527627 437041032 657174863 740270145 275322065 821904158 168839497 791683747 610837500 492108080 598563202 564716989 368253824 963179010 156927532 666671950 59934463 717435636 371861954 916584167 349686492 485633407 342945220 137686633 791822302 779661651 156733657 589930220 175422598 390562387 505256880 926251745 741834795 254577750 175172303 979029512 675664995 413405224 805384629 943637156 210346099 294749420 698591316 870273712 501428696 468156462 314862725 828202090 294923632 337918380 121631980 961344606 116974042 13759048 342788675 833129628 37155682 592706797 341549637 577206084 588145066 779000601 126791940 872876804 535390400 657590478 561165885 433942564 624678772 829534149 561449995 263068702 556550015 534804481 174288520 805738825 856315304 962289496 493542320 132886123 968278962 484721865 343120230 162411043 20346290 629351707 913409231 867499540 803455998 639625428 321899294 483457540 787956273 142869083 787234616 871952818 441334266 862322318 307308544 517731021 603365980 100831116 623437632 882519642 194745222 832227825 844218566 727516344 983460532 787275382 465922773 783298407 479162033 516416998 336075205 325028951 956006817 318885100 91389468 693429201 42173600 46502872 934692012 665294260 90486537 867496981 336160582 799794009 920666683 229539722 818026268 396375455 803737073 936014280 348537744 90009824 752587521 472781538 782036245 193629315 160072153 903531593 390273796 53331881 497116151 710090363 332238905 172344752 525732567 723176641 360182711 115534349 203402521 671031030 46472477 443882856 682925004 423418408 680144468 555158917 947330155 965579437 933925772 112535326 153575869 13995835 338314150 738991653 334889483 435366567 501070953 388155899 764027464 943648015 86528253 1354476 349858103 468664309 305994203 255736106 242317491 792161817 851393684 818891200 914512079 894878975 836330077 73877444 840408314 393707874 799221573 683899946 459181400 674669212 522730350 354919644 877516533 336214108 677101016 740153613 422557798 455368770 486603797 813503436 649139121 266780905 208000046 917820444 720504458 783428228 219019125 506585938 601687430 865372174 717467490 13106512 76184395 905341842 948136326 304034283 467708907 840427477 907915362 332823033 487745900 16361791 82208121 603742255 265647321 554333670 844153589 445079922 817463145 918449406 350267744 349912148 756987554 278570668 866423595 32579903 419928571 551370749 937400652 631856205 578729964 120554873 257335748 162258687 5154005 339383405 628894079 654126129 580377379 41143202 9047011 998635490 601264261 189897588 613093423 91892544 952248353 433037416 81498245 390191267 570306414 300930736 15886114 165232800 776846185 701794519 165151408 673175682 276511216 291942556 277114941 246457530 445862373 348967201 639753492 938339770 387195491 918392220 850848115 590798768 669703853 612043159 779147065 621518385 778856638 796507269 443504464 655754070 495922682 133626405 891971565 825834353 711915168 889591921 487068417 448490842 16574715 553789673 693425140 55506031 396807056 475241811 211155679 831434273 379455976 130474693 141074459 837636240 92558489 579320569 964936164 252060402 302115816 197079819 300906488 270868856 635223792 101143107 219685849 760259718 645473335 774511407 396103111 882632874 592495743 711727513 143569032 228495169 111859942 414221974 802018198 879800067 529155790 815797657 145478246 164325428 147622511 115147863 882388247 137571639 459120181 230833557 977939294 598538353 212262210 441124606 448561565 138068634 82571773 527857878 680572530 590128251 237805043 676098130 765598236 733858879 190652470 975333436 612308993 283353904 708684972 418586359 692147250 530894022 452529707 562994708 740797286 863738144 323907157 104186801 702155072 42389263 112049279 358841953 569018470 266386333 493706393 717060601 752106497 304155196 989348566 161731774 554950692 156981181 834676660 474445512 97625786 539782831 303163882 596863914 474683655 586460046 712361815 237874866 314390255 219703314 332350459 46120594 88513148 141679210 73942857 773308823 957588741 858227799 368996700 368950069 564612052 451260158 553188848 372973917 821639191 254350483 326307346 298689170 365198605 919448379 950042868 179862543 266639213 263111285 27482831 513573533 357256492 229334743 16688691 971779397 311505828 887930287 648549587 582074378 533771662 667966018 454318969 865147543 338661743 893606846 737181450 153757417 746908038 828725443 724840103 440011406 597283861 940375492 580523323 826324952 97518946 261844723 735571520 364359718 749132696 108703203 616293929 817451104 787468535 260685488 74330775 199259584 811966225 130570185 303640817 965451188 170815896 164122479 166934942 680881529 78517720 37028392 623376421 324816405 148339041 889268374 876200435 795309098 237932816 782458073 237671803 550176964 876467591 483896948 744343631 322197912 773242973 9807485 846065300 835659360 994968766 295113768 914576673 70166580 570660692 214826108 377873792 761185851 637241527 868381835 416386401 827062015 302002457 652645948 744831814 506309236 763499649 637592719 69759339 437872062 880764667 270800441 278858543 54905459 783689856 117024764 682643569 911314615 364105971 54015068 881236427 13051263 723187176 995444395 736514663 266285973 573084649 306128458 324696636 504560239 518232905 397560983 78943509 358249235 389748862 727189652 898144604 404060465 887044288 759145613 319256540 74932189 61398949 435773423 115698277 724500519 265541487 534921974 194086663 753111928 716685746 756610383 756426074 276278241 26958025 224718591 213609276 71793629 329011076 916900767 2566969 802948581 725180158 334164938 663008983 161775090 236021000 108232760 301603391 903335197 756602612 531270990 134832942 490111126 196427129 648923166 782897551 179774363 32382114 871020627 419092383 206585389 475414298 763118734 832509759 164660580 227476009 206392779 178670946 914900799 954606666 921101402 270993200 175894284 610763420 927236266 141279386 360463115 862478389 320543305 562763371 114386785 956360815 17660721 771016489 192202763 546653635 871697320 181411286 83746170 873062060 260370175 443012478 260145850 388994237 824486905 407178300 778462987 322563539 181800380 901987435 345845029 183580241 219928424 538654562 833663039 689891945 594708857 277620591 943745038 360941172 226209697 63207492 816550353 65464096 807864485 219794059 991959225 436716525 928553885 740509097 777218362 321351294 931254429 716885972 661219373 850097924 661806710 772363072 165165500 117367129 536467183 347955112 91340038 239762357 684971415 941170400 206844346 483932357 126849925 316726092 188064317 968769745 894404471 361585734 564954058 989999361 465250989 408136032 733052730 513404899 13791361 643956173 109923357 520552133 384492701 107394249 49824902 945551171 618343242 43956958 69738415 99956022 109680550 234434308 395207825 93612262 295033280 152885133 129218191 210851583 60285078 229584940 114273927 614910650 135782499 969247126 87992754 762699106 733617612 487759377 627165311 584993389 475782505 320207632 692349599 117273058 584324260 92555756 960534764 55743343 45762375 303672433 996594379 170600015 606879858 145618295 414121284 701322559 353480028 445693785 701264253 222849476 972656086 870741928 618634150 625342936 901407590 148491424 748026462 608066264 753051911 42636826 862766586 139363057 469348240 99745775 664857296 690219972 883722692 268223246 753132581 157384692 411950113 238826592 706934053 724074050 275474697 136500160 316255956 385702691 42867510 933735379 413413495 6235959 373069858 953805894 91197777 59542463 774239039 665387471 764761215 918758996 245295648 37756245 149828155 806611326 810446351 702490710 623700178 522564566 626359857 556071907 162182580 409169154 322741959 266495928 727921424 755342198 185491182 790983985 697333190 315176645 299178766 481021145 998537629 824644562 161159493 967165509 268254358 266033044 109805289 907207674 139006482 589255756 714562066 914689048 783071712 72260527 512175794 290625327 108998539 997514104 985568272 272808013 424602902 954151203 935551101 237527347 296054480 615831336 171492380 27237520 442498231 911401146 995189059 50207456 890088649 277400495 569732631 339938970 629861247 77780338 787261676 429591803 449692107 424039190 869198919 846497452 134564369 630246871 784533577 581570319 475019459 301551306 963860535 432010952 782702382 526566601 571425306 921231565 689355590 268347814 76750991 357163967 323918980 798243430 660695769 274615150 320204108 126231501 896899319 329217593 343615840 411674995 11243331 792830342 695047804 894298486 805576240 401432907 861489951 508824330 924871110 228521860 789681134 253984724 748321158 258972650 757746644 334949228 430566848 846826715 482341006 975079410 772324491 653806052 749857932 516976425 25991225 522325338 710047831 465959283 27313181 61054537 756239763 700249725 424318991 779816108 179952713 255413767 293309380 660929788 361069893 576709130 966591889 150388321 613485047 618960178 991156617 632648817 369405162 929465533 925296424 399038801 351901129 342977909 130834472 157468652 716302993 208255033 501186194 100412304 546549303 259859495 563535985 718123393 13807612 438231209 971934524 774138303 440999171 443041550 705097869 936581302 245529002 275932328 300096222 501676538 166294729 961064946 181312996 558850139 768716742 155678016 680819098 654753548 545657288 668159076 114407098 814121264 789741931 712645907 309966059 998459590 713799368 965196531 294430751 746672811 851199989 72665045 823598456 560826466 183945661 848707953 176886802 849590535 196248448 13226858 25537913 900031821 182357565 580212332 304527963 351564164 342916684 773891758 890945349 487695546 408638728 639122119 83741680 62055962 22224974 368787420 938255834 692935037 851350259 526907121 41361380 439259849 321187016 474180997 39689417 274327714 524388081 774337352 156940089 691008591 757142097 154662112 2308789 402091658 138152838 497617208 525048114 772508453 766088629 531811101 299634067 9351848 593436883 426601690 872203095 866974552 774043969 888896279 269077033 403919113 19342844 22757557 696824929 839185840 146687400 538964935 906096128 637512859 734366030 405118052 894942429 155498796 987647324 112221202 9131818 697290606 761098317 563078601 587355724 664423742 355429214 104236995 968695258 496743094 877887281 159397296 181508318 847734485 502718279 785747744 202159722 682020058 109890457 817296532 897133780 134103432 128992398 768761052 25053006 44831070 577259455 502894215 187513046 929395576 175635743 467901427 690833304 161767601 196261788 105205400 115573826 715120223 387520399 924348349 658990596 540204727 956240539 353468278 652409808 976199683 476784358 301371189 192544404 897150294 731410090 639884016 633763782 350185944 886494207 579706251 230395889 231485253 575712562 114322657 666559677 52616943 514096833 420698518 608575607 409568993 258335447 613200581 351009980 509342638 460200978 639134785 9677222 643953816 507109022 679492592 643618683 893483178 20163086 354725188 470960258 808266780 274708780 611887687 392781204 896693362 503261587 294426554 306731674 288766309 27322624 875000342 872670716 513456213 839460847 614939306 796451083 323395633 826670663 371763215 346119010 751986751 222256535 9526523 457035199 17792368 476775040 596728497 626559483 652635454 403241102 170782490 29323691 879206956 544437066 803366399 875139487 112886606 325900737 270579647 668896360 197410669 760955008 373292363 498042051 142930215 436577743 758492664 242945557 184941220 462161883 326302625 278287781 626813100 702347284 549101768 171640895 109373400 436842453 250955543 320611710 196912109 656193302 524882200 420175090 471801849 697766382 658979891 387288577 862911372 406740937 996884025 317187249 343189406 9758048 948973047 522737657 531431614 997073813 56698056 99933109 145691540 883504822 49944800 583756996 530433884 286134125 158751514 478071062 962234339 464619699 726664226 88356481 381332822 105555371 820935365 78801698 467341076 341958362 549998802 309048941 780937372 303550446 925882311 279359029 729469189 328247352 34396646 926632236 91218807 271531099 196825942 836562283 612534056 733099984 645343105 890085033 319176833 695739383 380495152 896656240 642724808 678148460 447071298 558329560 361777537 533352260 245841962 389064238 632541575 818523486 315253655 924485108 654469498 563036999 271232625 564080399 930596706 616113657 595868910 279203334 892118847 842472100 451177657 571981710 549884029 198356796 552136227 684918565 402944896 613817367 823643775 114811375 159627126 283549448 569025651 323021994 772487388 712765931 39366005 353311874 611960709 437989216 588585963 233444182 8788541 243414585 19419226 69936796 240944666 38304805 279772872 234850985 544132525 691916476 666952004 457203637 573615543 263305464 824570661 362186677 106261435 134211450 294837822 28462645 132044939 807517898 639073734 165168393 883386096 132193757 928669930 868519428 30072772 381394289 212275333 639568362 7970077 482573874 653887510 621213520 246559322 483274260 71921865 647247153 693610486 607900922 992883626 618077167 26422498 415362203 314097811 132374421 386041555 163220768 911364693 349610640 841810852 746885869 883714880 636044295 824041858 792857986 413854846 900697502 626409208 373182481 207805409 531536261 160588937 390637150 713994136 602296167 748394835 885818289 8483265 921362541 403011455 878297551 909024785 638333612 576624731 156259480 367866735 388476858 364503668 908842637 549683044 966459893 486800608 794857942 63906294 641498390 681232925 63256671 646158400 228360636 207524945 898097445 779905887 271274224 919252021 284606541 705293180 888654016 747719548 661397415 934781170 940552799 672537146 857917081 313732703 50734809 762686827 710655156 256924857 821315340 682192208 700399535 116638162 103004520 775956225 750995873 28648944 202508380 208318859 941427358 571899030 387140129 503587885 408981384 230696714 417883600 323449383 790117214 26745030 224022451 406500158 411784600 627126788 808396441 715511885 156309325 932047212 532012952 157923514 919772856 584498079 770776084 878992455 754330918 25601982 562215913 629415393 784752049 462269273 603315995 430888390 295297724 966876332 968670164 252596225 926090201 383935885 293376454 525332728 939334232 634866919 512544539 287159761 722916999 726135729 468465843 711371250 464420540 877505278 440507559 251069035 489293082 81590130 512427923 988558258 911930317 571758204 684678005 156062459 859849957 833713470 14503895 11869864 86516515 926046613 298264816 715411257 986777172 229051948 868866220 580376695 476250118 226802700 205533308 398296825 973638321 903068665 641557990 226380177 990984310 859737807 596309780 664732807 398987899 42854184 743541538 743743589 773077729 41192688 190874346 514567686 309830934 806094685 35266646 568404262 822405580 491762279 246972107 301009584 332943769 204811480 387203975 276928863 713030016 829715000 52052009 772559699 10023116 97403041 88583254 421443417 532048770 836502150 307193535 374982651 790416806 513562744 842887919 981043770 22494141 546091383 138270934 518551491 987937814 212774905 938680963 244935415 212263370 434175493 620976616 820575789 591659016 781460323 426506689 794672702 407219383 42329160 856886657 658325110 857221810 141590664 419072025 824318094 804882776 924519202 644722372 49175087 673413591 669793929 792435618 80101870 660954194 651221191 277941616 613140971 570272559 416642678 364862831 702238193 650022246 778438692 278167003 210283198 18820688 888752599 996238917 891823598 663197690 503181249 237400627 249863913 98580024 473092776 467245266 860793848 33725769 304461498 635298004 73098127 26137089 175852494 653300169 406432202 582253939 792489459 574323848 73686778 176792003 805711899 514132619 293489183 477553229 555561938 516024316 512005308 939308585 654280088 18064919 50475454 710072080 670516754 791738234 304691972 257078193 362220946 316046815 891889652 117500498 999655043 592192371 606108201 868216691 246022159 406210889 798485900 514265342 495390506 6209149 99868184 534532380 702302587 781652434 287361201 647326935 464239533 937524550 228926622 626779728 965884943 143632393 820150838 475225837 893222238 820760189 829910980 746980335 135676748 691625397 883218302 543578887 50376585 407107604 800858813 760666852 77267789 479990905 392357883 188563997 542525207 195633335 654077329 931171432 561253650 6855393 154293251 263385676 713919851 166425726 298433242 9189502 68188451 202263745 597034606 676535178 743343817 585731932 722473383 604652079 765376961 252377944 106054838 977374197 416612489 174107691 529326584 399556789 947462985 574846708 325276514 278311719 609450689 878138164 661707428 201187842 451551283 73095014 859412903 288521070 992824888 552262567 70067350 889800619 555806567 429672858 330990875 635990104 692527071 78484421 513338833 199410468 326055664 230937011 199624889 710483705 122790660 317488313 449604505 516179446 377920564 785452145 150053136 140461154 6896016 457744446 507247403 989069643 588806975 433705649 875259487 309786113 476100960 974598631 48613147 934237437 973788897 944964027 981265980 849738982 855565349 734959640 712205804 391267193 991613262 148700766 711894435 507843972 117561735 525051997 410849419 222566516 67311100 591936580 381790276 637720347 877682099 572035240 209679758 461359908 414515770 879940542 465708924 89432958 717925397 551045783 412748460 780430935 803708000 703940217 469232563 267657446 710008589 745071316 610297988 460319917 342529245 353216465 711456474 628294679 346438653 290390596 298945854 794573605 128104955 539186370 783121223 676945662 198171419 978241088 60135962 843080531 3909981 498577250 180839625 723202150 482342383 759658489 734695950 242894197 506352320 690753121 112572405 315059868 878586962 146970532 594554031 597975774 80932948 578497730 422344709 171474707 23905603 255482356 37572880 94969860 697102593 931306685 693158126 388126069 399921520 499656891 995375621 67545943 139629598 881248931 700775861 7617138 961920531 674209117 832720169 954814823 56578193 106024326 209095883 49778446 839925829 781230429 316959049 320463854 280881432 915291068 472707657 989993835 243574742 947409987 663013626 353227294 275814680 407980943 574277295 238489409 871490436 824764822 34717419 84506391 732615120 272002526 182792376 794327523 10012619 604143081 295590848 96027675 261729317 352620752 520742074 801858769 86493274 656467775 429855377 879020696 702191557 175680593 790974809 615084516 233481104 265374524 856584100 585214030 319520193 187222906 708940516 151864502 364646429 690882833 589758479