10000 1033
346518590 124817747 844475925 27696591 231894892 850542587 706178289 766376660 290971224 275429832 497693437 706840330 433886821 32788094 807855621 16684592 132820610 736885201 718641799 773336194 315563802 19872284 449982234 277388162 33110978 667104928 420504209 628884541 7015634 765085517 634589415 667490068 148720323 109460480 930059435 147737830 631232563 954879899 697909574 716441271 302862957 220207207 180052237 84871028 2503788 456576309 431070026 57214141 982677598 94701900 117921219 972004795 687919314 80275921 293082642 94536213 574888326 698383075 201726110 360134270 270375056 316661785 848575831 954328709 595330398 199431700 306561862 631134874 492298403 982227684 738881844 124989615 181921218 20257020 602352777 254345242 359709856 949117683 999398090 31970871 833433080 979881841 495388413 536430424 495231707 666269533 376380863 218278816 750558218 919944706 393512475 998382987 173234785 158012398 47817192 619654872 816713723 294957588 137181194 68345275 493108776 335939739 791148130 288253064 843898225 984445825 873271747 408098853 9643708 415956106 303595455 327802596 513576027 913449988 815542131 514738112 752707789 503386209 637962182 974170547 111160151 58433369 230635491 288284050 999399002 110877255 988767379 120468448 333055319 792943837 675104644 547642153 533709053 79037672 235765074 137450780 599776669 963678327 618399027 47782102 132445188 585563677 10558605 247950850 912705140 473595229 646023388 487569706 883869463 638775507 875597864 576976701 426070659 993580645 445822250 123121683 736747687 866814564 306695519 180537150 407139236 695731642 465171329 192281279 921136640 696912203 329779993 241941420 601847586 167735058 557590966 453101583 401511782 544963092 133510704 87358876 405208206 81433104 839122687 845457151 405584781 249221859 324670364 677075263 608588244 836113849 134752166 570096896 209075045 469246160 849382634 857411369 568708044 569130174 887060628 496210401 578147893 508915001 34407432 771991237 328723478 665534122 286507274 934667549 591887012 31450237 250162657 458019586 524920455 879934226 179973996 606719468 366265479 880340153 967232226 89244890 309974480 283033803 135780444 828970054 57431000 788634354 597565856 585142401 488885592 388026011 28380910 538927705 208298035 632405466 214727785 232017990 621673557 731444516 555933077 257080823 988580551 975211588 784597952 687707632 487371735 353760341 755307266 477816913 854503708 38169870 765445529 444186793 319779125 543001293 728998815 716811069 368036432 737546511 248627585 539740722 850363864 443839990 947853837 716659546 497162948 832898825 919403827 781572703 324063781 925580052 508303870 56013842 344407761 96431422 6814248 903584023 658233523 785338430 72437591 26815573 232190594 319076129 915773416 382672956 54051103 384200985 390871847 273835246 187530658 937806619 979490697 710172390 637925783 640164720 176898139 761675012 646837443 755589225 704864065 369702967 64823155 248845860 624495266 522201438 511538022 721606626 285823169 441444743 349605065 942533253 408859530 694656516 501868714 503605844 809651950 47979037 223796917 570264856 892475862 819546020 113148043 467567843 127629427 776508063 190601552 669594300 161548562 411585054 754841981 816113130 328626763 587033791 262223518 644641702 358385569 737983014 198433303 813653273 816835203 782812779 588528156 121238858 279660373 269794154 999650923 223010048 919202485 183380826 691575650 261025148 293883099 558364322 34831419 550188389 522116717 397966849 772694508 908014006 326502829 61440906 871774770 122435926 778832385 539904803 886738895 692490475 541184383 233896079 610118881 495413333 310250518 742967783 677047260 772290375 37789912 591904678 176643237 390864875 457006717 373247693 890144893 967931506 566429379 215769669 748113792 168679378 704685103 276563212 100779922 752557824 76946832 930192963 604949837 134449500 902262966 347051503 652866612 760914259 213976518 672575737 246721017 563687831 675355413 867365367 892101842 187910891 203200913 84596535 769977432 855934262 487995359 723002828 782437153 720036023 199317026 524562016 872223893 833239330 607810688 258612495 363106132 128509117 704453288 700869852 683082928 208259797 219417729 658059286 2345040 147679783 50189296 853740609 960793231 72900581 520898016 539537785 439965294 707115050 346525805 796215726 875570484 642785780 670310700 494611083 897988332 219668447 198875250 844962994 642832483 748345080 904329661 170696082 554320521 959488202 249227010 118023645 256144127 686584814 361146078 807277528 832618277 768424186 752249857 383597458 670551833 735492439 580306984 462573418 927067521 615890284 226082139 235220869 832386668 646131853 765533010 269949253 46303613 146866424 807855733 370275060 295010108 688455995 970629093 76282059 977704176 541438306 355793850 827646159 112900855 802532538 455140190 851900302 601812044 91581607 767328929 238742040 842320321 884518012 524405774 911954886 782642107 280631820 203170931 529119297 105735652 48929227 348801160 960064963 992670774 120288930 896791920 706485081 500057446 336648406 315286151 296443091 955902012 465143415 171040759 273428074 199570117 71357153 149309196 766262193 199978545 911390055 113608778 710283223 501390775 672958857 620668072 307922618 526125427 716836173 10440296 815426881 795076800 309975811 113446300 190903437 3815980 583201799 778410820 31990455 172921567 923538042 391295979 477085579 577603312 171829431 719696865 861876990 224473639 502465411 92154067 335543672 301032204 29388374 791441782 662681101 343258865 411599791 181898415 760610240 902012477 461413812 468545074 393867211 410487191 743862761 861021940 109745761 798053007 944293316 502073671 402722411 609226884 207048059 284183939 724034033 251287107 609927866 207502569 444489724 514628704 54536302 915467527 604867282 68324967 554155681 953147152 887175547 764555519 385764647 786517947 583409828 680141317 490177213 179587724 780575982 963590311 168313224 342165207 741349990 771508601 682449746 748072258 584024606 933558244 356439755 747403027 650751756 338839232 497415666 20981040 897063761 233441346 128923198 660276036 887441303 204812580 88458658 531360921 55073332 706253056 594910477 203490238 422469677 482691411 929462304 590317258 4190485 974434892 624299596 165253431 520016396 718746361 695546164 104663999 817859028 104475076 55650878 203283302 856495895 653046098 818535797 803996133 702680211 583224788 58235461 828787200 605493749 383050378 649196456 612405767 826924633 316774423 271281384 64307315 944662225 490664291 928469715 979291637 393069670 528202700 369956109 486531585 815039035 452279955 261206858 674756200 51061219 407515562 243045945 918425615 816816382 172143039 889087628 339175118 628246273 33479194 264037845 874193247 305494852 761611326 112977390 96820525 150823813 559773268 511043515 618370551 822392760 559173743 431964387 101087001 386179640 540582957 383493313 216032733 108785631 754371502 562670920 153971873 867349830 30757373 383116267 839886251 851415507 338040185 502967298 655619913 287768002 452723849 486128144 30498388 876462911 576326890 176582013 207736812 313123663 156827642 766696948 443098776 120232762 164406123 964594748 181911692 675500242 389014018 116635931 102011632 907662432 169746198 618088325 302906428 923623064 492413588 857995708 358679507 960136052 571489750 723862202 101568519 147417591 74266168 547007647 85869380 168936601 44140794 67994144 376314566 43548911 236404025 430703239 469902554 545704010 322480066 451073902 880742086 997991608 191114996 861094140 183370496 283500394 98781064 135881108 614057027 892648899 111402462 282815375 75834277 204563226 939933543 182116975 72272634 102153438 317513019 29917963 404317574 413553284 638366910 885725437 636635889 972886077 27828373 972330379 142946369 176282425 939988518 40489019 408527309 145926780 375431696 797105270 15691652 183210213 43957235 189751443 83330376 496667570 597110631 825998064 314195956 167216000 903098 314503540 197462797 659261626 793184120 149062270 273127751 651157761 717994275 740518769 283070636 899715043 555445950 744331769 172626120 336902090 407509892 539327855 252081940 691266626 476887516 263900443 481192336 322324763 606275251 902638356 907439160 624204995 257473673 801144603 697217205 39199343 522245589 870908120 274704851 397153424 649348117 560084114 273022627 39890623 922290669 973665536 465990598 899349664 382108902 713472676 97095092 756695264 175777663 417094003 130652631 29263767 345107349 488728735 158312043 423895432 884340832 396361302 801668340 26828270 222941559 175648405 843662654 684102875 744668284 799027982 883346319 510818357 289373270 525944714 59056821 200747176 183315364 41147049 409449470 905031270 952064011 662380586 731332427 614659420 9465433 102719762 333038289 935933290 150461997 858596439 220296741 3348598 533056355 565692144 115623775 949436261 636174688 856589157 3349493 919931161 698478275 482113682 773433993 596977827 737032802 928864587 10373988 775987424 953469839 412278164 991649654 332624594 913729983 272430533 919717058 293820911 969071584 281868985 701292303 644353634 255182749 558876134 266271136 167928201 18127184 18912599 67055785 228289938 57628420 145983723 329493382 212705765 595607377 535820324 897784491 934901782 50678264 751510931 249776148 761530354 413112066 427514987 605362048 882602956 17909862 743149249 779916473 850938197 828783848 579501717 839999941 3848203 358030678 775379099 309510921 297042012 720147636 403165020 886629053 18857232 745360896 957859386 185971461 374661045 976699920 375048935 935448320 150417063 67030827 420001381 97090950 790277926 974262811 794655440 748545618 827278286 789437406 747818473 714732711 178178195 110424522 208186709 846360286 299600668 704886784 726569258 230536517 776076813 896498017 621316724 257701514 334631806 80187429 563282565 173913932 631071661 342966107 87572111 401770287 384757940 510717416 794451431 632129362 757392897 281284407 164574150 440479638 482110435 106327405 444751072 474045473 954749060 993410852 430189120 103727183 566652273 264846507 565444378 705788402 813219568 420634346 995415656 521488944 65861040 482520641 790177285 901338023 312739720 651072717 759544366 494173659 253913181 418695551 133845858 913348651 471992178 440345344 265314908 469850811 329007777 663916796 79397699 21547449 318665485 2429016 680237162 854722306 67752213 366989237 94233116 144587796 87629619 453448587 591792054 526203689 648738051 859287317 197059670 545040676 364819033 827720114 43155405 153185234 768206990 634643270 286622069 149579634 125618472 241445065 132766951 44557116 788903331 942427440 219624386 971392995 62711395 560702041 833185359 89478161 364488301 927483285 984291475 27249516 344263727 525153208 78545619 506720278 341404076 15269148 720528358 412277307 186370490 406306197 713972526 363772457 277412897 983895981 942992809 561295312 703543989 531322901 189193848 777732859 441084276 289259956 752939554 925361676 685652708 332479488 181133719 999650353 995156046 423622690 608871822 746873226 532247842 593620491 704014333 609891435 231084109 193761412 384085523 549905982 391107651 352488502 157904315 948822955 974827198 906281008 508218963 63616054 943391739 981545365 326477292 210547564 565523176 562949281 656292536 202845738 960458480 508959529 373174555 211446194 129906523 912784925 196408055 532684958 190781344 769508789 615993924 132872638 992663794 81717759 277102599 696996804 497410282 383870565 676433884 866046630 11974450 123430584 960637061 894212369 593627318 628191052 338975771 623701322 468968456 132327214 61922581 866941661 919024457 803388510 676128453 555245874 20044957 782454728 577333372 303638911 745977065 760558893 648702540 25296964 668899976 639715631 529724454 847375640 304098858 175845839 723667199 321307413 510527308 763618914 256810051 684757091 795738300 983982128 980084297 195913387 270081294 521144203 451306282 603198460 414575447 637941377 193798430 537996513 595514507 100195171 163789971 341024829 515644578 547320735 274046062 991648287 923148593 84545538 82510166 675601450 308134372 846652863 603261028 783266671 653896475 454987793 286535665 422507601 56073477 753649942 256717256 512441816 320937205 44423810 595428036 780290723 838640086 409961530 911750919 309617101 482833676 229206439 329370193 161964959 442012894 359981990 550229897 663304269 42227895 611690695 817667069 252698211 417180025 498192361 100765653 224747811 896837081 452891121 253890480 606164910 632397686 48428775 596669232 274543105 414369403 616023019 91781103 279718642 901769573 494372739 764423305 70417652 459876769 186094749 992792141 916404747 358536379 102774342 318070922 145538146 974608490 36967836 49343924 415737768 897871643 531665503 825255434 932684667 85783448 522603401 229389622 474801420 845741618 961067408 622556852 242776385 921674937 683784670 566559262 361010549 651775160 299125122 777993322 469039855 511437828 440092981 704578014 33518033 165935152 238695311 697045125 324718054 335478188 279234570 920302551 164909099 849550655 945049730 612617580 547075054 42710313 660619688 38680548 632870415 801807177 945507400 319448930 973110499 698072390 253829123 415449475 861042266 884003813 121223934 811165091 448870006 429779290 640591223 365360186 946916524 572867426 828118131 665543420 151194266 290388453 963197098 655521029 536398578 182808672 714750560 966545597 403479545 429726429 460895034 906450290 10484733 730348075 153196179 893541026 32811604 521588559 228795294 745379509 499246387 20201540 295389363 920679654 647714813 625394644 935177958 892512429 716990202 12470773 182234571 759123280 269185565 214876473 145015307 621020859 224482419 147291476 747235076 526493130 890610344 775320306 740079063 197889325 661527130 641672734 967252950 197484203 435649382 975486452 949788514 222015021 928563075 691365177 343789937 667763434 206244846 287632797 103758561 498474244 988292993 162941616 531047182 664756495 237726591 724736673 589401401 269245227 445784186 131852516 774568253 511855958 145998730 118928363 899461807 886922648 790156286 616392192 742024571 135234184 918630562 97679919 319168640 669992664 723459653 364953766 58120032 804076200 358108430 723210372 539617095 705853473 931792788 880427854 781715668 684454231 109733298 318885318 767839264 190934111 126573822 371807615 818380313 532939575 812457787 726220670 915131418 700381988 997861620 618309125 59731814 507988968 23280997 241856611 676839280 803248837 126354366 177633280 759747478 658889781 231361070 772646215 25743715 189979149 51094530 408297915 421771622 918080321 873416254 599919485 992005428 571922728 752158797 64302082 86473204 769919429 991470412 204822296 72763810 217087536 192487739 868043364 794661045 539334910 219112971 513604448 444368275 455990655 432872442 672128562 235874203 556513448 692512818 606638501 183096954 151931822 522821010 597805727 787584674 517705927 449923575 644041809 918106347 170191881 581848445 91903846 130497128 542755275 819698468 193826868 858822913 948042381 621419586 42430888 783409882 3641523 743715943 235514501 503113608 957793494 561967338 476183462 390446423 235244367 694210698 149004311 256460059 916550971 535788522 297037728 466732643 598827168 121084422 243780706 515739920 421833925 363630169 132398665 338036166 561361742 95835713 25958420 862210558 926050302 728680833 118215305 562057088 551616848 830903188 174454235 528021936 118136278 275319189 927800558 751684047 596749912 383762064 239139906 924919929 113873867 325810576 286974757 275438981 39257759 317620245 308278630 360464890 337766562 464094798 289850161 34926479 567047390 56156963 146451346 386145275 288136823 296186974 6564940 621923053 627449715 620578444 899270203 81271773 898107167 227250968 932825045 628424226 21634788 897551579 527372150 34890381 647389751 432225964 890535076 752446765 616013306 363461530 329116949 749284726 148496077 188860348 31411221 134476983 698963334 701284466 732550670 217395232 866972374 39723386 913860573 661532959 139387172 728011010 661626719 790476460 812601728 21224763 559044259 643902789 761016697 746637306 676428255 584651564 628264578 753539247 952457461 479702226 776343076 761298770 772418369 861083971 952689789 815901 260608850 931703117 325675084 860324932 165969661 769542074 107698809 237116131 164172099 391408978 340503402 695419990 598781919 435406976 710498462 752109517 739679775 859934926 745498221 607229927 153376565 693495984 271227270 110937807 201237756 607035425 399478341 88805615 752687438 21647065 475847715 737758900 964194337 848371881 826441341 694208080 190458146 643052223 574836645 684979017 613159665 961822458 194852602 290496127 172645755 691698280 353314923 443830936 495418028 426604509 287514210 723780987 889850989 610552599 369046158 828070521 715886571 737142929 199423819 830616310 310934156 94276650 393946807 573571852 843900461 178038517 151703934 369076071 761446862 668123462 921520238 31933964 262010315 344947 612206925 961030623 293749361 446163815 171892219 50251655 317502532 52862066 725623881 952357325 829249933 973272350 426843661 345932552 819846654 180976979 63770105 431801776 947820008 31072983 314709716 564200049 552002598 275501115 700433517 474051860 787735064 277047667 827949042 412071664 165877940 762078830 879559517 381549008 67737402 185738930 345666074 911522907 757525221 704649026 543860174 108019416 861105981 277190573 824241765 482663308 416812862 605470197 531743111 362207224 598710255 848058743 894050326 369766947 25016824 581449352 822980641 408685798 789947373 939702784 341014268 196209213 129693354 702108079 276044474 803216113 124296267 733235306 152821784 119387680 206044214 79123534 336792603 898369395 703815263 566230173 829484896 738811269 59613475 884985693 47915351 246956328 484372926 477289131 404118777 947607604 110785914 408651698 551748746 480426066 829587865 457103739 104721719 548473175 881399395 848029824 908468432 406354296 504589197 354084869 583009599 626974935 570817353 107218287 898876874 949192802 668187699 188331160 181563868 362663216 281255328 743779823 868464126 581810081 899627395 214894021 945826902 691320042 826552459 871769190 51292191 98171613 776869893 506760337 543959511 283439989 577665197 172229708 490602778 571310818 711349437 981732640 715453241 930614494 129685727 919903436 346622425 898317631 613013722 809845470 606385245 720345369 345404808 882586367 681764130 34074661 374758130 169195156 695645131 832953215 77319765 160079343 312568982 601714868 216156957 171784266 942207014 541544894 83032192 940094851 297765637 610037007 942124523 976346719 702705875 412297385 809960291 430303584 525231905 490599657 617419754 496258629 690716306 136410363 343235326 496130702 856614215 806693090 367331348 61303005 747019689 341209273 976510265 94171097 747295177 14549253 920330122 844986693 434321443 343799911 132021038 302706703 27320168 207983757 964585730 298781485 637254177 981319404 912742861 744007095 32505920 496175915 216108294 210469792 289525860 18593476 215307532 954992492 732909860 708610247 493731885 118366183 11627202 180684492 112722887 216401002 180799114 205154274 182485550 521520779 779634429 399996021 960742374 829830809 681755422 953129178 519777226 538455242 880113096 139482148 887616394 303049948 586966731 588947632 170276015 272405403 360185825 802404450 714988353 283349384 917669167 570873032 980638376 299882261 586725073 66473257 703849360 247765667 17419758 959062821 89633970 878691962 89178880 333656576 520363887 740548562 106484889 832996291 726786291 900877229 537908383 449234859 407376901 535493401 748464809 350321869 465647462 195922478 682607762 403001275 669690812 566396375 563319422 598168256 747709516 916507615 753167811 647829653 801230287 351412364 900888054 665452073 719215766 411455494 138152367 148951707 610327823 775132215 473940504 158845654 139140295 793906999 510153092 857531701 899699756 738247276 908549166 623600742 385816021 57004225 225706158 933440879 287466637 71145598 767011475 794444301 256720855 138300873 333918523 32771124 172166473 930094459 791534561 186063301 564221682 537278219 90200751 113475605 45506260 636258859 402084975 868303484 660043549 228030375 813403206 299841502 939603355 621656969 266254321 610452292 428668820 806739291 230305240 825741086 888616260 10417987 507793359 828998240 233100959 614814497 603483353 297160967 733346834 6422498 936247542 459627617 766561421 586390593 685907529 372738353 522317985 745890172 638761073 77217152 487463503 167366528 173815749 866699674 424212317 921687788 626032760 450017185 20071405 556664949 322843068 689276928 340016461 414398755 18496602 779981034 306365935 525234527 931284725 844245985 647846670 673240561 621953829 741203977 669744130 58824098 52972300 753023022 933942166 469293974 230569031 334758411 67781998 431090035 477704249 173790156 966788420 2313722 282894620 669384284 23435524 830425093 908319601 930453635 514084328 531616181 848409592 503350408 709252397 860428450 654125192 375678860 247360158 318420449 523753452 872383219 569381874 167857759 677526502 785604379 703591196 872970417 175442401 771096648 852589377 476712447 362773794 919604685 727432771 136399741 817207276 435050219 311408534 961526018 256861188 113272051 985160359 764526687 349681579 405853994 599535652 37820953 759691963 52408063 450936796 430444102 253055987 858260280 546266206 781279537 571076567 596721568 791854602 907596 730248832 384918527 250254627 364077977 593751030 54585096 575808984 175301747 340129709 843872916 525653160 552053454 545435741 124563932 645948909 54656864 22218244 710316840 630551489 370645804 75179165 956272481 408426192 741092213 146328702 583305665 888637542 776802017 556109740 792154426 674876579 170799224 194838393 548641564 821901589 819488637 727353049 355002908 691544735 91819447 684723371 183290775 36023184 598942614 810456516 897308581 203612231 629907104 391748679 666900063 390917896 519216056 971510852 59847355 361205514 800923172 320058235 605913088 396242107 710312115 805595548 870438706 326684713 258286512 624875942 745321950 457418453 112101620 451851381 780534891 38733167 102492154 580255664 312856846 558536520 296477594 149409344 665046587 667641904 779196426 853316282 408760235 276628588 750019786 896141692 736325819 399253088 47867732 695216615 621665540 757135521 799299381 122361439 563507304 395880234 499731431 324735530 496549542 832049376 38079977 79964450 832996335 489431573 218539643 517800877 128275312 640284637 593887840 278501894 764532136 368066044 267943728 474611582 100981036 835507513 151648133 811558221 218296511 931445682 113193120 676719624 547463513 739910564 448291672 645235116 986649929 372708047 976012971 885792053 604886337 40268030 300000083 925126985 368049041 843748043 510939849 895449019 369533140 837512980 955515326 710732126 216189883 209126703 759524271 979741226 510315223 177841626 638479898 226730610 304760181 722306425 974146319 639741590 748216287 464270132 358771564 688886986 532463376 625350361 113998519 784245872 738792985 482305325 896197646 283973387 668911177 885827940 738020628 586666589 120763297 471691351 670983642 856246034 296450653 553413376 785546956 636053118 512485666 365094763 718928055 519555765 276937475 586130664 904125174 234897907 269976603 752393231 200560905 175882813 256521267 852388636 886611862 267437162 380924997 932322899 34068181 306672305 209962980 677042022 699867511 393956995 51361406 802578933 103668772 928952773 274523171 379731747 616358175 681623575 466318 156814628 832162025 83081814 121236841 414077767 227192125 957142385 881024330 283415995 969812809 523693711 312185768 376893006 577096883 446407822 771605715 875052743 735404383 753014726 302153880 671586652 22235231 467453931 16046059 883230801 115868320 50207791 551702778 283644408 954451484 611462567 952882896 811856672 486707562 383191606 494045630 818064309 35592334 361383421 27286645 946785165 128200081 630609309 101937703 304345097 550699117 150910498 436311132 618339996 15173431 398475065 589937565 525998292 776772414 823617539 580067522 67877560 568992 730848709 646155170 642423703 968661216 736313043 891877378 241025255 904458125 573364964 962578588 227887828 796623651 990723016 362464862 892159096 985648013 751514495 518517460 743738649 521745205 972992464 198337757 377582917 536114203 636150725 282282461 825636613 271473169 406038016 860305529 407624573 955920260 695666570 677666079 571034994 388699825 576984047 304568869 219470369 855502140 725536313 690917958 958404683 177441942 590491063 484061566 229502169 576252728 140632103 519178670 392554944 200047480 680327821 316893629 498241680 562852554 909311681 678791056 630150751 317726209 563368937 62357114 384043086 461434522 271310372 792488383 351910213 351024583 410410757 195681328 250647290 895071138 988598870 35652055 730043153 219548403 210141211 15181173 943065867 685915541 716150410 959643904 593112076 985639381 765350857 548912197 485232548 829899820 716468269 827990841 606781103 207121203 131388838 518383151 499683578 284520543 444392844 773527427 314461303 771191907 567862112 278577710 510812750 868409954 80485619 389252557 590304547 139041196 869769375 921453197 435991102 252037615 666564183 838166776 676734395 737344853 156124864 780423573 111062533 697503370 777823292 858497781 367912050 181606982 488869152 986009997 169392568 615556486 284571141 555508110 6591677 942518969 800343137 942735599 66501004 964198478 53908599 908357180 810371241 554215653 234437953 993900802 805405548 71194432 329184045 34788820 93026552 761705573 846239247 805663395 866382814 367022100 730824672 67603008 981522734 634156692 869432294 140703471 638787028 511791011 829758846 777398054 491035968 568708782 75924590 528741039 804299818 634480746 332914755 79679200 105797818 355503398 250342626 844204915 132828164 774660655 253437817 883694481 802474502 756006355 778452829 470112680 209132257 324366373 411112125 533736504 395493202 396759021 39501202 957418923 409944067 965312989 811340283 659917641 983424605 623635819 130937323 911838731 495835715 557012892 926518361 485864106 199684267 871338190 386755806 855258522 567473044 383614753 824285323 972722125 855845020 307523307 219045143 639391325 571148865 851347710 785113937 585964008 284206465 593662946 840904073 98451426 320116459 318939453 686147783 417397278 476065045 371472586 956911502 306608495 27464503 21195121 879926601 323336377 869387651 858579831 221862404 718850901 895777887 105793561 309955821 104838084 636505518 508149538 138026587 596215824 582400143 60593031 547242525 816372998 429639657 128401652 577794963 878536577 217154137 839028978 950824304 696311198 878874745 685559193 202770851 552766197 495005089 442517066 149353933 678794843 251627864 873224350 438577239 210391341 333793377 721910674 861926050 196760563 353258979 895802161 693972015 587214034 77306819 115754892 340498436 2220464 577029337 466102653 798590356 645022277 9789984 968593689 52671450 363722847 295142451 51344721 22622194 601413870 471005872 167702329 213413384 979084651 926378188 387968228 883726048 544947649 573442223 262620957 215526952 905867100 417762698 72907612 264954910 243235912 336341019 40669247 464861764 940230945 614649618 352681521 410712804 313638064 425020676 834013132 31044245 883913518 517561767 632114613 34382221 861708530 948434951 946556851 458043693 430966312 456602863 525900618 288875117 185221261 186442879 893957189 26260457 634243341 615065193 933942406 800177361 377172940 310351472 975136610 183919577 562579686 10320125 730749652 982558585 633357543 323985064 44806269 209050946 278055216 377629409 934107939 767755648 569183233 127800772 94326240 621449730 639318999 245160437 382622679 292312971 820164256 352570041 219915799 984664915 994644299 460700399 797009476 918297129 69129928 321277506 217410554 117860341 850141805 414680384 235399056 59974953 982478710 427794827 390661575 998492124 7013912 236899181 690781956 916352430 391468728 672934516 599206935 768918147 503776929 134464914 389969165 553135632 826611925 360791547 774768037 958830308 966681401 213846101 465334063 23084623 317741600 171384876 770181149 641117111 415880892 881089179 50844731 537098477 761032878 218207375 493769720 688714003 633141061 923274447 898412530 83757182 215931108 378235169 27821345 425759047 86545824 337077316 430512696 569626709 184243421 474668880 592452614 391447103 764522033 683019019 648461888 417174622 354229716 537447558 424802986 3833081 108529823 242579651 862995986 411116190 809980944 535285560 473048843 980047133 232689386 362051934 202017067 146197691 969170588 93118444 84091875 403278738 993063963 374461689 68136835 552341776 941583794 41891387 844308978 810724297 217448245 233622279 822418230 972437101 679436339 268038201 13576160 957096302 583425827 822040263 46243517 544610557 529135227 185572185 290190717 162507436 448050411 583079951 306924929 214928347 309192234 682035800 402673256 481090361 246454388 607929802 687788295 906577452 164834425 864031851 82210038 474833112 46156817 446088995 5842206 525499836 201971654 452167931 688958878 29342919 53984470 405248816 872451158 175678344 636696723 462363739 913121351 620965227 23999381 67589649 681118871 796509439 986118838 935918557 376777767 899960057 425961591 756806824 813292092 227987766 379167077 888651417 832453325 470331788 602356275 525117638 403716756 952693954 145964137 891826400 959612881 158859010 253489137 724640043 220544196 459969713 82210123 141859363 626895244 949753851 381771646 98059155 126537424 927641887 666323960 941966942 703758238 481302072 125144931 802979206 823463190 65524005 804545788 692796425 949162434 290324841 114472501 583111575 845661781 80227760 74485476 151289506 882505895 352821491 580129300 711406261 946892144 132627375 180054065 205893184 772032668 189109588 608869957 440266993 670553039 419683417 393756261 593129011 179449576 782538782 996842032 92595325 831117844 479843788 291287225 281106532 505930403 19026880 702724500 302376706 227868271 691314611 300598993 10183757 908233912 866529984 407300692 298852387 405073632 911484358 981861835 726971879 147393282 226132733 109743229 104879899 636484656 296474463 823171520 873586358 458884120 430546164 396072736 523005551 799711077 626273808 606470926 544163380 52554560 36229563 213178135 109793479 808107823 930062548 50355224 107349477 508930468 895782441 805431725 232543626 983920291 738445424 165689493 867361100 992271287 261593525 701241367 646531629 118677267 730698121 952313185 193217262 845799460 305345813 680742038 461087266 880622676 11663621 892245582 868410807 429404747 440429389 321154315 549908512 787843746 616932988 476462945 433323186 928621824 743246121 457866455 907709704 843866778 623082031 738119312 142808219 400237806 988950873 293726725 62786183 181106610 374182198 984096019 814651809 452705872 215465047 472827063 757279272 307049167 254751326 375431625 697579906 243553175 11825134 162591862 239004760 470907866 704729968 946255225 656014494 816258166 503760696 356425011 921072392 293377154 765056412 596985762 513468681 777433918 192898857 618413841 279998259 395110716 88347652 327336880 620189878 214357265 717392423 422367972 82942776 308169954 270408696 463605181 720078978 437183510 496156995 182767079 36530464 931405744 889298137 763485523 915845876 207245871 145576808 394561090 710475230 542356889 733542014 39036688 87608258 170595210 575267661 253091550 473146926 603149053 50297479 816883339 500592097 169948113 237059050 563671816 33838872 109598045 213272506 765109625 13317659 85055558 996868341 786731246 662475489 530886626 577824110 488424713 752741296 666658910 454026914 572365169 542716216 903141250 288832649 469785251 761254272 49957519 413804911 164110559 854852180 534584375 974065559 620364253 133296431 860735646 64023957 65568759 928800026 230527712 55549847 301518187 991652387 843265885 258477118 183184841 889804356 506618698 819770704 522083445 23876566 575261565 643970523 164369858 316854012 828223610 639536457 584029379 425404889 641475038 442819607 246053268 687157202 80127647 616610928 672050933 724919130 754699890 898581713 657890017 682224722 702239325 508454977 41359205 358048331 179736897 783293474 575564628 121815166 656998010 832142832 208491648 568395844 649667298 898130743 13718918 686247432 119167231 850462017 42828894 808839329 853852798 202502597 672520339 501218586 998273162 882679102 858942754 59561489 494403918 754059754 883501601 369898260 92498456 986328804 861052258 932247177 664167471 594592042 546693511 558830269 631223063 51920776 483342966 87242451 206819060 831585645 282638950 647205251 384088527 530129928 832093545 186725433 399971752 800041900 74162044 210057544 574105539 771716008 406230272 572307322 416222743 72573243 738986251 523576043 301759568 916513899 457388877 566720393 850083960 742037360 482611252 806098223 738441662 40377041 368383988 812478182 380349207 955013290 704901250 303219995 555126124 740190983 159481753 233021074 376645476 958131582 722005060 247393762 889247898 957001291 933955967 424644759 821789320 136962164 470160065 754597818 434186049 973964155 510481861 211276691 569827524 855661406 268730549 397045856 675068580 568104968 717907433 584560662 256198910 933494654 339851854 338476634 612616011 450097914 666181996 933691249 950251129 168529636 193010816 212313626 881203305 472577218 531221027 857491278 868057502 54892331 777559065 189200328 969321121 122535894 925714113 932102816 169275609 482315955 579964013 565735634 28563376 959700218 688284113 789571976 541505515 105444496 142781458 344678255 666406114 188179049 367089416 27476396 94591618 440168541 2991509 935494962 606319754 420488759 790110115 658950919 473994455 234027654 363918563 332449773 756030373 358827594 6326702 506859300 806249456 874041496 146313041 32921429 293419794 638076991 613837330 421489361 805989805 2116028 147080337 67936937 660291590 405433674 408475813 157857277 256384141 269101737 393741544 412061513 384638040 991007732 835705825 594203347 536990626 24774230 841654655 935636241 166014415 739965047 837595831 507536427 310901798 629209562 716628904 662326478 498942720 229025963 598744759 314316324 642557782 659825717 640137122 536715480 933368909 608069503 680575351 978323021 576115895 488226423 270451684 170181052 833923491 155990438 291337796 25338291 464070657 117853337 386209759 776064371 517235033 144746997 968518691 237228189 43388218 445795733 523554737 595536849 204927085 338609123 127090197 170868611 500118774 852137285 536411978 591584812 698385965 107977347 283355740 327574151 14195427 152872112 423491710 914446947 297025457 57407064 947138588 852509794 449581750 909394519 802439257 721443282 971417998 381310106 70144683 19207830 669279813 865741074 821278009 947705357 8990929 560745831 84614733 39576873 626918051 60187766 554147823 307911432 97121163 915128247 968498582 306226980 283480862 497239192 875866760 902578003 704573800 448165020 879396635 423898620 599744528 401644002 884072348 696813548 700258259 741649157 460596623 518220597 229411155 684831467 935936170 485160345 800689838 202232749 528239653 206180157 244681597 396343267 196920688 289462802 358670474 333402314 412672090 659462926 812328604 346730309 138630191 575436362 549591002 395298697 273500946 372425634 242508495 317436714 98239003 443858502 152547558 582973764 968466359 135102739 91194375 265778330 118409936 539250135 353277945 972123127 944185588 440069753 576459851 465055338 227009873 401111096 921914635 657968968 444900663 744745092 667282694 570155013 473051593 330677538 5098798 278720357 51025098 609185891 548702661 24011466 80910705 625024213 839873886 458442907 831906913 626776248 631830381 587247259 29893198 459952287 586858848 532786931 747226835 936166251 57015604 286371612 20759894 447626815 5346495 448339704 2010848 674847249 211443008 672447014 561513173 42304461 14838197 169927843 268989975 399996658 785468367 82591595 409436223 215523557 865221211 737185854 493538250 257165319 525963942 541333166 400698561 520695725 881219336 325093738 278689541 960464248 263537715 93164260 939052492 374048871 142396650 569471942 6347217 165101639 690480283 953370954 116120540 273622001 533602637 539958946 259829081 691457152 326237582 684939824 740058403 137745554 896646930 744068076 226802734 203120506 881866838 786341655 780690093 188793435 101091383 399608211 742954520 346870748 81839228 659528092 205949102 178874925 875653525 436101730 285495653 984655650 298078768 848076327 319649204 478352870 986868758 238635429 314516084 774361172 294116022 969039801 947413619 385239069 223826732 312058625 849499369 180649092 294577217 725053868 176099653 578003888 26181003 837091458 403656747 261370889 644471046 140945275 106910585 132322438 387632153 164226555 665345639 650263333 861820469 178405990 28908775 976919978 57552688 652176032 748921308 40855714 217817067 861500385 507030391 508766590 15728185 416242080 509422157 714177626 571865461 462341006 949688388 283098140 551861805 211991258 766005334 560189611 659859706 672140301 747676279 355992786 15322220 503034012 172727948 611171069 949837138 690068612 435288606 964488155 290220376 651256702 465265157 110784457 307785816 554244706 50203899 704880005 895868446 313291651 859359686 886317833 667936463 684037668 69995027 24357517 473370727 342500836 247027993 214818094 163271254 675066899 756892953 707361738 50018718 128730550 869333304 660490338 745815822 411035888 346633732 224923674 624405684 638607804 443109136 816626514 773815480 576394313 809784908 763000754 562167236 806306967 341938787 555780435 413848162 33274594 642711725 205508798 83072195 595907930 885151566 395314907 255014758 195324110 990474215 232114620 278597187 518856741 601702982 223397702 401873740 545298439 273799002 796447401 688704606 321193864 636002742 568756790 679238023 115366143 161765736 345293004 585198869 265040535 119946223 147303547 182461444 67570627 536699444 443380154 114014865 800750980 651917534 442181008 487476226 528999333 69747827 28378509 499939853 837422641 339284064 905918490 947376723 689354439 325856148 457084231 287421528 416390399 98704598 834547246 241644629 375095850 81659886 595918218 694222940 498561448 816102190 503399503 686516149 810172791 407655727 746391103 324454634 156307444 316213211 378921250 815873792 457128524 781099051 119732339 912559005 817887813 185272901 97423727 361348116 744218532 854010843 112816579 434735991 608335661 665897545 106518153 510553805 494765803 602574058 828555819 777828351 137354368 468630984 198628281 859725406 292599645 693045799 447299151 237466493 905892608 837929747 662332630 322528554 718834188 162107483 164244065 331525856 949634040 771926274 823850256 734001025 570445584 806119988 6981548 656686625 790997285 243388955 681776556 2751763 49306935 53414129 556200287 762142457 397650392 960604193 616719945 660200802 67655318 258476186 610064274 785251028 889332831 17668133 486361215 344095277 338773177 713024254 685820918 701049287 935210580 873817033 709560282 681287471 944922373 968113986 537584732 92664376 114568014 263079848 505192914 303550478 342394965 730686510 142335769 487672539 823955767 190076505 974609522 911065012 543836173 107265265 365047777 129672605 105461500 979422920 600681522 852076069 818742750 671054490 84853140 827906635 56321356 70905866 235417277 941476676 698905662 430989011 866256538 45879011 779513789 740369815 496547801 584091318 142459530 158499176 279984179 432018273 530761548 818146772 636377625 207647180 828480905 865576963 362649352 565894268 800096478 710633928 84379753 36133451 875983266 768235975 475140344 928394351 993702392 606997941 303230142 205553829 638339946 649809297 713824313 322064226 45499320 824565600 358750638 176641763 477158190 146721290 595894137 365276702 418097235 395851728 706748764 479466518 143250654 987988988 466564048 488404782 478062352 414798720 181691459 202255940 757798843 963166178 299436378 857725046 202649372 342200571 701648456 98405861 306662550 89966136 287893479 799096402 370369931 20680445 714198370 728756408 283935040 720884485 522233407 558144088 417822713 985104874 363364627 239064744 283809202 515805026 21525413 378336402 877693140 260006067 468711720 469705884 97602597 961653419 504235971 182987702 891177548 992263025 886396206 556268453 443525912 464438137 977276569 103710277 134935585 427064204 772301427 620368103 66202979 270361000 951111509 531907624 991034346 638194368 538169856 66834030 484095394 114374153 113085869 229780455 14193124 115658785 573990883 235255781 510571231 274703347 66174193 461891136 390995658 576677626 727314337 112039616 985739965 513800300 690516684 168883221 614176306 849564808 126984938 799732799 893138913 465127894 542757044 97833172 789134447 374911866 472667616 713520964 76580204 671014198 199015751 858023102 108119750 640121376 962275459 999258655 852516578 238439548 515917811 16736209 939780475 691066009 152671175 833512276 942676628 292587087 881881663 892027207 939171748 578900189 867859443 399918810 33175794 88818945 842790019 329929815 325007885 320617981 359171996 865291780 901046990 203451269 311384946 541182990 68985458 363816877 982988476 777037989 919059781 74698760 53201887 533708944 863422213 640524766 476511838 191168805 538626542 967191216 751134276 342780514 819859653 192898469 904809526 813314151 598566849 722805070 235728975 9225667 489529888 580201280 645068601 589890322 830317300 345675930 491878848 442716352 206148304 366845803 380259686 398259616 175008230 105611018 938918732 546162452 249380874 580616491 501554488 23199295 864881119 290116966 205146424 377696163 330990134 426884119 572058957 173780994 326371975 649332053 75228616 194913183 106673725 464724684 218440555 334544432 121706785 57550440 910109554 359018988 465719545 234010499 614405124 803526995 182935662 457534265 741942701 827654758 7038033 844223572 925532135 558605415 461911588 641682059 421158894 864108178 48014568 356239083 1886132 198214529 453126703 975376833 505174359 597458104 988958600 653451356 626704847 674382560 280758252 299531068 618210248 454315215 40285968 902281898 696547555 451342035 620466973 902666492 507531190 306499021 415321446 287884920 552469696 181307154 664916856 244547428 216895620 575221878 239068697 861058447 799308484 346159712 112539013 915514785 201734395 449536475 736437699 181812615 29052868 52624329 697246600 597361153 86159042 148644926 564820090 535701246 559365347 38967057 774579132 885159746 499193880 269033444 250533562 689554636 510718891 613332271 624281763 762516764 867976629 15404907 535569992 85803690 196947583 829456120 492065676 275905668 977099089 86682296 876623291 182974909 520624861 381802500 147761169 49829905 165375208 731240076 791066889 664457317 145594766 914359299 932313580 163301981 115991649 180098875 359854961 431520937 282705839 141834520 996042779 806572845 715714473 209547305 323718583 122673340 27316471 127107488 268794283 308961326 741023224 985894901 263104679 296300506 197343807 546456290 837688625 313258489 818471680 332183316 1027403 577594083 15229923 43494110 441871714 289706921 930496612 530068328 148045060 426213129 845613754 906707576 678355551 270735163 595915346 315662165 526990487 509381126 557331715 537626385 826197207 521018716 598630893 562260772 521706914 962051813 113584124 574899420 829725837 752160694 348684690 839600033 810901384 998653044 683661945 880504131 823732893 400637045 514273132 837109425 779228067 803164708 767651112 291270877 287868210 451259402 549500501 865496055 144690831 134304042 34848888 914444909 154432344 225185508 520092015 523448065 962460787 339801054 499643425 282662819 23918299 684674448 373073027 794827950 559032267 110007138 159231159 414777499 839779694 553889906 341607265 581114365 246221697 396188253 775206209 414683487 81240489 95336398 261043901 250571392 82778794 287610217 357657381 431021312 4161201 700437845 532865896 445207454 109266927 821835229 733691157 285921774 192866278 696526560 954539266 326266589 734272528 918173527 883470364 292791945 997950134 59392141 945373224 979170044 581535107 899844207 489945984 401733298 693165763 889006102 417383367 828543943 42352285 231044608 900979728 167625577 905942091 58057990 757118936 188321610 391535042 249491443 76109717 33909740 451674650 442679962 752713257 843672446 119086987 651861337 811117794 79115920 104643038 844408100 907154952 941440145 482876203 713792426 364721203 36974984 602005215 676564828 161405093 605247073 235249974 869531534 5918631 474782114 700063548 697676193 480450579 284518805 261106147 352041486 9251758 249704219 808155819 503499732 295707518 180100308 57718555 731049536 861575219 911969266 778246617 747126094 473158808 771035817 368270716 277083194 249141654 619193920 738825551 672001862 397388853 798848697 100364025 938164033 84219286 674393505 773237361 433317204 965741055 210204826 350408357 725334741 603710227 141924629 150181050 6535205 156618489 586836479 627700852 464443961 687892250 570586602 438342465 557806721 900961607 576792985 568001137 501879313 806394679 598374529 883323136 133172226 289188945 656766483 458208025 990095904 443989415 268349035 336087295 59035020 304438567 46077694 826688662 963924513 708295149 391613313 820400114 148502150 69111303 499292394 870627150 986566908 233298798 687352181 386494888 857942305 303674960 504994080 824744838 396208417 732594953 731814686 459007487 811036212 837000507 176855851 234738944 905314521 404507547 428068588 94525982 94089505 361492602 237057356 627491057 57469125 475549390 379386652 994818744 22633754 976121275 830139849 80769791 730141449 271241299 317146593 585003922 406952392 682648822 796277363 729376962 707996398 15224809 713574792 937241164 924194809 533059636 263928357 261944658 347885082 821704448 127788307 531273283 417049134 271973928 679329381 301797970 99061518 158864903 805353936 583500743 742851858 343745964 206865568 738630890 602323021 208512596 853040207 2719044 5064988 268800600 182211608 778125405 242695109 972615976 673056246 112570512 615119786 666089170 408487157 755655202 431108278 861699703 723225305 330309893 570797157 943716229 458881220 899696367 18141668 196908439 921742748 688600936 158553089 868935416 42624393 662623358 730466482 811103064 815734872 448357504 407547007 607196524 578262853 885889790 287030524 522568913 966667654 918720582 674053514 756762566 219652076 243826493 371737646 514577484 43396630 988770949 389433983 941940411 955669206 448619732 219847642 599178538 554931390 882466448 878809797 290444149 912426101 801664911 486145947 612777224 762904128 673981786 921599628 501065740 437558737 617026980 902836937 332837104 881193941 505205975 928627343 239298224 914954660 178850470 309894072 695348526 47917575 676602233 899158971 226174574 398529327 741726056 626569053 953187525 330767544 996393248 489193916 106057355 770180532 207134393 835018441 550364024 450138524 878566071 647888101 353620971 832842447 849084903 823876188 113311847 532222269 842941431 843661238 130889440 678319171 798842354 377171669 738486653 792022563 568744778 392207167 418195273 67225356 423165974 917272091 737102093 938544379 905838026 977649394 89032085 657009845 975369737 682614922 738019643 86415268 462037839 755107665 643675324 623739557 92315764 712034950 435980605 127472036 401693967 270307105 382111916 898731414 581537829 842979720 755366429 548430762 63540587 599133269 776094659 546662213 542011287 859040969 661854118 606152953 912641903 143901536 328727593 49734864 637061008 205110974 90920488 443586657 85079164 892595880 34537451 891705343 484045789 565355383 814345286 534038658 394219608 854030081 202920252 501127264 37904659 162701439 746223657 562607340 472949593 434759775 586092696 335264229 628003967 675451063 427609889 5449239 806031432 381999729 402221167 246673390 252724271 300076091 260122919 759240716 885487474 101975185 315802615 33990250 804620266 623637032 251525314 366586381 945864959 650398294 11063147 367457500 935321540 89528461 844176794 766321899 290805937 489238702 420162346 188657505 684012909 674995296 727995819 648879473 156951551 394540402 489648019 948415205 659522908 500690593 285865700 707804649 556039864 440508677 471375030 987940223 377958517 667743415 495490856 388623402 842749567 24498107 841535000 597141382 933916847 17051099 130062963 194436225 201201961 487754546 975957526 840043786 766417724 367490035 348354393 506656626 726187639 353315729 844616467 613144618 606519004 433519949 305836586 327572977 607969031 430884094 808512018 733620934 312949442 448997061 46605320 755969237 454709309 97226466 818237783 984610836 411386207 180324246 528366788 207104896 918667806 324405629 268352511 201784073 621168405 418237595 794387029 513734072 423784019 826003851 71800299 443137455 486527019 149854447 776167136 462042286 366688655 268152442 147295187 74722722 542277207 202680465 473735877 119777039 772328686 689906125 225121924 825032655 442534776 773117503 198556466 818140500 855502824 514156700 526964340 447907663 511983350 713652002 608319063 23928303 551737082 838423644 215166223 688382681 257183384 16327060 583148929 366091288 659323061 913804008 484669368 652450958 662788403 381914213 194520416 906423264 851029077 626032495 459081928 543129428 994376059 358165491 563822487 146394237 926818889 99767502 605974627 406611269 395789275 234559172 843286292 114639298 151618612 428136745 811232986 720740015 239818832 667392365 292912494 666166234 45879162 134606695 412262751 358606655 787351064 250608448 196356551 824259440 333895687 549771087 723219061 211093793 992267251 102256117 467489776 925441579 97454867 371009908 184412783 264227238 185667570 946911715 729147387 940995130 973232648 678037991 85650750 118869091 738736102 226285405 404194376 299687006 52180271 154918239 70332583 978756031 172551694 854659581 50082078 726168928 164147787 668451161 15121135 260697719 376357634 683357297 3660791 450681695 2934621 870343045 357755527 161615076 369951980 981985904 309852584 310287734 221664736 397389095 696938986 969736732 294048667 582488207 29333581 342062468 591548573 509819997 922357444 851193091 804512818 130944253 481247240 353072160 114003636 134546011 735170313 371390651 907523049 293667658 314221310 139475471 402956197 741746170 935321876 848777225 974042551 127175736 286800358 482489620 481655508 886120117 683290018 743403624 239713883 2484619 560035009 332917548 678725729 269537305 311807358 425101831 714270022 526590233 301723786 469175487 994521865 644887851 419845026 644333800 327149826 423229275 144323827 847154566 296091653 351172105 826884368 694456844 587923754 444840469 315005550 97578260 787551574 236022256 231709668 352938373 226312869 448485818 254689437 834561344 688209319 247904450 262505654 330535444 193224982 702565124 496106423 97650102 731359389 698088322 385932704 697115336 928553888 588255399 619288237 15918345 858973872 898648249 660643161 680089017 895749108 588013014 356503011 412581137 705445850 416518944 24434225 578528291 39822077 709853933 855120513 556073770 634648819 165772710 811102573 530770817 687486119 728613517 260987763 329050233 481915604 884107455 235163633 514006156 83219626 5700466 794016929 502997442 453397935 800691282 453723354 744660736 895585457 101428097 171165674 841484391 921427239 918265374 819570283 313657020 876314127 350839350 11317928 166171397 696846949 453945216 714287329 487570138 670761623 91452914 70576309 436951509 373283192 804775261 251557492 543842558 771330266 880614729 819351477 128937335 457401229 876584629 747673048 4871156 286572079 265154889 145783568 264854517 899762532 85025215 784631009 787235460 108353359 869115651 390203853 479485229 829685661 502134954 713449234 885008944 262366155 490588406 506750276 191777147 4080806 715814150 355412217 573228389 778147899 630404517 545216582 454243900 825022917 877104057 48926327 137300841 251551162 446865591 737065782 665153851 916398231 561947763 723252002 341502556 959960829 99364611 969034845 634035080 315774750 977105444 828158688 818909491 775550122 538662263 49541423 976185913 510079233 961494386 592086306 938900878 508273509 243228520 788714606 565147982 136619072 385329632 388553711 401609607 163027166 852180787 894326785 18105596 436163903 907140465 184706891 144755687 98683048 105012394 573415491 988508211 36142257 473714562 783966386 522593866 174128352 95423830 142286426 657110793 755852437 144572645 590964267 386152256 358139987 134046831 315959787 730627277 672004010 956591625 858557844 904709158 801649625 664794209 9505210 274654835 354083756 517430602 318818524 322260047 344776914 623898782 718056454 892335212 535016035 751732201 354005307 149389005 762774493 43669947 446146154 500927863 645047494 579532677 128355122 809238017 602928035 505301050 145853147 928556782 510513393 328742066 845255001 207052091 741622122 481382124 269402685 437604004 85669419 743311286 428319077 292312236 252401213 155890717 828874179 634360686 629412334 544945612 741200101 11244435 925765141 452547373 246946526 369375991 965168861 54975237 23896076 567739468 671346973 907526430 848779243 391809782 270472852 817666520 283087103 442740668 897719981 144955399 172089779 883227070 62475659 185514065 170088989 214205935 121168969 344961711 340971967 66631459 200826248 67161793 38925655 756050876 20699289 182905514 272290833 752444589 373523823 915193211 146968648 215010190 401215594 822473513 888954464 906117067 950163066 506673104 709550977 938489449 133250026 28315391 840033834 629132232 815980890 494025332 682739634 668997608 494352680 350475417 405623443 700702546 646745688 903313528 317670147 369732235 108421123 953988280 817861931 965921996 612276732 504426559 730164695 6672920 399843642 693254045 475990312 701535222 535392150 409795406 132990544 20038063 219631434 301952635 378738687 725208076 859277181 657294791 696389698 513443288 988010291 785276965 410068330 541899767 534622948 903250726 988086051 695006379 808354317 239786300 868929334 904089470 140183746 608649398 888552381 921975351 151957560 764924356 588296220 568128877 707979857 766916331 449557449 747335134 40212327 450983509 70493613 776112872 202394107 867601561 24939118 647802176 730683461 966037001 329240392 984070152 315845901 948510177 300608040 860910569 696847287 502492297 728067896 784676373 111851089 98650783 706512640 140446089 327653833 447918771 314947097 980576802 760636068 154709331 557969021 931869284 850160649 748941178 147529358 115741554 742541844 800956638 7494436 688165030 514575369 760848184 211485035 435444707 628001446 406851252 357252491 417059574 736304334 612106711 978177527 110409828 132094396 206868428 437146143 160447853 773043525 208256073 279633339 933055186 892398621 56192177 238496226 920169455 29641854 948138044 832384854 653117645 292760005 986646408 388396677 671673451 806781733 269372930 518368495 181924460 202354360 896281810 505492528 366792874 853328342 728064271 395017823 255492637 402437840 605823274 405079252 148669181 272241111 424566956 565367638 995230789 350256370 968127369 593752170 276319224 566386960 191289731 660487836 715143327 600676846 461382112 273983585 150790612 975264589 406192392 504660555 26477057 615131686 150875678 471407613 780606519 208824753 494829310 540105436 780302094 581587352 77255695 227605955 7287511 740748527 764002135 791811686 423360103 328057733 969704089 671303588 330533084 673777623 320782085 247760623 808982588 89993060 188207211 483352158 588593358 841067126 278928971 67502612 37180775 416742196 906204270 534675251 369413263 671072879 790063913 982382067 822419425 281760829 681451550 916381435 626439702 503775714 183628968 811428187 405615959 808897148 512042406 649611351 889296311 267950616 521070253 813394956 485196894 937547674 383710981 757500080 864814279 654096770 933638138 721868711 114376184 220041978 383792301 978749336 954779739 440507307 423356693 590571829 247034871 904165084 804653974 346754487 412338887 801273967 761706413 151479335 596559953 767700676 325390628 931020408 189674844 901702771 138803767 393430118 103695083 224278643 618830662 789840835 303538452 294407208 739880476 414197689 150926405 32002315 2216463 368843809 324186285 187677244 850724422 713578922 562413155 152562898 218263506 151440050 136247065 605180783 7444147 100068539 497325903 853024472 52492452 454836490 203623362 596256473 555002778 39453660 44462652 39337730 229846014 829346436 13574116 223335145 533382888 123150506 126570052 418283186 59575788 499623371 368483009 468960099 715956647 694834831 861715994 1754218 770230253 836063913 182882007 85148869 730876602 85027634 343444318 829571419 190536941 3642765 630407498 205839220 299670809 8362080 2688859 234477375 826403428 651478630 198295001 266424686 242667550 101754896 421783311 647031402 692822540 53548819 357685465 605251896 996702083 385673658 624850327 888636928 112275909 176870489 418510919 522570143 610412247 466020739 976301435 520314415 729597277 586422059 748276029 630994554 525129143 426342886 930609030 520891796 61994892 336921638 546331552 565090493 217235270 298946119 72769675 651524395 921102990 393420615 913405941 969172710 457278485 381780226 479392049 452724896 143872933 1515607 318031377 400789596 519764641 170171293 7515854 570337902 510743086 302144357 534177078 596311634 727586860 891113777 198363241 171665264 770195310 460256515 994641728 908101238 113234228 189700838 854692621 342355547 219151303 859062514 292812078 625915410 452199460 631778325 216362619 573845731 840174524 864813190 670341266 412703892 393356637 354081397 573831422 669111109 597204495 801617365 739926606 86438489 892008804 61234587 800592300 813541887 780307662 943224408 930015647 779420988 316960680 994358439 685916863 957498990 593635795 738506533 302998643 635167884 162217345 364783476 589808660 225568824 497297303 956369240 925424612 106707464 509152674 905408442 554437336 674951998 673056016 159444127 401527055 326710809 396208802 50157023 486057209 779674035 845013043 640079530 993571088 773058611 45394955 970953617 355578658 198835465 546562515 648599471 220925298 396729315 902120017 335660825 726377019 505715843 566322386 448586607 399792526 532373671 469936191 850925740 435174135 4786595 709968648 128898678 25680313 944738571 382736584 547068534 584987673 397701826 240274779 50445303 855583673 491123538 633255010 789898498 458811868 59412031 959633072 440674329 867675750 156290809 614368212 884862627 639495146 237833896 25782804 573352807 974010984 956279303 476331217 427513153 709603846 24902941 142603344 234605441 1427379 106320588 802691508 511747865 612683214 800498878 640712986 819836520 741580825 901374588 589386102 866089469 921461715 548707508 110354964 736285707 79291692 853845681 507399890 115063769 25571418 977863965 445004890 954887843 524040635 723670359 839715722 689623563 580608082 434969783 970684392 413667798 44046727 464873623 423565278 97487677 200289434 43862578 182902501 528699311 139522243 246433729 535797114 718040030 945442311 240143667 161670706 722663446 775771343 235188735 272421528 660539962 740688117 999064154 149497217 656828971 104976269 227424304 35229960 80776508 310524148 60855719 101728165 927757811 372451113 651453265 198438066 886884139 811306057 538780844 686490791 317042041 678860852 443254957 20039646 91163605 511183399 201729463 42891053 320143421 734593762 277252147 26091539 96480175 477243044 673871573 472925367 681400644 391610797 142290649 568586622 551037821 540158626 229857402 193981334 489103524 113517255 471644087 93465505 22089323 364174122 252367172 767144141 730896146 470629787 197660538 555766251 974025172 731558860 945137198 526157418 408406553 85674457 116459733 764988092 609516905 365728700 268271107 664924964 678292967 536264893 149769230 613729062 225544715 414046927 868688393 419941256 933744897 890402497 847716231 133140396 163916054 352649736 47209860 760194843 203862337 835123153 413091415 651283578 948803417 332824968 851006428 913103260 813994570 757547121 297221090 709376943 196856166 591181332 316650158 473921379 714293782 791309612 910877741 478918829 23134469 587182933 444454754 456016853 395075793 325744850 833900140 516927418 855726963 184924482 726086157 821705902 585868176 898647304 105584169 306525879 360064601 570595124 279802741 119650622 409788923 753335489 780152529 972187227 618668371 979181397 892418707 937616015 337327019 800882759 175714784 542910007 785313596 494262984 194969419 496439907 637779936 13767282 920524626 691754784 621801489 701146067 841201270 62204124 571440636 866635222 747600127 108271570 584241568 809546255 537129649 762160588 844379969 210001519 109757883 6118623 168252159 620137344 183215332 37210462 388925127 381258950 761553692 649683002 562138698 50470251 469316344 330120983 542228847 893132007 797307557 819388226 391459091 461476362 264130996 121925157 958369014 568667794 783098196 319236788 844707695 679307049 776656829 504128980 41724432 444560518 830481476 691922806 729030947 416551656 766501656 652176219 926046023 237002858 97077600 284381627 403520022 71994719 935972676 823619465 127023811 499095165 525552588 772702440 306049097 899591050 995024730 977751497 13746803 476124601 919758213 760896149 428923575 611257504 616325967 810051662 889941086 937247172 409513978 519270654 884983573 359250316 663161948 65122044 220887575 965134279 125071992 408110316 605609746 451307639 757661560 783198619 103760788 925660821 393261585 773269370 625285850 122797332 124377984 923202022 937376307 767713203 467115037 586455781 530508137 510242708 158832277 427343349 481576327 985828945 323966463 754798812 14723371 981847500 570027693 817486896 297474203 557242032 610402269 431673224 898902518 769782729 356293091 699096885 755009559 905125527 812317421 367131947 109871836 784881787 821983514 632747709 230811729 17686778 855363537 280223856 580102332 720725222 85648456 652831782 212108961 739141803 113169672 392883291 761961454 678517532 767698910 873204466 123970612 706595799 903406373 891037390 579642055 109991985 410619864 907480706 787947185 464903985 528356986 17974439 891337538 972470129 669849888 319583291 807220567 92035307 498414458 368426844 732772504 632188602 40630517 537748662 52289887 617143208 193213188 565680373 670235519 496854071 426929809 230748452 65987121 758004611 411805971 280314408 712089589 698705686 667235654 284442196 222472933 142786572 640827619 938233625 506923026 522200452 966714618 788729612 950326463 135975616 110833250 770383439 886589167 683988618 124409006 892693787 27999579 98704767 269470348 621245399 648529525 879508680 680203002 978541016 444959481 81524243 160613720 645297648 943475644 434519835 444469494 668989265 446802985 761236229 809451269 867617777 193571081 760074214 457714865 773990470 536554152 70685921 616423049 935815576 158922393 397867969 11193126 376066814 703104492 711859709 56451260 222116387 953860953 116354646 317439623 213684227 655641197 229300879 728710371 482029947 537252645 842678943 339014930 485099916 103833127 432209447 949443540 395527687 644726201 472825762 380990512 868339491 143317051 1772142 951735023 245030830 356865044 840662288 21717943 465086861 816267441 746320527 847274139 671426632 451522119 657969065 295415109 462848133 470278080 988736491 184484783 323311661 463478355 650662073 860183558 179214441 967915253 179770003 465495051 874099952 544106866 793627396 861473119 971875411 695414911 271040702 27079247 539504693 771354516 307257988 659306681 983942125 760142781 379533320 67361064 216832274 792577184 747335300 371473712 159297698 74804977 485558471 88480504 826849424 709522495 571995710 952161855 861032340 448995607 501401949 842618519 85093409 823680569 861212552 234865521 334191494 250351709 698780826 673273402 672096979 549303067 530547063 526213620 871364972 801133598 878500813 107156964 721041679 641272312 442928928 463805465 65677484 593927843 479734088 134452550 581225828 213877969 146394117 993277825 472993679 313096701 399122171 231189358 85731517 643869986 387245996 399453854 958921232 849975738 380459905 700515936 154593251 317220839 911013904 800826795 72617771 302977545 703769224 595606342 365013234 905183249 288422044 693793714 930422850 839546478 306468830 608425616 150476718 967433785 656364418 218635434 66132122 167212686 137108754 576548494 444236890 415378253 406805681 289864079 661194273 784111961 993816095 162822845 516219835 740020012 209204985 376291074 376634138 952573984 140125969 671362578 312454339 862647286 983327960 88977193 706946721 759461444 603338582 195860363 706394550 198134971 823161025 209499395 87762249 163458558 895732662 250962624 925806622 10125058 569847103 253327674 292719602 672113527 44653391 217038228 590712335 24877216 530380383 617190678 356222902 416484659 55070141 903403388 265337114 185463349 176620712 37837941 279377647 941272858 584647421 620840523 22176249 269218219 622659128 437867184 342427062 291813141 109568861 81861076 392867649 775080281 804020198 806129837 995006864 612797791 647299564 730946426 972081641 884534519 460829734 173654193 448233234 795558696 247410741 717010306 441442590 693861432 930842127 859659557 184569783 982261074 343913532 187217200 420700135 106561677 620799492 915249932 118002980 251517205 483846913 206348777 696870303 60238778 271360680 422255739 425225050 699284463 93784355 593141520 506835311 98557815 57419163 111271437 330043767 565256231 189998739 965694369 266103855 147984004 610628644 409849852 987775566 513378113 346786751 655039249 664980228 100271297 54913692 5554006 465571524 766014299 115627988 576109062 954454150 34081580 735187586 848425 377616539 666412095 312633412 249505925 676153914 859920100 164080478 895649400 852605689 112103703 703452985 670069581 946801288 652154808 79421422 796724127 687448365 662209455 482398122 754664711 344822952 613529931 612734146 93426943 199417259 592158390 159017473 361821291 895758944 459272726 739989499 420448944 178790370 983418178 945664258 459211392 41286442 314883479 128752159 447958345 923674748 50859087 9169960 884326644 719640736 999221820 634112614 159001346 745907595 575615242 58492342 75657981 233480394 810887232 535165401 573476196 715677933 130036627 779184829 54559622 714454278 404886317 774639517 265435125 173376944 510056878 583511977 65183511 579561277 405954783 668251751 396322290 728111910 236746943 89975840 627179873 77367113 742350390 283779342 760504266 359069184 713651867 74484425 180151327 351940402 340138883 842645874 200143665 145371395 77148761 947489604 755932460 320093462 944306192 536525481 539481574 118228463 744277016 23588921 148606758 764050945 657010922 915850388 472725736 391320750 587197836 35423263 499114960 587328196 557695631 825183399 879947215 349619820 979214952 528393400 619565232 352124780 122269584 894462172 528933233 607009651 610556795 186664737 66749106 480149452 574256839 883321237 847969943 697081470 645673148 748652994 733415081 85264175 555574505 971499110 429009885 731176398 874517630 858623623 813700607 758815988 484393650 725671351 774348445 579228056 656191431 224587468 311011233 88190593 157534260 652772234 133664556 211486829 194417245 306917143 75388161 420041568 323903445 248480292 51767179 776294786 254955810 91006719 975402890 582100258 997077917 337717960 622416992 722261214 1291282 471358040 719214354 221725487 942083902 294748844 644263094 63061179 46762665 8144538 121604044 228476091 630490145 63512031 892350395 353383265 566321362 639800923 227844016 687460187 711631251 556037083 270160399 495376725 250476831 309598270 446986877 342079803 593268124 831242535 747009615 648718861 203051969 717738540 244961746 3714136 455263232 928659242 648059261 294556272 238157558 263146344 27602159 798022526 576118964 577825741 770067295 822509281 491902947 346620754 405553448 782750481 719517959 64132662 896890694 1440466 139250989 713735834 442261829 305724087 321416572 453772102 336167612 801185554 46534502 998902640 901511516 527245959 893540383 65649167 263805257 990321127 658876868 782446300 391396993 33740243 862642666 110941361 135548956 952206982 459685788 894208454 496430090 731200010 662825755 4041374 420952823 446206554 192425825 810217741 914976790 569398556 335065224 161316305 423588341 683248209 86389370 405783087 542446835 73747780 130043434 181451579 766250572 639906107 150763026 955271727 67730763 567961815 366865427 111404972 456697417 40813237 571650615 152239193 990939488 860589291 573840001 904924080 952780818 725507029 351775611 618129876 11843899 80478743 120057017 258653879 816001138 220649247 550699594 150344017 468390524 19543619 433029905 509806568 807436951 966678158 274038258 828851139 390123992 807350497 967770915 723395895 546452743 427250402 680383520 104920078 764381428 262943222 720829700 659872555 7281185 672517048 854491612 932339157 350990607 323410658 105567890 514484429 864884204 381285496 956158977 278674565 116716678 583111360 908932667 627629108 593595863 764387417 59510017 157736500 154400798 206649761 353283773 806543660 141267040 695757206 612353195 736825383 255305014 398822918 383712463 452439470 850621084 387581812 8195568 107776954 750484487 189238890 869611315 589972765 713709409 401805115 707249153 622533359 438661596 830804799 338411911 83514581 23707105 798887153 330304380 533068104 689357516 983102332 794110325 651223098 596331572 605560264 955777502 66943144 158796188 950315075 579559195 895234487 119542203 836677762 516990991 848505966 596654405 530406975 572667338 287132059 291395938 132921849 683813598 795121243 726047921 968431453 477656360 680175608 267347114 742143631 529215433 740563569 801890180 336302200 997387165 936287700 760317877 350708569 401653450 241299601 924598970 502174648 530006626 132368034 856687089 336244165 826178173 380875417 54573211 415129697 825858269 201532220 444012775 988019171 701697809 325368731 339314983 777196247 358743971 516055760 901354484 5700723 712112560 315966446 943454654 371905845 79191085 583572484 60908838 743028256 129705731 719377159 808339202 853105043 394071795 759857505 442523873 527264990 43195381 991234992 373578592 803279893 328853599 332138701 594918200 401091456 727560833 633071074 14901118 588179667 105526851 982893465 546037310 621491589 169107315 6997251 740107826 986471929 426007074 526646212 328256899 774797325 813296978 4431062 632520494 175469826 477449690 618924068 646701778 226210005 941736510 55818099 567917381 756747343 982872798 745161253 416424006 299152580 746327271 185594654 347833416 21061962 834997405 55105414 199225259 266720878 599895911 697666825 873265101 362143665 258840668 605201073 761896577 431071424 128522141 889713004 979739047 385217105 349199072 934043984 649525364 674989668 212365366 816755795 949873159 656447704 567264817 40426137 981214195 220524538 987912835 954024432 93576597 663767203 109162592 884097980 164363649 103593218 147426951 892487882 888332642 987167422 450155211 551543977 37945333 31036507 220655080 743560782 557232962 774286092 380710685 574429878 187342938 806364370 846214638 552360592 101783152 87298568 73911490 920969001 43286911 526116057 435828916 907352416 512370412 860184147 406594187 147918290 361730463 410970013 397651134 310782773 475514311 33808102 438900982 505606102 769162510 122876204 504863390 283655739 316187810 223451393 236796849 62373489 53945970 727485948 596142315 936585345 564891060 744754240 843583728 813696172 10157269 22258531 741483098 541654960 749667046 428820365 798428454 463997701 736707140 777651833 265504405 485784153 499654592 878893602 799494837 495956891 600041490 981717070 662840076 733199505 271248841 726302741 480171113 760705657 134841018 52462168 645909908 569147399 59532865 738653928 392665692 776820826 958168876 453058681 440617897 888304538 697133331 908122638 452117036 727457460 897176458 856249763 495824443 435233287 140376088 121559943 279548347 456027349 845392471 269497639 69508761 447925004 870418026 344520555 184710909 331172087 511733029 558769209 868674006 179125071 896431831 418991797 5642430 261304591 344599238 999562387 979752656 415177757 35534680 450866455 332560440 66999502 42790975 62843146 73589698 517468248 673065553 935637491 819578568 726011363 586192807 969523798 244180297 618522438 464434234 552664315 392283755 216997004 360157668 34489656 139233902 335049509 404763373 202826256 939777952 959695036 235203455 36631952 146407341 42950435 267839118 881941033 51531677 113902508 142312202 700875996 810138039 681053280 559624250 358379780 236930915 737233436 217998125 355057929 235492972 630677387 306445704 863706230 632004585 306930025 301040336 52948155 994430586 172104259 73082708 24492839 637542013 513656473 673452222 935762017 396009009 906087416 686006716 98456909 43665185 235622569 430359660 631048751 576572416 343996386 431534316 315216488 504689101 328207454 138322211 4936620 10839813 102168439 246302990 240094157 73939628 652052331 181208447 941802691 891149274 714839039 662353835 793453483 397205924 234325690 971215781 135011608 709587890 383681970 859883088 119228363 430801942 153882665 592277755 319541510 151084213 818623463 410416702 779466001 925414592 359606773 380953138 728248955 964737673 842122535 812296032 703555213 924470019 280041905 895521772 798747713 844978535 525240237 70687348 604975802 713683144 67810625 970647975 475059980 607217803 671444638 249898485 829267113 598691628 625535720 262198764 577816084 862503655 724584352 287077191 587468773 937302364 426173562 494253203 338125105 830601290 118419840 362721674 761685728 48472437 523553001 770004497 916935814 149576370 781843951 565504165 867214146 499673151 44523302 665815408 126928252 334709365 460732373 88695042 140158700 662819 666601980 220732454 148802667 289738981 151234789 17261265 385570758 809772849 359047681 595098800 518984717 54972600 352769348 658622180 191665880 973295272 838113677 833831067 63610847 548295232 569541631 843123040 394214239 930205610 822979263 828815402 702606172 211993270 13286501 861834941 299266719 568569761 442020919 7214846 843830498 954309318 158838691 378005700 115216896 991320489 426398536 142052730 431196335 329544377 700089272 492673270 557602794 954300252 87474482 863699379 290592243 894677524 567586952 163552447 216138205 518959160 216968155 263563413 748537518 187411408 741060507 23489527 828242245 312708714 253813476 325289622 715097994 201696761 622876739 123466275 136666522 247346423 614227519 867129871 715101411 796386181 529357805 216661667 921522991 402206020 50146435 366717887 357914315 682450387 156485457 550944268 258090804 668269707 456852086 700669108 971695233 532577018 582386538 334748113 607515195 639295060 832988852 91787783 999531664 465546059 489825275 857289273 124627629 337059934 552617196 692597600 52469466 584387204 653837843 186045421 63893392 928931680 363288737 973957222 8707186 635004868 41040814 888448842 176407202 462045132 942504661 584842746 354201572 171283247 582825135 156454455 412587167 983517329 264410403 108678196 158787751 460142745 756834656 249224039 709768935 585855891 180685121 668036148 118300309 21869031 264373325 697711108 606460125 795578690 300692944 309947051 125028071 677044916 862642190 447853450 852618566 419198382 927584691 130946558 402981851 354292645 394258677 559387228 813704588 486642736 770372519 289819798 869589384 494595374 141300385 941023183 727605388 149613112 381430962 729101106 512893907 451039887 38744967 445888358 568346887 319189478 669612203 890559124 47795992 734324652 837483648 94409577 359162321 761945676 657155466 212327145 15289563 319275686 227487120 266447741 689524079 960490224 223776806 208919241 429533343 219338725 437333811 422056798 927146702 362685129 192865959 550472846 882851740 279573671 778694324 737911411 623016340 203320693 830402606 437327591 667727949 642976891 803590260 275392630 676041025 172321312 776301478 253476337 422694749 284228153 844592554 759625058 331310404 783732604 896507029 107359892 822877645 792623215 433337296 630886948 434887574 331311858 394904182 909949207 931062033 531194146 364771809 799999671 8446534 642430842 695444409 413112661 294617801 40854319 550064637 854691786 349256038 143570058 793666095 439356226 538035298 245578349 905253771 401233353 140155088 157319045 637535600 630029129 866280214 957036485 569944524 262402615 307683127 778619442 172027851 13958404 591903639 974152837 993962872 910090514 47711845 984620537 227461389 349556761 325440371 766447282 109072671 63854180 779546323 542454870 210244480 7156101 458376545 486970025 795999327 977355745 610109662 80943041 78192227 215912753 523781145 676689677 150867815 411770007 235869006 346856283 15997103 403027231 514747113 60067137 940655836 483089961 959457054 254873672 791190197 174957272 414065831 488922328 444461575 485982869 330430443 572647138 360399109 589721749 447209769 843398078 771980620 957871967 286708110 132499723 914037145 383773633 91365871 411478590 980083461 868818552 114759258 585820517 683520090 237072415 877433637 725143782 469969488 717080746 366675856 552243669 918599972 296240085 772785585 582286157 37514761 36894312 208579367 739060204 848776870 995783906 590617769 382858305 486769671 139872875 487141416 124553930 263945089 346338219 885243255 435834271 126178436 822746759 213602930 440094554 455670063 647768701 505514825 100385893 686805774 257211336 496925229 321826720 331309599 607293306 491968489 517201897 894855149 64916010 969418949 199254476 306111539 729846365 620897882 541510379 206469205 8746492 933248119 658415475 286601462 798394853 136502248 530294208 419231398 651704741 272581354 253148069 972001550 131479602 861794501 162622278 797082356 761068016 568743418 893362505 217305682 926552082 934575874 259300326 741894824 69193406 535773750 556124607 40445562 344170953 172781976 692079171 105861744 670229231 733066039 879701083 513024745 353506890 243364632 626411742 523889248 980138361 7831826 713710079 137021852 992781472 331185144 23129172 749703716 460504231 859489582 577147191 352117450 463344618 996842032 697087904 477492381 806331188 765069917 58593511 756028962 676096044 249847705 947082636 915330430 378051714 374618908 12802253 482756716 953575907 524946580 475689831 677537577 418245570 281839126 187042788 489600513 130160479 358247455 793758419 415893890 260945568 247523607 112311224 193367109 56383553 556152077 285807211 499731735 354211501 764045158 451409366 211252295 401530579 514199918 606792128 718578832 793773557 366323656 453918834 637723482 563612947 169385982 854575757 757603144 408080184 105230730 169510754 203629643 844727613 20336611 582057577 427410685 804059328 866790675 549504364 885823195 332977681 813416224 239092180 847606763 327111683 145809743 327394122 904435447 646367752 29044708 858602447 307336631 420364510 435014215 323686619 8701297 395985330 763418252 579380075 899456165 99521288 282785081 708445263 224949933 74386095 837870394 703253180 322230303 775199674 117100048 863242551 877818639 860542590 585507353 646206749 35262521 618465150 573216137 311990351 914433548 379517852 439308102 52527922 62231284 695483332 309578764 508519846 381269136 696773683 185567099 809246096 354149423 982300576 679624122 906796425 962816963 527982738 767739779 975434885 881519123 313069190 715581068 223054869 51630001 322284511 970443753 257003367 744801925 1862841 454191752 519904890 397009496 605773631 896468837 885175598 45469566 671043220 108477251 750804513 223734036 306666254 981203998 10642797 629913739 393771356 635856874 601216920 221978432 752895994 50851373 7802406 151965973 564223594 961957437 289725817 42701448 994219535 262923196 466496240 986881609 220568136 64065551 203323663 336221577 462548608 517889101 587710276 551065541 347360327 901493715 688381369 989541270 569510937 449822204 626996412 61574003 865769662 383751962 351153848 242557630 225922370 75186504 336776600 662456638 275268964 441913497 294436495 981984709 362308699 566771593 830042386 663758392 896381596 685640826 669272278 266907246 911699862 661295667 77655869 538835603 234533448 461793851 711047076 579771382 912358997 843388700 607425617 125230132 650059825 234485415 267352744 76900865 448284922 104802138 331625123 419237004 66371612 165745235 568019726 139227663 482361913 130923441 398497515 113603781 809023898 193865295 955665628 17186635 702916129 50898543 62861523 545859910 67305598 892920789 17183868 76467168 304976390 414830094 369514682 342621606 204411666 978386583 946221035 664760548 892188818 421158887 963345683 80413783 695431577 599233670 962334785 666220338 808932454 502903150 780504615 326325754 433651824 193281002 610636272 676112449 668799356 664162682 388990069 571258296 387022311 9371110 565203596 544095776 499160739 184412257 382191366 119568633 43584971 58825452 880338529 925802822 352295141 616258920 121289415 42083618 915719064 436867821 701697913 869282248 524843798 577655552 617103235 246048959 383327248 344221370 756080363 175731877 150172006 332130477 622323191 746622939 659234132 318354581 845890815 515649556 749227970 73140858 443726182 561856086 938509129 324530382 138729329 727489994 858949855 618224206 57779430 352653150 727450129 951298506 476037863 876314203 674522517 277127883 671975555 665586821 871107001 40051263 713234674 626196022 376570221 990491864 726736363 72035956 440063802 556590915 352708146 385118951 562597867 822731250 973567053 107781214 729301924 961459715 473619998 722197708 270709455 285121860 868799093 245477386 877615445 840255638 921782381 480319976 895333873 55754320 790751380 785159484 576354821 626381750 835395810 493099382 796679927 833537810 848222544 74361424 529367174 503737612 272234743 296030214 373798343 511754969 842265713 561241349 861535466 719523021 950671467 428926229 622212450 900936909 643264386 790099257 864102877 8083944 226091085 110171615 315034219 713903603 907240815 296726864 315965713 144811882 57903898 562836909 964611075 593890824 211079289 886372527 251230525 132304225 892106170 399868076 540092540 503534920 183781452 487478004 53533802 618890891 319160451 389470008 605506646 232422648 885493878 550245567 623035723 406372501 386872204 646652329 723303693 584112119 715641007 47206478 764906442 781349298 806833772 633952651 419454464 723293472 309634110 555274477 829101656 57585920 360866838 284433033 589814174 890154853 55669292 623778744 210259867 988469115 921656975 52638112 5441690 82057002 611859969 156692973 455264430 645496214 635955079 43310564 1673344 642816615 163874226 270413194 483451471 538141313 93821144 845748150 463568674 711828243 261210744 783724426 526580727 172082077 740538013 458680428 665422878 638212964 173554446 550218962 942727131 410117056 77030900 126016536 733503678 482229384 599272831 331705846 714540652 546385061 149980694 401357665 287782563 885833215 633819570 995495942 638267089 130735448 809534202 318024983 972523701 145129521 866407136 455342955 407174491 772252193 162802312 613126843 932548847 187425779 873362765 322699791 258203217 122332946 288457964 286747257 514309008 234823457 652752451 602705517 437047103 640103195 329196031 967448049 473768932 444174530 94959996 203292673 915207394 400537596 306548053 177122564 61173658 617773069 338221756 355800021 401261515 328590127 441555196 877637847 490213332 580241881 418590371 24259285 808971508 366711308 457359166 119413071 865038224 452920141 755412949 106506173 947997065 999855628 531112638 958260593 119894145 334774464 791114328 98577398 838456090 240522879 469776379 854354556 675339557 181036325 947320746 600304229 383120780 577589402 579252364 898007569 543099261 946644353 768038688 690309102 929365725 520888028 639118123 634674416 385032882 922363675 917403284 125303600 571959516 468637580 403962554 384106599 403370889 663787162 28823816 528935379 456062946 164979227 583021496 306687861 329929518 914579791 657981004 248713435 967731807 582465178 166590801 616816202 824188557 911000907 267178512 728325940 356094314 862182890 764561214 723287033 25472360 105183147 498295571 25700370 700230166 716455405 922363263 264543268 423646792 827716289 998687826 569790965 548587221 995356796 690975357 161687523 581965552 731871541 787708917 324565884 656742823 167467300 892436966 464826057 584558887 819181650 967503996 993941637 988399972 173853001 728966576 135848656 803039751 136761770 908725308 791105320 189513110 920654608 742166497 813443366 145308415 806820249 938005292 591191954 40058414 573180390 357657941 546797666 395745098 142706330 633742784 131549765 377948590 378248227 322121033 104667931 694027045 83128597 83197527 58855461 110172148 390940334 907981021 755750696 956140063 726348729 166254512 282747775 268139995 62248612 995574627 757853172 492276315 103888911 643691758 319962909 140557571 403641495 326611755 479767517 224777621 42470625 931987205 669630217 495056100 180152122 769179894 284523518 993680113 391883654 876375830 39145879 430725789 462894701 916247434 562994554 699003574 509799535 677759621 664026784 549664551 201026486 15292381 768779401 814125213 818866779 152410385 85312580 858667453 646950055 700979616 94199786 749569593 696593774 613687989 150216174 864231471 253223279 124222870 637809800 773203723 131654112 66035355 429999798 554275373 5709889 558381935 602500170 781386978 861111248 298206628 285558266 438809353 775995095 376337500 485208740 307518396 28855175 655884447 134387801 672090890 625689594 828198718 787211061 80893523 781304713 5591998 858290873 132156953 964795072 505332272 442021075 999555100 959722715 786912038 26733336 628073546 260007891 242176356 422294115 933527194 696331939 788025410 294740851 711780157 967781033 578179447 819718135 49804779 481502512 661431370 792278169 209441479 729174874 430426781 992032854 864867221 597031655 105917001 26278395 120286268 189938070 64990452 674215800 482041342 422324919 850033793 118951612 888316514 399495574 930346162 461897090 388872057 188532064 997898500 274573888 5959303 51802849 103403908 575443425 384484801 583168347 666424376 260580858 228537802 30793132 455773189 733392484 854649892 110144259 957649851 293247130 316165967 387994458 144034368 338279440 910763592 12616876 862199275 291923037 765869416 737398346 469709875 141799314 918632867 978127006 699391193 929735575 309061154 128684675 114876006 678561900 372040259 352707051 706167320 224571314 815018063 547824153 624300962 755730265 404366967 494525114 414316947 120229065 35013468 422256377 323495009 650248111 370818843 109464319 228352499 368832436 454440998 446018794 154798095 504861453 459293683 924757160 382107648 772726769 254416417 280607917 558157661 620822881 646771296 673158973 72045949 698735969 882377925 265089157 496215473 688871021 847904081 623761405 826571820 450971475 963299281 106227776 647273497 62691035 604324555 531452612 153445196 151341137 123367650 754526723 867360914 576439414 536652200 112841432 200214790 883449450 330058589 762250262 684861883 25932070 646089197 651355528 874407162 805224780 719285746 601159043 398708031 682296097 698397436 123657364 116374841 68761626 924242696 324157191 818555811 605791232 819908289 828329777 136448924 86795357 153853436 910987153 286697748 82651801 170095063 841294531 719686967 925560850 812479470 257515965 774134085 267246654 505577933 213951461 588331766 782340031 538310947 8542180 376945604 114546513 269493538 401110857 662305847 535943538 866436148 269769193 919789696 628788712 96444550 275336847 373108437 221503422 102241786 804250906 246138487 944445915 448949362 709891886 340332885 627020620 504479022 289613322 876119917 827113675 456272983 27653079 22670316 450594729 392868452 771380187 153332222 345185534 507604038 336767481 71250783 202276123 471791125 916314343 825493904 308826599 514670593 801999373 634316768 842428030 240334197 559231857 240899998 571401970 929528108 939883388 894935023 549502583 892342754 828084553 556374995 142505975 488493840 3664856 947451470 899495256 753839246 301562802 228723624 632612438 226075567 507718920 57610145 585851722 603894316 18994142 19571250 570563735 237965208 780808048 736185316 586993675 294345844 434110173 577892286 577338701 761613898 690326365 954757773 276130221 879559950 51299305 623906589 416003179 145824495 981648913 52094390 831784608 986941362 168574424 791268458 506013158 650891682 182566055 292383404 748803248 214599126 198903337 484046643 630671076 976023709 704244535 338403126 731359050 77893738 771975121 463575398 909371456 918363655 43706793 249066143 43754835 514275273 346436920 182780481 656744288 885454784 122200091 849939030 618986769 563338845 710926492 818726248 698937793 605732815 712115767 672094454 235202898 432841549 377135651 788517656 316137526 763363242 750427053 682330153 259845625 644779787 713495927 292403847 654767934 196638280 835222920 95974365 683702583 865360857 269521157 583086695 2584333 860535992 625414858 358703711 374919687 146980130 573358934 391907674 906986408 925859 696131625 945066249 993719788 246213679 635923719 916048195 622373642 155332979 625821698 385685653 701300895 999685002 769904353 325145857 931603420 640380603 894442615 736513963 938711696 463120137 235982431 646278235 698141987 681046876 808430998 146855280 693263283 964359107 805074953 463669737 672429102 509949336 714589091 604467864 812210219 838581771 325527222 707649739 846448045 6831637 175653537 879451147 427628820 620916863 356965648 821486162 909032555 234739000 708663919 564607380 942004377 702912950 780193210 460870684 668310402 778789738 236120847 33135039 548250039 922479031 826792507 469312449 527968427 841079660 378573108 851173525 43368647 746620344 500708858 399891481 771520814 747593616 460449691 761271286 685526077 903509832 378372737 701354200 969405346 160623348 992872447 798074250 600026220 607770091 530979701 432249715 893061817 948299025 274288323 104637191 10164005 441077546 570344876 923579961 516288490 39419506 877729337 127404942 185567135 552429025 910862934 472203679 103489971 358302854 454868219 645731611 626749578 540648354 550784965 789530458 64928659 339123729 219781578 345147935 16253699 494149908 322250013 575551204 824966558 916441598 227635711 236071172 531512207 591939887 29573281 199142120 57056261 401267594 596482524 157065525 638690647 396789138 760370601 906058557 582352454 764536397 600334163 100076084 984404797 362793754 459235925 739163022 35092942 957659959 805768085 569172256 61480294 207019213 231684495 838238288 85777215 430674664 793636040 911981339 62928297 926692678 530064459 355677469 917615291 300974178 395166610 234326344 181046801 418378601 578109100 175156001 264385314 967108157 894341790 500663468 278318761 626083473 833538883 46874687 222679432 444431523 580411127 391451208 875611841 707657593 666541694 288305616 263546499 755531275 606932311 515270008 471865193 467474839 379160648 98669652 845294988 570493419 865819417 475957254 859732784 420415742 957107175 521974078 786223055 786576522 965743897 974180295 543777990 942077304 49206426 150691533 351214823 989655348 139224286 715205798 973035404 809512208 474971438 803397766 900492667 33174476 397830847 435441775 474580243 692205732 639314855 901929382 576765108 404591715 820314905 267050837 368902589 116278628 473715470 687201976 100199398 982920698 679993947 381190572 430592970 947784616 829043996 132030895 215638149 197257556 709766624 10910331 20054469 835740727 373921386 480523809 582969006 538774438 597501547 502401836 310480202 357839572 720914589 582447825 776526530 597052059 832361814 12807990 921943214 995685724 486758285 370845401 677232927 556311004 617788000 383652319 204755599 834937005 815298860 511275513 686455941 33867241 840405175 116115442 726730231 610682792 948354755 794627331 997978558 576894394 388968641 203142113 125460903 263878203 154629617 536979339 831425666 753164160 795926384 262817479 84523980 48449824 920131459 949180990 765384951 203064035 6766372 904518721 49438158 958047344 749353575 387263554 142010072 929399982 966634291 42078113 322806073 967209549 427578087 470741579 641416134 753687998 280060479 686748796 710801093 783275114 714166058 61595810 436737124 467967765 60624225 460837262 79194812 940713127 669026844 362849522 76901101 977388480 170250075 343788383 703459169 246768397 361287680 923484785 722722953 233677187 873592197 174333471 339953376 139961761 834307449 887734907 408374168 103038277 276490576 997910650 544683090 501595516 95830662 501531279 217996219 804620984 187712357 881929200 772874206 835503945 813778805 174591634 57692252 866972084 819827027 987435849 148056377 223405204 728634695 288005475 160590358 147684014 717155232 411378433 762828184 968704277 57133038 867484870 120907917 927763177 740434394 620565187 301149930 742724516 794739894 101055299 23414632 568882478 441046786 885628402 847019602 736137926 477836567 448791918 976785648 104839818 75731926 966737555 305850966 170396317 614163865 815699724 501763373 737401255 219608713 353857563 850855572 20920660 784456019 959120341 433350633 638602059 367466663 582999808 997727411 188813773 577297287 465801585 105318130 60255025 973541712 247874694 18064587 681160725 505466400 49038550 788316266 621005571 970057068 141523798 80088552 54249702 849617070 654405210 23881340 804249113 94651659 383938905 526649883 942635988 762166400 640598839 13428537 668852899 68876253 903842566 395953690 215023357 838249931 48150783 363962780 674587504 903608604 426338977 103839763 555186011 959536777 523010875 960364018 473826853 348326988 556555516 265145150 657124783 470355024 208010152 538603519 967126084 380502414 735654641 53628784 527481956 681741087 378383164 240388945 241584237 697613449 198420491 761021485 952291229 563029804 713328816 730597557 706244878 938397019 204506360 926160712 968538353 410131634 518074785 834135073 607571012 546034410 292198604 220127946 510078800 552347452 22840794 518180477 285967042 500881817 65327746 494868271 688866747 220396505 395937979 51692764 397000267 975993949 165218854 717411456 215675829 323046874 697639727 14168937 946825285 242065283 727182411 920364536 621234143 11328847 928332572 185415826 210931105 868044193 308236746 783405680 61424709 315232426 102648954 392847449 774200631 817467967 147666426 772415495 800787532 256634273 225984211 17719361 267125797 181890735 779336079 388004079 131673701 151764842 847379120 47528150 259305746 105434498 912970091 512518121 189499042 815423439 462067077 410396847 475366080 266296445 571235142 569209646 638610368 849223023 287463112 789841267 688359597 458891731 675455642 600897820 662643073 118952574 13303515 826063825 463208220 310926126 355559070 34282773 849638261 514677763 710856394 89571968 893518445 64491894 344126991 710907182 506263479 73341486 600220950 460284690 402961124 832684580 134831331 433683288 271510310 703428764 5191587 262030280 474043255 179020400 9393582 518086508 572154654 337501715 906572117 24022747 629497160 811469858 650547647 253815762 10011418 910799383 901513376 598535920 789449729 684722588 85680546 213544104 101521982 722977998 955712451 183789579 663161278 347114988 145761769 413346950 534025693 479139830 496860207 807480599 262926446 987051971 481638073 792266134 299544631 942085254 300725555 759803302 998424166 46878957 565380740 444827014 793665825 508665293 357068431 36156555 794304030 283601974 757605833 435195298 750240984 61146830 280552002 277518142 803624789 288854220 193140621 856230778 954793235 476708497 294281033 177009946 32015422 316548649 965227750 142989466 9692856 45239017 761041990 297884870 735526184 643339786 920023021 648307414 703495097 251883155 733252986 267828650 318954026 717435361 695499403 238111444 11033456 281928578 483771215 72940636 298161912 623359020 150212309 103534966 889308182 839278883 601293770 357469418 533816732 967842125 479562099 477301752 400630491 789005396 722405786 889646587 186024290 128128990 632664891 509616876 210525964 480185726 450320415 224780537 866028639 181053434 448704360 500441125 633605798 195268753 379576004 526922359 597444280 104328742 303182248 5531795 478433700 482494607 251497767 9851796 209579032 823152497 495655004 725419335 120637187 209438437 412583642 276662248 447442359 102204760 82907404 788192674 367385802 248395999 42818544 427041990 242775366 600965890 89112982 805777421 448507805 489304200 340525599 729321632 113066956 914253397 547388302 466248796 539155139 999435530 330060616 213137882 413657198 329524068 942826153 849793993 153210611 428949041 941619183 244235117 325209965 238163775 304755708 506280322 584103107 655419771 383613399 48202499 627784896 989427803 777495305 102904238 380384384 292415039 810462102 910393065 474608189 169504984 590541218 22481308 103363046 857509958 997855500 528230611 767313972 972733913 664054804 285721828 20613298 543203970 11633365 34186151 1504668 44798447 326626398 443710093 230388291 101685982 472088107 653601917 578502460 750969935 955551452 564107107 26504895 793316985 633621814 990112042 42883451 312980254 383436213 190476699 372074677 337730751 150766493 422107196 737780539 252050252 957585608 717279616 662123707 869563938 823170239 613432354 977764443 739726921 957521873 452218292 360255511 225770003 370061282 499025823 907923546 976775507 318569181 289698462 128509454 706490075 800990271 123275012 275080808 2969821 85913834 939794410 751772970 168697054 953038638 486175159 310895878 238194420 826817443 394988564 98172618 425423299 137135102 437508586 212301552 68898544 272266133 757571741 749251472 829249734 685334699 895962398 673928207 497476150 208310941 3989605 298940139 84470724 734402911 449022355 398640539 930131357 176429874 914847081 782748222 563878625 615204413 66531479 25702303 428091055 895565787 774712 639587092 887437454 841578093 203336495 247071674 880897829 666794004 104811029 232117513 952535345 552160702 694908754 578810570 343555987 593814208 788897889 305912043 830738507 107956607 702192826 358903712 602831740 613649873 997819496 429869564 603807922 601939973 308586573 970125877 498486908 458426678 79325168 392601406 531134011 603596052 90209367 271939692 752027032 805289676 223082792 205191866 303552528 779498787 726606163 992958418 951604795 235319898 628670747 189263704 593317625 450986419 849412617 196669284 868941831 771587529 514419964 580337663 573159631 7407042 563573084 207081510 407531919 791537703 727124536 172910663 204338179 551378919 487863451 696488159 21925773 365192018 797055857 779303255 299347062 620459787 548751490 52608024 956768648 183255803 43930673 589843866 91363643 19495318 850546296 22728636 605855832 579462361 439445018 755489567 174412008 450293194 917011856 143643627 899914822 692906557 190090335 678411939 443911026 200114933 903362565 260546733 108322477 321736602 681871589 135941483 822780821 898861364 90684961 80921554 406901067 732133719 375113125 53235411 586495142 155996960 204237424 445234244 481119463 6233895 598610626 176901428 987487856 550913524 229125884 715520736 297898552 762619018 220796911 467803011 708138548 589037303 665974482 398226881 770754002 718343539 299691963 454009914 655472274 380342115 463991468 717679838 733719296 869125481 869958015 248377903 841407469 876927274 367089268 694591944 379969189 930254776 319457583 656110492 201588393 317465934 68422564 886111501 704664124 495084203 843246845 246485798 796947638 950956233 314446069 567972841 63617392 615680120 948422734 718562768 846272981 295445374 771726851 118480940 730959170 805071803