8951 271708254 753730645 517775293 980407455 129262229 147369685 488509278 756343970 333469151 829990990 640239121 736126212 754361043 986436227 528229972 707337718 950479232 986269132 849455474 881115245 924475938 934534226 621708324 964311939 702090921 762551729 562583452 749256115 500222707 847402093 975569145 983601659 153833588 939934982 23157411 952990584 677724773 790768756 178653633 279384774 466594643 573798880 83442022 954438821 704360460 822310506 797825226 951578149 670166338 748520265 931875541 981052953 386204343 872587109 433108429 790036887 459139266 991218503 461104080 504287630 294000678 661567491 445037790 509953968 404119731 563459087 828316293 883075229 663436224 960014154 513396756 784390120 594274047 890521153 500996536 503566940 1 358292824 911477563 981758218 845262151 932895175 589635959 943596983 374814159 964383647 740998562 774864942 791788026 984760931 56832136 747066597 388972494 728002585 739816628 900986684 618279862 897670775 999700722 999960598 1 908509174 94721224 313737047 379945474 946555913 434058792 821079464 726557077 909722085 296805614 468569547 217822089 928103419 275846959 424537942 524076437 694025344 159467005 290989472 271532827 462473128 896325977 977957963 549729220 802083416 619502293 742941078 395097145 867524120 697911660 845353321 42010204 118454634 581095572 932566639 657617145 782724097 101337446 616282853 384436991 439936294 680250988 962923502 153493173 573089880 2920198 220340155 252901707 278140128 369532200 615730423 770652089 992263664 893578115 922155021 133977086 651242794 327907500 758828064 944433633 982030504 604225786 797225180 103506313 971852368 704823555 916356109 606630988 735735231 78830227 102130298 69604513 933992879 709663642 964330390 499447814 915761006 539932053 997076089 681982162 959085822 769059898 987518948 966108332 970475621 626081491 829691599 228773557 754350183 412011958 899155755 134458557 418999834 780604251 829205896 343217411 500461587 975398722 991159852 668813135 890098251 307216686 695931727 54650417 276499014 981207240 990722806 616312608 871235075 162881166 708175252 152130444 855161345 373303314 494261269 122905591 525154213 385104133 641239739 399530008 457081719 803343009 898807202 340201060 736973186 886556706 947926523 276542390 606546273 692404645 726455964 330003302 703902527 798671130 859870201 347846083 888604555 545919955 845584940 748131714 789469383 223830280 868467768 613300146 869176866 753837375 824864264 478626582 606163765 595693517 835264649 976787811 988298809 433149559 857884277 597776985 647915011 495516484 777340075 313737807 568694946 209831551 257289133 619787501 918268014 111542952 355423706 627726744 797987963 487388778 610065943 242953334 468642264 508457874 606665245 541973481 637520228 964314328 976744165 836177559 907366792 961268030 964575678 477938869 708337602 271499666 834013757 131837548 398878522 861876191 983171606 400344540 977753857 630412034 714899521 112885910 124344318 684710356 757496641 163917538 413844483 135373598 699560189 741294396 928673675 664539012 888657146 955197403 969184730 872756349 985583355 123850908 751557715 868637261 941313361 560554171 934247599 664280164 875410075 838860537 882526265 957355190 980798814 426647260 743010874 377085361 853454992 727986120 875161008 773663823 922586628 57003309 587093889 659743738 703899241 480960394 721405719 636965457 820458390 192355152 616456836 56119050 812484656 810071563 841143056 191017209 574421649 372358484 750292265 738073310 922825864 914420127 979212660 345433358 625256791 276956892 764009940 76555876 383971258 497071241 530931871 846743953 991618830 714123098 760645734 539915192 894135609 676963632 935920249 181017236 914809959 535884190 766072954 251705961 398782512 427268597 907692706 30874826 777823446 168300236 624504859 495038131 548567467 535832055 552235893 110744138 141972462 620227375 834288510 206445346 834431514 610208998 761682650 637806251 731333357 980694143 985633821 569168459 650762664 855045431 994501026 330810683 838858773 499277487 708046636 280598064 832624672 529507347 542443371 393441924 824982722 383433906 450186246 978390657 985120605 654255480 747254817 237481648 965933666 164957082 243267834 258747134 375598564 312528953 564739212 259233222 526524340 507422181 948753722 537509403 656184137 5784003 509963924 543948397 862008922 515785725 853128137 950054054 999801381 55094998 907767441 420307965 495003907 468691780 688468696 731168454 754918408 743631379 955687905 630711855 696200416 510550877 719679886 474120520 666125234 829595929 965954745 692003723 900899296 750940742 755924203 913080707 917365327 800115348 873776177 816347227 835172678 925613847 984017925 171993988 919783125 238494019 610858744 437233541 764854299 128347354 194859771 287962217 746585636 163073947 407838444 660508466 896193682 404535568 684878393 921286820 965819046 466206526 939469082 790137481 954859361 918201649 923823446 628760857 720633861 230022073 434873973 960355658 980072872 32656466 672079148 870200491 958666348 577260369 603883831 238997564 688112082 571090760 904025174 130270716 724517457 359257202 425255643 699160029 744912404 975161733 978079367 812155997 834189010 412318863 551144494 857881007 983139605 588906689 992965513 858245080 908012888 396884867 827031666 274831733 419888684 939709378 946352934 375826677 788835417 766353913 897492343 95893582 620401616 107486313 504847669 523476107 862167809 218476903 368410669 817328535 923600181 879466586 880976390 830974795 904019589 260271051 528179701 607614698 765604741 968222293 972604427 733566413 748573652 54381644 231842281 110901391 706753722 165278107 738707295 63926024 267690106 556507353 651876718 199938173 638530871 829576028 949664686 833449657 971675340 654847625 959613838 344623805 766942193 190056209 441368859 249319603 713583916 358916507 968230739 659960322 837153315 481856664 818834077 212440915 700207141 526125315 825520336 512722798 784019162 517492266 695317058 303071719 625979326 894803452 969018784 799723041 924690138 151254388 859096329 71771562 350440217 937334398 946263286 284490323 788970362 352757393 367724626 247243182 680809933 926001233 984312242 342660547 359989815 663715005 928210151 947172765 983889550 28091572 739853119 294019412 775934395 800463528 969195677 738542265 814077704 485013525 729496098 319284136 640860519 204583140 375080955 961639635 968215697 540777890 628817188 680761829 743471209 303764473 872500567 795044699 905285386 292248373 879618648 25588949 575124618 262945363 987287666 287542419 332348965 701916399 891113824 613072102 949078898 586106443 652706787 279284676 521678649 478884561 789832523 213635470 827674665 785663863 837355852 872556704 964858238 732816858 803546393 175840624 509476192 595699557 992234410 563371932 587066775 104299515 193342662 590550774 880568156 523099594 790362368 189448001 472968581 680704295 954424224 673892162 867075499 121972011 664014222 76520845 807813309 613155259 630179060 281354075 444553984 513062723 569635863 371737874 663505290 414575009 511074146 40230005 308457283 738191565 932085463 819126905 873330214 866273023 934059417 927059600 940357157 970646779 972312281 412302286 841601996 616124667 884417005 254873206 535533926 506427477 820640834 93845343 830272245 424119083 728601560 483939790 874606803 583731653 619518541 631953831 924759527 626826656 920357348 551140943 729752254 487688771 672727564 528264373 788185265 337571110 969308664 863608026 930053168 242813418 776404371 581208350 925285681 701781131 941069496 667865257 813799899 387374712 401108852 964854771 980670610 659753781 979538406 579184637 619213390 654108525 684789178 12911116 681272930 581063801 915892335 190908805 249858623 54183882 649685890 526100023 688585801 269978249 681057104 313948654 653856067 303402645 476595444 866684011 991773301 646815819 841058027 102576482 535708587 956746923 984561099 849555956 911783540 941789248 944345486 350494089 891400641 101177709 476593583 629309689 714666166 423943442 757320836 972818323 996995534 649359998 785202771 438516709 484902671 452268974 954108918 586757730 973089287 53688394 83310530 148573171 223571379 197578175 792196592 985078121 991352983 551066552 926295507 179971171 479808227 27206246 679272422 155290239 504939004 904417862 933837405 934039562 983642602 712859527 956477477 380967119 934589473 4890922 812278859 801088405 904508396 212439126 542310399 654574509 746702694 319115127 528813874 883023412 993157078 396059396 841707006 688687436 790308737 793264597 978636547 827907032 960069963 794813351 863539198 316474071 363287840 291156209 970183194 387673098 410978727 124000824 317469078 595245327 879867948 702267794 985573956 79301846 955041376 707609099 795204694 129043949 836773602 159434104 160064521 936180012 974937176 807852969 912231312 482679506 741527423 199916973 524002577 923265092 973820134 662773365 915571464 440501536 545201721 1 741613879 920935554 971929738 99943472 546124931 631539957 831520595 171178304 285650388 993370417 995154076 546973441 827496062 231481424 519105056 588837654 706590555 781463095 988260651 230468287 892197102 650344277 804241520 711978847 803917976 871681707 919683777 647789061 945196262 489976061 912285251 947420904 979625380 93595854 225112154 761983304 779387598 384198920 722034122 961738298 975246298 25567920 246076081 594571343 783483394 248209820 870468829 572808288 642527965 767780121 972984523 381504211 687924352 440855003 629421692 347486745 538883496 230557002 952127857 242036900 910624248 954572975 976067129 642482562 695418475 155727484 743101603 953648261 983934307 534127777 630879757 181831003 462839385 965814055 969468450 740800066 865589604 559986819 821915434 744019145 847709856 781975149 985976213 951676422 965952669 300721023 464364520 557291542 633370535 981134929 981898165 993677024 996805560 766827196 900144925 694055908 916152271 981646439 996233433 459298346 993125808 153362240 897074257 61695326 256301809 391121531 929014001 955621404 975445636 429188169 508940276 952006006 983731195 285369059 890859423 294169706 806291206 387686376 551005190 50036390 216496730 184594588 962948294 588945047 886806036 884735132 939609032 751373702 903001556 777819744 896718292 467690404 972140427 56946208 277179604 682301419 686209640 183926384 512781798 935785920 997939308 846207644 895301796 442619217 764717086 457450155 501823483 768164377 812374537 898315741 927952831 103857435 176742035 888642767 907702587 656692805 999427865 401851689 861041310 465857259 498366599 801568083 808187786 456270846 809976431 689939319 934035751 331211567 617895577 691153105 840102760 603395579 754714748 673036851 869906812 215892909 572952606 546949083 800622045 517906878 730066176 129528807 480222192 613622345 971396293 883107329 943279652 496635286 598096827 723142539 985023906 205880109 372405391 515146660 637916994 970737663 985895700 418850040 433342395 695092822 939025695 322562148 449134429 845983773 888809537 165763888 875092840 798374250 969497401 746976583 803008389 915552697 978096529 140270940 749767744 664314006 998209939 571932178 732994861 578283203 884361405 43325209 897422065 98966900 312251113 485998100 670925795 847145637 899941079 750302133 754633280 696562444 983070250 174022856 571541621 837938886 980861026 717254513 867204712 898406459 929468817 525594078 712620496 273413867 889996522 270608196 962598448 564001562 564732048 173068287 306953480 363437333 660153067 546815709 637932721 759332873 994919738 589421481 817715140 678441323 984506153 933988039 959343089 619199709 713807880 507440726 960388435 325729155 794513215 210722822 491598679 706442505 707867186 976089725 978729764 556496809 814461966 557582352 851044993 519265684 927338441 640222265 697395492 634872627 736675451 685269584 831001295 332687331 776946775 236814659 326494687 230815060 923282638 203189318 320108862 692931872 884490582 931416536 982223823 671165845 824217196 904701096 935251778 537791041 850239270 636378247 995313985 66367520 259272336 790855689 890909157 943410239 970560415 955756839 979608825 164173271 164973543 521215989 639232747 781332917 869650915 287748129 607295859 918341484 989030965 749748716 787323591 33982572 182831371 821297078 873285692 712432501 859797725 267561315 783705048 792995008 897063962 295108975 766998037 318931218 694879724 894603885 899719871 162981589 583401243 795534020 879356862 538025034 623323032 345195602 345255603 132016868 789288173 129708079 428296962 686790246 731430015 679716335 825242133 766918992 808651926 823845154 949709606 131811202 564869447 175183961 531412660 404552016 768032779 649121009 877265201 771906854 803046146 387714744 723162401 97141451 215565371 71464323 125154428 587835289 711442691 378452086 665771287 892349123 959782730 247835228 689990986 773706023 976715033 379173332 891667511 131309847 531961434 237921313 384076363 886688458 935131833 787124655 952105757 534674285 625651990 172352055 241678447 228205759 488110983 198359545 416401104 378740519 670381198 127547711 981046058 36448492 537516058 254551634 266023583 754947346 988894751 986231038 990191031 516597802 560463808 563597451 970408140 309023846 680425293 899255019 964368289 10715216 73414573 406255396 852478294 120979330 546809714 158686688 164084769 179053685 640185281 266139870 309660910 81768413 880590862 335783965 612381109 765878569 842455041 106496631 321533435 820829259 925332799 720085434 943567382 886811433 963853719 196224423 229030093 765876046 976675034 263625548 893754045 570186020 996843315 916950243 919767462 517968524 710074329 899165190 911070397 420153891 690111684 210666990 646941161 389392727 594516183 346938029 373097902 304856542 480350879 469560544 696489668 285593339 859887374 513296510 934034839 183087979 901552222 398132275 637422287 680129150 728280474 440880962 804673759 861193831 948106778 140886436 871820167 921085952 985769464 847878372 939288997 894944178 997126837 512751154 525061516 677063907 843625266 6827868 517663625 827555180 920289620 608633908 667524558 681642728 906985614 1 136632143 538147534 632042543 232131150 473390388 365159416 604334759 272054455 501099843 392826977 747417176 383999749 552976701 940355180 998097703 903492285 956851437 71464172 393871321 452689556 845504482 779210332 797104314 473888899 517344032 351976314 692326902 894481242 921259224 414683007 995177907 146183975 444735719 354728136 999974005 870833599 937190908 814043639 854707291 106186374 894195742 371284518 703074309 427537951 715935873 674404924 705801107 6416580 588873917 459185578 502991414 54668268 463393283 49198958 504728208 955036394 961176685 189873968 212081777 379550249 536991425 991505269 998109354 553294359 600601161 761348502 820506573 810699114 861737137 538573743 701680278 36141424 37257043 691842421 715433298 260368581 741071641 240335522 860368823 824137729 953674884 533245217 544889474 56360664 99582332 336290300 623735364 405016784 545357139 975300790 993181516 519550906 597340254 35162010 880915234 132860506 745604850 69439892 508789203 61480571 87777859 459158992 696266015 32084247 79237192 15340951 626137539 600929634 632943245 227267041 902161865 877035533 905067782 985360638 988530474 6851872 18414872 501014123 735238401 168487153 713433687 189433499 374449616 1 228281884 347005936 394127893 122985253 688770694 763491798 886122270 640730681 714013960 539466877 941110075 759085470 814210016 424437779 985624530 954787627 999650596 514346854 669099870 37733183 892872769 829475762 950051653 502774440 935205561 627616570 647724980 707120448 744334544 92740628 756555560 692724849 999015266 511654906 668836233 640627848 979500024 901747228 975976248 289574546 787417697 334125630 630544468 602412460 991132582 973506221 986444254 173618083 190866143 916103360 916160646 483245282 761295820 767287042 825898245 393801610 779330839 202095207 809993555 11563430 631799451 239310109 961938256 921640691 992934641 498363335 680575110 204376502 373748965 131910413 577382092 480540033 521593630 710135649 874370547 38099112 744844283 250884177 904384589 949797509 989449997 944426290 975183124 75149689 923985160 615533624 826398049 544544861 953305587 196383352 750460673 831428924 950657603 5654218 772238235 910934894 929469931 961485225 982226747 181380462 775060281 827534453 956058392 497807460 901260018 814352086 989109839 747915678 899812464 139440988 456297483 459415106 463311248 562991850 816622490 360227640 363460999 789933297 981472399 617140696 995388059 6635209 751607065 334136032 416602211 932064401 938339000 65082185 656886614 50604364 52811107 332596516 564497657 548771611 774161731 546115142 726729313 609133857 659835006 820813317 964191758 417120092 446427415 735261513 865963676 271668719 754719740 356672479 719122735 824703603 978704830 999405077 999733242 383572203 652643748 213646796 825652295 749713646 785431939 51512075 815257167 714982301 724112720 410479609 469908761 127951514 141491948 552409857 573890871 713009770 781651233 923048540 974626844 931577764 932516386 14816602 876782605 73408594 660481366 77543555 188306200 493021758 658520689 91810256 463622655 806832176 947150582 271241540 450223517 530867308 995857802 814196454 851260027 4862636 26238444 303971914 518028074 672096183 812120184 60652830 245234956 373146447 675498202 799980842 883952216 328992062 532915699 185373438 838078952 802483096 954248785 869961755 925615682 944860354 967671843 165554540 409244659 775591472 779950155 535252291 756695957 201902625 441250431 819138313 845280443 455698488 980206798 863596266 945661930 984962040 990096275 221647868 529577235 680504276 999639779 396217985 703853653 828405183 890058916 65631903 881897722 517776720 807174110 597286217 902161275 180606026 229101016 902492804 984998859 985359974 999071661 779215653 966310871 676370780 707135118 727831646 825052454 78880459 697610818 315568115 536419665 941537297 947296199 867481035 981153035 633907919 735780322 556814665 760447302 430580930 813285768 314842263 686234486 718967507 771134143 690780894 783444452 400552239 475901194 584926445 920400836 426200328 441885775 888747523 958507711 584527445 635322287 774895023 897607090 12962464 196799995 369089747 472192397 336649455 776134744 637600499 713009055 168972205 327728004 119553838 481345203 993204897 995276897 516638024 618036342 511224779 733287888 996539572 999356823 402934594 996809994 41200055 449652136 371853576 482633802 464023266 923752430 110522635 175109143 403365304 992483261 751259744 894677984 187181187 238254070 781121986 794931310 153705157 959338692 179367953 939983196 791313691 839986580 200122949 644427228 355749611 889359196 215567157 452537161 301030150 401175401 587151079 649878711 382254957 479220661 707396039 861417641 462682670 929898070 463840362 730293473 837769211 990959037 437020887 783072929 777872176 996313725 751453868 821356218 213788893 622395219 281933137 730722018 92243503 193837072 307983523 914464501 912382078 928785679 980483843 994805336 653550281 853276612 572953198 965559603 493240524 819114478 299979012 419082310 994058424 995277122 900816144 925538654 345954914 812060858 570626401 650451022 459643176 877096426 1 601884642 253979408 789258534 538567807 753316577 501559101 982175028 168487572 377448769 687538262 701683952 857089677 958475470 929776762 979742213 758917449 905467774 753423936 955522150 965381610 971363690 861113316 867171941 716827868 944779387 532258073 919155357 400345670 856097020 845672460 909729389 182007254 442793661 272909457 548736123 558879416 872855023 139236080 324602740 908682898 960622353 557106859 795132505 477605689 936263612 832969782 867649448 161882685 280053526 241985503 553468651 588700625 897001870 185955988 676229444 28308337 545020093 70149121 477436071 341704971 698349714 620676870 930552352 632042284 662717556 737045622 944317790 966519737 984860429 21562152 820053015 499050642 696543598 88207397 592831413 995076056 998439958 66855293 831746733 269378405 634597803 675612307 895782973 827876370 969660458 311545550 375151735 130343431 667622313 920979776 926399568 924104742 998313928 110032165 567983884 176651452 190287219 73893104 701042379 297313107 708697645 787172359 845595668 262484775 279615374 588498407 614049096 560074184 579708958 197817316 882441313 590039360 769024927 30680675 331248326 878055219 966695399 865127088 985359843 516970973 922839320 445875232 955556089 348095914 437589087 189644893 198196542 222373805 365027242 7847543 618739531 106718248 187357449 185373371 806430972 51855356 339931035 27211481 720905260 933737357 938300554 472671085 618610031 339217377 998235399 743598934 923513143 977180875 992622669 272864536 311753593 34903848 404315812 125349221 191373659 26312348 339878403 757949097 905945066 386363911 795555626 107026753 389115071 717732937 890173719 353942561 524501563 297138227 368407933 159426149 197260582 929737917 933733477 832900331 979696775 342782510 848243917 865611965 892303762 982681142 994258472 829574264 907157252 498115236 680684255 961552560 990668961 825738311 993985533 881128472 996510472 753483945 766980271 551648340 912281895 324015787 897621643 358950112 775189048 750306299 929639413 554780695 709672668 998589699 999739650 643004700 694276993 830457153 900432740 910990994 920217332 737358550 914670736 512776959 661512024 372595952 594133600 784050692 821604650 103765661 309294324 425044164 988322987 913753736 916046667 666317353 816051435 150675638 845930119 949890759 984523926 153369110 888084376 1 583560666 27237914 52828292 881511176 934891171 709152582 759198942 181283852 740082956 907768320 944024818 538625410 823072443 4839669 221863586 742127325 938864670 99876809 765033674 147418348 364631281 430492191 488313594 537908324 680569422 853659202 880527190 515456171 847879627 566866247 936973283 91863029 122456199 189152332 822562299 574187616 763648618 575208897 904183239 673559045 855500514 833028197 837117421 890297851 923818489 712221649 902259583 271593212 849805755 977305810 996539138 753902088 993933802 195467278 849153869 615400730 618439180 322186564 722000799 351664040 841572409 677128414 680679531 742330006 839554222 283242216 850802745 474866421 817233281 766124 248123920 809447884 973196682 369722535 828078577 333668739 899174983 290673540 311742529 154983513 311054566 164201248 843123184 299784376 588461990 203655955 695523974 160745941 872611084 950330108 965719876 661938824 986139915 858863612 908492951 86710929 923818630 250519796 284687093 702229867 828037993 865191591 957613143 582556683 868605855 217110517 374547019 725475328 924335102 587043261 892599097 122338289 506608517 789572175 846444341 941277711 947447438 91598789 339812625 889484769 973709072 785030076 981174816 986825529 992304159 525632507 953927019 483833131 907488713 503930260 870538514 600402066 601993679 449657677 893784390 170017766 357049522 688783189 760801149 777451322 983767541 496415839 914326639 682445103 917637669 64243465 775153436 388948664 597482139 616521982 724354734 682068958 988605458 163226643 596765033 672527959 675424533 323285016 505159442 569820610 628236104 854090186 995163996 734340309 803715414 823800068 894318389 941089892 957908617 275018082 586837413 703707277 757444826 532215422 783430830 322061214 445944636 751069074 862854332 725884958 828336549 542649306 666170799 98959269 207326385 259584862 514562271 478258712 942054357 197397893 462159586 973065807 995087378 520877143 885947350 11535449 775446308 845867424 948593315 516224157 801604659 271127395 459115451 179659195 988046176 669551046 882033477 355207446 706809362 832905688 908913285 87893391 866431951 488885040 802250760 58557380 768033285 796280433 923334104 480386813 585806815 228014354 438345486 366778396 455798461 767720365 920483617 42466609 157585055 181092053 693886550 726402399 767078735 953629118 988721014 841796342 857614729 708685727 866571962 633817760 822020931 93109112 777893896 646198227 835997218 279472365 575784736 286873703 612292649 214945535 856128619 444599107 563369490 610495548 700892866 521912255 540552397 445255875 809288998 280768260 745038887 129492039 435162797 366132405 992323562 996166397 997609794 336660640 618101053 1 947151360 798742900 817045325 76424175 937756021 507733896 775214754 543209677 982095566 375197761 730856096 372809370 728029458 573637395 716098431 844946796 973017214 493247570 803546664 375533510 506596994 167978613 265425658 333240667 753511309 26412712 869222731 41872526 707619200 283476431 799125606 576874590 602693138 709462857 928078815 943656391 995232215 402412036 406090436 841406770 992853104 211722417 537128707 578342601 831839016 161205062 846643652 177736928 915611184 481925429 687469456 907632591 934259495 598323078 777374176 328530969 991280739 36175215 411858862 404965564 805551120 162529855 233134743 193896973 285641078 274377449 912627371 148063266 981462144 296976561 930354351 709006072 892181014 808584525 884140624 804050826 970124493 818756810 838111632 688092177 994032292 934357523 964261184 719792603 808383037 631747904 869065440 382144552 749813435 800873581 956943378 179272255 307898365 357607338 830994771 791938381 992500154 496246759 983405393 764182409 793049809 691205548 804936930 763611650 774300020 700119023 911975464 46430648 333966153 644075102 781110154 716754641 991297350 490291 175885918 1 141151604 242118751 503600143 173004846 629672910 372969337 985866793 312130883 450524642 835503958 939765863 449147219 900269353 104971086 955862485 427545256 628274504 155857668 826995174 741539140 778058414 619519097 795493589 506065056 747793031 418387939 484172469 670584859 721846863 202073348 919206537 572419152 658839119 318147586 959692206 205109821 888212072 285824862 483103880 291737115 618014852 637507748 822555893 746253993 751268624 462124850 980648307 74562978 676973860 693151705 938188134 721754791 774476110 351284867 575704790 468442101 618040349 273131561 697492616 885060598 975210402 593619745 819354572 741687404 852094045 977539655 998075435 516135676 936727509 671020479 797220451 149746544 632921596 713384291 731001499 249622393 734802687 235551422 383284940 308721149 532141670 768467604 868522189 954088836 957128191 433752780 758715459 883872489 901664088 62839273 585930623 492733802 986854778 93955321 874379531 83392927 407237432 699764191 856912578 564046840 654530348 455043449 616799570 121174904 431398941 917551974 935714637 448041729 613250414 689680062 859203898 920329832 953475546 519430784 684034188 140611052 703674557 73727064 115118580 816264018 936920093 795492196 844070667 649081511 786706184 601723536 632114527 436775858 700735012 367141925 511190929 95462868 738792877 59687230 722048506 375675905 525905461 807247505 955067066 995263532 996106634 265651456 754052487 364283062 460738944 589514713 891207608 1 668067948 552843069 919908945 393693681 576947443 123852127 393027764 198778982 374356996 273497426 527735441 258133748 668543121 878345791 986407382 678827726 942483086 774179878 950333637 389311836 564088729 911794530 931433745 943718181 966795915 94297900 785561100 100395270 987134727 456916673 983600381 696501664 921688133 818235674 930852583 678505933 957886163 516860371 701007506 869943603 994052372 750639550 862249241 260208470 630671303 410220689 850128403 44921353 292132139 614081101 998592684 493913077 928281293 660334032 966417869 496251786 995521847 56369727 589504047 516024067 915761005 731220739 815910388 197981814 739802662 756404820 949983207 128996723 747059399 933731402 958482619 124577421 168507728 407800222 805881407 292684590 491677093 348638450 730187695 152719858 352488164 731788292 996098160 439929001 544555578 464606693 945545077 431084513 939954423 451400981 957272332 435765030 891906782 706289741 828465206 1 667565896 700734250 803561329 451560665 766164019 442798102 720044679 656458946 806599102 757632534 842434645 610253709 765631371 777331588 928824900 335395956 813620797 556085899 590048997 492185578 872204843 28614597 934194144 196352761 663609425 118120086 577545790 1 783097611 786850534 976325655 302619079 778019725 267454474 467100446 378146601 550935270 294480465 885760649 384154541 669772862 113580423 722575090 767257526 927444024 614382408 906347658 723603423 933550618 526272029 829045312 771060382 866412108 900268504 948937166 948350017 950741061 898347727 953231629 972747860 994299210 182518918 435372885 110851209 158946960 180497244 214907118 634064306 728322183 925146482 986254010 813313348 976033262 691458618 800817714 237075815 735779469 737761244 806686299 598710490 672247115 706240462 906643589 395390626 547462643 556931146 740880425 557162688 664139245 404707356 455002363 841983428 955415705 106709662 824621762 1 786862317 298344472 493889980 242803584 676166742 697555059 838439621 127684620 146054309 426690215 486366672 530722676 736231723 632313867 930745966 432860111 566689200 172062604 665622650 894893315 913711943 844773030 997043696 461470755 843828722 119581077 201466641 400603423 960293083 691887105 695513352 791406666 831802902 908765555 925615350 797139843 995929036 158433467 999707580 471914870 562567409 559420583 837693641 127946541 866823234 263604426 776551153 727905688 919627564 256631370 671372367 158154995 306910424 955037975 971709037 309739062 732773098 912885398 937741394 748194682 887699746 364911533 901836203 356902829 797217555 577611010 795815965 492850453 820741910 214301805 585257346 575448203 636207097 340378443 362661230 660242882 886571235 124779090 358839827 642701005 911255340 834089449 987351230 182139056 914894108 641273131 720346857 837988562 875551421 52267127 352611116 575923311 588293185 730319581 764647564 685629241 826710533 67636035 323203986 813010285 992817799 102948322 328956524 587897377 823302057 44916726 908673377 992769552 996265027 985405432 989953396 7851091 607792235 821389396 948902485 396211657 859213987 316848025 861282499 616174460 836074677 327987048 373790288 345048741 667300933 908849561 954641255 813918834 986979657 571658073 773371847 148759328 606366658 784013446 791134498 353598016 682561006 884157446 949536914 992623908 997862006 488791957 734954864 689500008 943600692 58023023 212738993 537655230 858935595 807164424 819370003 747241907 833412782 924991274 961497992 263862217 971416685 993279620 998514585 379162009 746458874 399997241 463028018 51208781 481860074 981421931 999985797 517390909 736190883 281276650 708262996 453466453 677461889 959129385 970186044 861961596 883140154 345847836 767124729 931195405 962778888 692395482 779251083 957316908 979682476 152979567 187606363 416958441 496744222 676828407 876170886 708309023 805021441 841473290 878323253 153235543 892346072 728300072 829837660 851783422 929795331 953076238 985593668 339836621 527609948 921000274 930299669 886224557 991365662 137104480 666174751 690925281 713571816 493123807 876119367 915011816 945177485 992207126 994625222 755192291 965009706 910856163 996997642 254633739 454386629 31034551 119091734 965850043 970624662 804908239 965510939 930635192 963903404 165232191 587804471 511064463 515602008 258661532 454080863 125754187 126959152 624804160 828501984 442686347 936079690 19570448 441584942 762925969 959238160 531349704 625408659 535421141 763513936 680771283 842658417 715060477 995568096 212225742 404076859 220180914 939911064 394511688 507747461 347602545 873449350 524922530 744095316 483349341 756880676 321111325 913475592 758028681 829574290 402721120 648845306 597005596 924700502 443243349 883725598 321973668 551073767 974041213 997829034 226859364 539765539 607789320 702007621 58322557 333747798 175258124 463493924 648292848 846814143 328629783 700313721 638584338 831332132 217488933 410072623 333109763 938716146 102421680 428142628 486145694 719962300 35523570 293182200 224902644 608355619 421367504 873992066 534952411 661385003 201904550 678754706 682019770 853514914 403396476 489590215 630374680 699207769 784504979 814331203 950457230 954861726 875579864 935611937 236409730 427529426 373876032 793445288 503134941 844458078 606539411 652763417 23519122 135507167 695526321 834146842 535151149 791159984 198774720 339810055 606874424 956298878 234346846 392153868 569929504 869519379 513000815 718906044 347974708 397425720 828426722 902039344 516737130 901314484 321594920 882257880 699672924 924688110 237642059 356658674 53060253 225801748 881659486 958924377 868008661 997597389 954179689 957917627 303964901 429739888 999259053 999387662 855391586 859461063 113556739 448807781 642638431 742277530 789922226 863604986 863560416 949405604 955753104 988216806 426621521 705102066 705543136 997038230 276297894 563959375 803269733 818383961 611023864 656005663 596250270 699337850 281021485 574981782 345398316 928684512 896250462 955164572 880014866 915793658 454024451 666934061 249757849 739015867 855219231 963073938 98519507 621645442 974401640 985760535 168963412 691769297 960362032 972913472 446672520 499903330 915438717 961407571 26479861 614444452 945544982 949696289 547063833 930579659 261987218 712861867 604089858 927903469 428550546 842068813 839848851 889573333 571148123 924475037 653729907 704251304 33589731 285524252 63466544 246646152 360823342 523430773 663421718 702480325 431942458 433124382 790183400 902851830 930950728 985665457 475374574 571407219 770174057 901698417 262457705 938219199 283026221 434958577 504405671 857540808 185114226 787607100 128979595 529668253 193665674 902514833 884063004 957485708 237503535 494303890 200252565 490599842 722561247 922334094 34563927 402169362 899839625 907935898 464414434 527216786 122295259 472539777 65181880 799021615 858660632 990962308 695722786 757129816 194949853 240006929 971823442 992130488 694175484 751722018 107399080 981174891 79384142 780106546 661892547 964685083 878843271 980131541 790444098 800924068 581521292 874443567 641294017 951351874 11097033 229233886 90736571 764776985 676952301 773225157 291670917 693830745 92509578 721663563 462237216 519713333 21401029 597916929 153974872 822697655 350369900 443753907 158712234 352999091 199831149 231645310 88408387 356691283 118879141 338961996 311519846 401892310 908764061 970933265 197805095 622019715 161182039 790970152 782058602 880548914 151489843 775536584 693492034 847486568 982957558 985940341 666542789 800338228 7799497 693915103 222325685 437853238 289966429 802318458 325248923 870239109 17277859 714258709 717389283 930138627 641084249 718629285 591217801 788903833 103251751 778478594 771043175 873665808 922290508 959635483 150488884 623803812 374108854 774658918 893366013 982896032 549123639 774218551 743405386 811110673 691039214 998769847 920117516 953657143 786289185 881033467 877496848 968174438 237376176 914798320 51447838 545698532 953284521 967685430 975744906 980068638 126644532 697733124 258677464 837768351 958079998 998661637 241257728 305711345 586471831 999040978 681389993 803305860 224767673 271910325 341712048 494870756 160587493 858911380 337621296 567423863 687479700 759939104 165993728 174952022 432113676 787474012 167804308 851964605 873478549 903959781 147297908 389796823 611370779 874650141 546143689 645492925 1 630657286 526448968 584066187 258984442 363972945 899866125 991371424 781450507 925126073 983685550 986296078 276941497 569401886 919888845 964939434 388408917 705619093 977010111 983191442 475685512 941053928 132762619 244541526 159259195 504060035 273636248 581685685 145514545 662203137 720495955 832557276 230043751 447505473 878262529 928457924 273245542 862757598 138008364 989546291 794341659 818864387 701346713 846762095 929299992 979428071 867814903 935843946 23823837 872632365 443652767 767734171 302390342 953022718 363538984 595247479 32637258 339090885 1 147322043 79849923 719177110 263341427 840661410 627767173 952027939 807292344 958427480 479020155 578465160 967599542 987521929 126273638 707494474 475109994 840558972 455283184 820632592 955066480 999387771 128374165 589212057 161460546 230439406 503005998 557787131 681389244 812617463 348289251 400579507 652081113 710475233 29796306 206287441 351344418 943696443 986477840 996873914 847312885 887669744 181113881 192684227 271979217 914638685 603245787 612120421 987506902 987663900 22329075 990094374 750427519 917407289 967596326 998080168 136065357 649094131 225951700 741582850 194836510 212697576 925407523 929117000 536410467 943854441 804811166 820559961 249404503 454388855 846232075 942966619 101379504 850295480 774757081 785225133 328685575 727194012 596148174 637691417 17109104 319477111 326737674 882368968 753821979 876814130 346037771 474424570 296736859 977492323 491772317 977914003 795721396 970068312 76167819 359486622 414064190 537350683 247290929 592086322 322635739 448492487 719553694 925428032 847102932 922523917 600784006 642282786 468353929 511047694 278064144 710168281 815187021 866511558 631839216 689585143 13543779 710241340 83606856 280554122 488446040 774132951 317483809 569809101 454426799 769605416 526206456 899175353 819997426 850954988 324306930 925652817 511035453 776806691 883974743 978117224 858539074 956707018 461950534 472486835 232213476 611059284 892841232 954251252 762078376 855085717 128448233 576156870 380675544 417095674 717932234 958222525 256647234 351554769 73396944 473310958 576389568 922055927 421156269 632086628 852248265 949851117 774762246 919355870 576966186 648100726 410846996 690988923 548356095 857269846 77596712 663168485 205724537 802263419 40568080 383143352 349773597 384449602 903702635 992397140 415726251 445957535 95598875 792021068 43304636 916293900 197455360 686663439 847266666 954241455 25312058 26318850 995969149 997117550 300098042 713095710 478867471 634392968 46388709 908593915 21077015 460520260 243919356 823821241 190125698 212634464 453404209 890329135 238532827 724461849 601213497 947227348 874622849 875486112 188744409 696327925 385036802 601566918 343604566 830277578 708540862 772567680 918090407 932921180 538378473 608420274 838910746 890611180 96175973 370457252 302954555 573491218 210803602 377151438 705965360 798183346 71390808 861136234 925353127 955890720 128474978 808186700 442756011 754943381 1 742779029 744837732 965917363 622400196 663212929 273794 285425219 906939936 923861673 502957110 534360774 59339189 909673916 255819450 838955533 242183045 726339166 619861100 708398304 653720155 854737268 3322572 361526708 833500304 970439400 45142415 876014442 59628790 197734981 615515590 769684527 383669622 786052022 669158797 822074380 97090709 825052672 810070077 969956897 318385405 445425135 202291618 580579922 934540938 973129128 28652618 696832084 574964387 764700185 724395809 767831437 961089104 989279456 328202707 785563329 220673808 922650903 188730067 552278922 862616443 918620555 90702121 134453477 939444436 970976660 750044777 921792364 850930636 878454743 921726651 976594075 741264870 980003266 254044313 985042970 384346693 493676857 49820436 699489851 14910974 947942276 986643353 989946976 547551251 757292543 803464061 902959847 801524231 913757406 293866183 633082203 195149062 961117613 567109872 715530709 621573301 692389482 500260773 733081643 532280287 568190136 826959246 884178633 282078366 367969490 672446758 908980710 590126124 683794743 645279910 936197611 452350845 791636525 29521842 697289881 396520394 589553940 184469316 685287490 999588242 999691127 328337857 925717406 497196737 637251437 528147684 558866245 635864611 674410991 222274628 554240734 52253060 367694569 466536954 899570362 990174130 991882545 762709969 867803764 863219596 903671993 886838180 996007238 858562922 893838114 441431789 721900227 110366984 419748924 752943635 938586468 295681310 907671020 778576886 862729742 723072085 940980030 159908989 420663130 535946432 580985214 532543796 579955990 622621210 782009231 826758240 998593396 769778 106408403 75517802 554024973 924924404 986657645 455450208 979181901 191756993 230991394 580640874 720874290 277174863 314174354 986675751 999391211 1 674285342 190251735 457574177 353352515 889218960 715748050 820776037 60841011 960301932 401962561 418497676 50202949 237908216 692471102 831258749 151705480 236034544 330953292 763073251 645843009 701426442 675020223 882155517 559880159 796440042 985715825 992881321 619738325 634575576 988415421 993867536 802468473 992760193 518203454 877365000 17205749 724832498 802629469 818302755 306679088 738531931 501550523 615063120 557648572 643464813 616993383 964387638 888352800 999753126 182499501 944020214 733994229 965199883 485015988 591083710 912087801 994287092 793667037 913035468 81576132 963396833 1 415079970 561737891 792837152 461662547 881217995 799097293 898384840 280423582 622877989 977592276 999780441 8054052 960618331 840438329 869019179 496884316 587539234 398856446 976134487 431294095 928349738 412996407 913520044 857882547 901799779 667455840 692576613 385904128 975107196 506332768 803538908 197771258 735624551 148689420 972289893 792666684 959743062 238045047 728967067 840019152 936624099 565531742 686094205 85739957 459207739 65163393 662165601 647978017 649127716 651812248 839993812 330710868 809857604 696200053 838060732 862490969 942407543 230233995 536592133 66842566 787411265 186899111 983224388 925424001 990935124 664601831 931391389 484570060 733897870 409328818 570271688 196259465 374940208 598644364 656790267 565196327 593553466 780964520 823827073 459867695 891846726 16100817 731006358 948728843 993892196 202206197 961026620 363068757 770467518 396214505 689508132 674488067 921562607 463921176 499208359 171101395 749760327 32723424 424137361 171785397 995025764 546086196 894504529 126217844 256130435 479906779 519043177 34378127 508397239 553243555 812208630 192921825 315881481 117545411 214679210 328614920 985562410 983242734 993449319 262560691 713226507 390223583 786743396 804107829 957430421 195095232 851655311 882444478 931594044 624642754 651193743 212059405 261335078 360407599 409576754 616183309 703425521 749814695 831041231 137828350 833962698 247626913 488009545 743706955 972844807 710689553 863187220 904333553 912192427 698648549 802976078 958676123 964222106 319950716 941317139 57939813 430397212 175469741 425605317 637769002 740130562 209580964 263360075 899185704 910151711 906755645 949013885 77996291 212684626 917657306 966807496 283056245 681637854 682652096 949768670 882514156 890223050 166828895 353264575 2242867 315021664 608615780 773574980 135743689 449339018 751920233 871673368 592573056 870661267 641320384 676798659 70417810 578158658 305952440 957670928 249305911 848955203 692554827 754985919 769265365 991598258 513666356 683485102 149544173 458198360 928494717 960517039 604004330 914462372 384786350 478517189 331392654 896390272 309111906 736384105 8741473 936072171 784350686 907444069 309383144 886605742 550021183 777168713 752066182 873646380 708535736 820177496 923551572 927182686 884951327 923684909 5698299 239050952 316788602 881676025 946339904 982181806 731322849 756125802 917175548 963225061 462803381 987100461 713548278 829541570 729855371 813487023 368420675 830365140 599866901 757020305 73525581 869339900 739120239 962202165 433978676 530747697 340627528 847174456 349914713 617033487 425366299 791948425 760602505 915928818 314799812 398261956 878892472 910445972 720894432 860570887 551802993 894966275 31372514 318787958 619470659 768628182 983267358 987042821 245208026 522954133 896761352 962639081 359785075 937442179 86061924 857148611 728642704 796663961 478406393 551780125 387258642 472221926 715226717 858925268 924224709 957291127 512114277 828474853 785790106 823459875 531506930 670786380 40979446 729979636 407753784 901292508 408073174 417086796 58191809 202190503 226660853 926345587 515884644 549285168 972203548 989998104 872105372 969318523 259512736 990337544 789816650 822803014 628999721 659763054 606811401 625886922 645097918 909058148 549278163 716482147 210015734 955276230 602255691 896845142 324532814 570999830 826200806 939222093 595612451 836532309 425170215 649796191 49286349 427255678 274927122 810595350 46557268 122236587 19573302 777421917 874611594 894857357 384134406 424366174 547178521 737254878 668521675 686537610 114698921 523311384 440260863 691176693 355439504 900188616 658480724 838094553 359991628 919811241 708999083 922158204 597647843 639406847 557016691 608531823 659650503 848120392 85818313 723381903 365617669 398602279 491804392 664347177 990920871 997106483 769264077 927190979 63796695 439714121 231273723 428018159 514722886 645668311 93862448 390818836 986943311 997129638 782704622 788609498 894288868 936621921 61180481 285215367 702767125 884347825 881422329 999325722 698455409 852694487 631734189 738682544 761740840 876251499 324100313 869097806 2135074 403833245 816824693 985150953 315012598 338099965 575488058 989955402 19529093 779170083 652503602 877106320 595526315 757806718 75665665 702029039 834525550 930564898 825829179 830199916 628278816 851076317 249078344 319138170 533735362 626434024 530519535 986596249 790958864 829021433 303011569 561628585 242811400 877182233 434823012 437689499 682381225 780461154 888485540 967885889 34468731 527453279 140866858 332740253 75637131 585809953 840604137 922090177 244813759 276098769 209057338 295521958 735270264 872369976 370904548 437581699 907699979 944727405 806803804 870623429 607524367 884092752 716143590 903804719 726768350 727520166 627609856 733656683 187363260 988026281 468213833 505526884 656033638 942887485 513140444 919269075 157224809 758578711 825516810 949871767 562734123 916872270 799117930 930503823 380293256 626200660 575763318 948107845 723371886 807404563 308706866 830974609 820883366 888628847 350834836 859038201 826560402 860360090 378901049 995599580 633149484 867260483 954604576 959475173 94873187 266613523 610358416 713936272 349637122 734236771 103636602 700770970 322409263 846854591 300488669 359056255 326004241 433120235 28244708 503047357 609820487 790616930 988466910 996164248 857521635 935002632 692969156 787270462 204753624 576122493 683660596 895994308 539636011 772602123 629682614 797074078 148901051 780471882 586848035 673820672 741352953 818360305 117808337 589677889 890326335 936230645 894412494 982012930 434784389 761224622 110400729 536944635 969774041 984597655 253114560 981254610 348570483 637074403 298975060 785706505 861386723 871523755 375709093 841495367 28856250 189990887 921869092 939739433 40202926 926838852 888735974 972546757 479294517 501813343 116501521 593092489 957766936 977974118 76049596 130288802 734124690 929870665 680189057 753071532 691833449 812295883 747459059 954614064 192236640 625404594 366916076 915280698 332545491 582108401 812066384 883550316 602053779 875012170 805665754 924019743 214506434 679997755 951564810 988432420 1 559449520 226130296 531710391 131704584 633601458 555338153 718321989 251347937 704760815 337139411 608137648 854188422 884890608 674795454 892539774 252663248 394781595 568906740 791207601 576015219 585210821 488354801 897709332 787296878 794521898 136721446 854765615 450834158 820119916 270944074 824985773 296526877 562547179 235988404 630697984 350546998 500292121 80671527 546265756 81202609 387824029 279575842 747177540 185188147 232333824 365337686 432218718 218546247 320323903 284365729 992006106 382738633 444628902 1 159521737 704402820 709769408 485391587 494296778 928482749 999930650 324379280 981173907 887830724 960828040 703008090 710692299 50088667 479998350 239667224 411171129 721855081 872256043 418409986 505569427 429393973 632923016 969835560 988031605 101760570 818516805 811033056 839818646 359729538 606485965 709180899 796925209 12608051 630292613 230946325 667775917 451710591 823968927 39275987 255925868 919877736 925440415 313616048 630173095 982904520 986035497 976542956 992662073 916045690 990903609 562019713 591290272 322886916 813430597 195134071 333481163 250076782 968089637 243863923 558895802 755013436 760597706 630426292 955641646 122985402 528198764 64513608 410837163 989262414 999346445 573606434 898742516 787224857 820752151 387814355 938070320 678025445 829358056 723698990 815459447 991871926 993313825 730319248 860941494 501023204 555768472 179488227 422568634 251613474 499206902 625611885 650120450 528134106 728724301 504923366 549755825 551500782 880868713 14758782 768468617 49591468 369947935 159213559 686464634 141328105 795689040 510953407 991399046 759391684 929108433 683254322 781440230 546124562 952997964 486937779 607333808 743142614 960685219 550656809 985954183 817532487 984847588 352774078 982262710 191150428 952975630 622907403 894882892 406777309 653276090 643370384 891811955 743356251 850310891 360891246 801943263 746694006 874452766 903882724 904135960 203765487 621700555 533813374 853653631 905295908 914357835 1 405321355 819284076 940243889 892084926 965705180 561523088 632264796 832945328 859623560 859430845 880006796 506880670 986141911 671706722 877137948 531186224 576213870 438490576 753570897 901968502 955933104 537879484 693925278 533366810 555246905 636248798 875509023 945014067 994742046 846553227 891371069 771039357 936825522 312442116 315692413 67673697 474150972 751024472 870168686 297653550 793223801 717856127 986054831 218276427 773255455 233000629 649221711 446438851 798846559 653429836 768592312 200877481 852832897 579882615 691175527 238156944 748682644 239794901 882516537 277923318 984614363 679368269 932572827 918964662 973704781 906018100 998551285 326174560 699121773 454824962 731672794 916032377 977715990 786443860 973427380 715063709 910453338 324461190 883724553 38473756 273362763 140650306 748931415 770601445 785615511 659029232 699461887 549836304 953538245 996080368 999220209 219816837 490742122 857990173 936228019 352497140 872724176 178740976 380469826 938081388 961300924 349386877 984837832 781692195 797095715 357079218 525162728 105143812 667855768 709290225 878564358 104703692 210856475 77919557 577677780 807515246 888054270 511809077 552634963 453233488 800987712 87748644 332309832 445448515 957508812 443359923 492265091 468168613 825358282 812192819 852299180 756368486 771245656 461253896 475671280 577465359 969289133 338833723 703828112 833849607 957835144 349678064 511022819 443151371 490502526 518380840 925535162 104540247 377697879 949064912 982824876 1 177590422 822194840 975634452 711005154 785627011 562124189 741733955 311181235 766733422 678180767 981661591 306867750 553958429 152240766 709509702 287718792 410349720 584189746 878296211 128520005 131274465 427391234 785487251 849454424 891310081 976652965 983762714 246785715 555234705 777048871 848838231 570713467 751919863 761143905 900447624 181222259 714388100 498098589 676510838 144918 151910720 914879582 951795303 601837373 752586422 690516654 929542639 559684220 819696529 923631255 975830014 434203793 893265193 718700857 818234873 873303072 932941948 134766872 287211422 12520878 22234407 733468757 838564625 58956576 222627594 284755988 820301602 511464040 552433105 808746629 933744868 516941096 855763575 799116343 841531540 786767625 980454998 218463637 838800679 902180698 903082305 497555021 593576644 651822842 832272816 510904772 828743909 657005061 951245192 828729238 904523548 828652998 940243274 267267657 522505649 37140947 507748534 701461757 780217556 391387522 617877567 794865492 862670162 652425948 964443259 373481271 971134383 631148561 971496150 511807622 654679454 739648321 850825252 377991793 923194927 350829621 447016260 967475096 971844160 157555714 186541257 747118709 809024027 525419803 631739593 598036492 908977692 904546328 994418420 620979765 920459397 631255216 711614889 707986773 857898313 898459184 898890673 580115033 588544184 657119104 737322069 193592690 203994827 479361675 703099760 539959712 651103027 937099253 954504833 864236403 894582031 109681302 516574190 937025056 957263175 428001221 583404060 572066921 982488252 702800569 821293211 471639696 666145208 673695852 741541687 122817941 330545359 934970777 982001742 639618790 935989290 634442943 934674612 382403490 527811274 274943256 684318055 433343350 688557673 631800407 642252704 936110533 991648821 579868078 799832129 1 563620194 175343689 215907598 446724503 825362265 141589448 318027055 638088578 937759002 793843408 866737243 221503313 811344798 208495334 224571794 415103714 801091485 180113571 340323089 513694514 742100521 120544155 777507606 920333023 921546084 749411033 948123134 786494779 975601483 669060626 788667649 552555093 849915241 547088107 631987938 732302165 869146359 750125842 762524387 925126073 982951168 617926621 790566721 703151730 917110585 890929888 901988672 605528585 804943772 336921139 498022087 394009444 561781265 693478181 849517346 288726605 515940036 656920016 823352776 829028568 903231207 803608970 899071245 511835090 758490757 454029523 648589866 128504590 128851619 501116844 697507184 904719071 966596239 765086690 874745675 8367367 350808183 384300470 904418759 177150625 705304400 666405719 741955450 55480062 590179835 620573835 661721514 659722505 715841962 754276191 755890889 886120162 990685888 99301901 173329305 743470127 969267307 777416733 841633439 234393702 438816504 206373664 679563398 105366529 129701423 745086 970148371 399743035 900284586 825699409 977085002 501517475 600770672 999133144 999606504 144225791 247978127 381427025 995024327 456832272 811114772 516514471 625991674 935116184 978165288 805175771 990664394 79877266 809901412 449388130 471343308 176135168 919676067 200832144 829030677 928120963 948466235 125633060 385040426 988931972 997799195 805399282 868604465 248401936 841147343 38289678 89053838 22363877 657096539 165652436 646024566 38747015 787867720 596174932 805193202 377963835 425773629 219513959 955130858 883623549 889561067 583654031 632008715 472643072 497457068 393887197 778076539 348991241 810665477 878751990 995180613 609369904 711606864 947100329 972100819 157529137 501134348 557296989 712175391 45396458 954498150 117059138 651942291 606435292 669484379 352764922 460548106 202068215 981013583 289573248 633146820 150043590 922046039 385293961 966226702 255747643 984926969 2049453 97529338 650049495 917384450 739789970 899356401 67790496 664509373 719484178 884453294 23604993 143232031 504431980 886093325 242690808 392490602 870451459 871411245 812806992 966105146 107247263 583031700 41174340 477206339 372536024 975445414 23041409 971375306 535264198 699082067 92884314 498035150 852438783 864288541 532230248 632863604 308422014 932730686 886857412 989788409 915581649 918662243 610993280 943583026 817021139 980104474 45596461 297116235 332194812 370096563 9338237 639268062 319189850 424480548 737902506 982536854 624358760 990769063 447984747 569514051 980940502 990270987 176078602 431208806 196972213 305406190 695677950 865125465 872366779 932769597 378096446 800922629 662092034 771191743 608011324 683332291 930114157 962038133 86961063 636266836 334039750 947903866 560337753 822126247 675135657 939832212 559585244 973216252 182459202 668241464 735726053 820240160 880103203 896248017 497070124 501786003 141872499 967182686 713709845 797016357 889377988 980947919 194346662 843637239 191664610 225422264 8835389 176526532 67838519 453791000 543671957 952336348 360849629 636720699 946454367 991838298 999649068 999716639 878587317 969818242 886006063 993608874 254516919 312684569 802978971 887263326 6719092 551812131 403527388 638709406 493170630 949292797 433152307 816573987 588408601 597216741 782698541 972181297 750840696 921029252 461189270 737426714 158016626 853256983 512199626 661308785 295682731 394901262 265543543 749800489 55807694 985256309 810791874 877668637 396764706 674492121 22619324 228300574 246305997 477542886 304119914 570569390 702211415 987266080 532396897 532489814 644482162 717240832 111855729 817015282 324424370 905128544 386697873 661434045 429643669 477196285 504392868 970655269 27607960 357112508 946359116 951254789 248540756 778549006 959546144 986915055 469569307 655467041 356909313 567300126 604630350 917624750 464236051 945895319 85979763 565411383 911740909 954629714 829889402 850846604 764520519 875191288 62886775 620003475 222339976 584446989 562979343 828100876 379528845 420451641 176221594 527210403 727320055 779224434 408272017 550963786 861125973 947170462 573988209 576737238 425500467 982486351 251381906 470868239 397904692 897160386 57450789 915140960 193277817 726439281 213374673 335953777 744549114 968047219 318250709 326578214 347241708 840172159 309724183 957978950 230084870 919649453 536737069 636163080 500652114 590292338 431350459 736606490 774903518 859393348 916232862 955771478 787084297 904041221 436300483 471083593 954290654 981854274 12842141 593435749 758614347 771037790 888153445 978117371 222015486 887760571 607796874 852599288 988508943 999618590 435471433 586422788 613191227 726040066 357744569 937357656 304764093 527088998 752838862 925395488 385075120 772836597 810009500 883072700 757169370 812505458 386288433 951096987 409544377 986800965 513212649 850378596 247363742 689254894 1 95720302 382619861 941629334 478391757 785524242 467088184 713771203 983532763 985707438 717498527 969469915 84896921 207891527 340141482 665364619 423775867 545438972 660672266 737346820 54846063 444753426 430387493 917697525 888640157 960705639 258308289 387156675 909259421 970244626 429207814 782897302 485100889 701741876 56842693 701552404 359254292 900321737 34333004 892227388 321422516 672459937 79000566 755716407 911107629 940066059 455886521 599341312 77278141 731141560 565243144 679194588 339871761 375654591 178770569 221672120 947827277 985969117 117828596 429820454 384252934 965149952 90467899 542076813 473601455 702788432 495105591 935001209 206163718 582718327 138750470 529927682 568108832 823557957 74224216 380325753 889553656 989744227 119817744 536216433 446924878 672942875 316139746 717208367 655113330 676725559 1 486578876 930672173 988986669 914341289 920274701 766619289 804790663 368490312 968887111 280303221 415860331 318839827 602488514 522031218 790205311 1 760026906 659522606 916905291 264955726 584110399 256715902 601692317 106921778 460165804 227868781 271942348 257913406 910538145 155390679 176940941 481976097 521011733 608540337 851950925 469199784 986194428 737855136 942577682 21273665 645118615 534366214 876793202 320208844 756957583 641298074 772475742 410031632 850603671 428478392 770120563 913840683 968580474 577025105 790865359 396292225 555024089 750322959 998173386 90055533 682426033 46796489 419458982 280799949 625510319 308300558 958688477 638615764 914362237 544458693 890333740 341572568 608652231 701630353 726510281 45501644 310067486 340339449 371744483 962635722 981631484 31673313 408500630 722708064 877795962 650339834 729729174 681302737 823746315 365184477 994101361 658548094 879348601 410685195 987484822 198514187 334081280 282507065 843267649 757376134 785811689 979458981 986113078 265583614 740618274 410692238 775742943 249418807 653170434 293914558 817681715 802588746 865917672 404982149 570897996 242882432 826638557 127462756 521018142 52535643 623120056 456047713 848674102 371809488 546580293 176116013 958802144 389514110 515155222 500799356 678081822 337398152 981151468 669851017 686631018 119071123 414371341 478096988 774568272 839533478 938202439 279399932 739916577 836602288 859222067 76916142 514441536 791574203 880540993 505774999 730185884 879310808 999414715 383009124 650740289 72403404 356433712 308412582 863703231 743029976 904783701 64450724 365013854 748228965 818407611 826624206 851497385 34849566 143586826 896232087 926388457 722257414 966339830 613131838 626538603 798917184 971416155 665926997 735934633 622051313 883540438 241569823 257447446 967687249 974631799 739077956 884988353 101601093 964796834 572936761 741702614 278015442 534139662 610375096 881706152 908619120 941470155 23526913 687052336 662530150 804261433 472453751 978773735 616833979 942339327 225690013 647773668 138009343 372383908 686753928 897596418 244092529 350589186 152235981 721197936 650250499 731099349 578393472 618939790 469112634 909318361 689089 730510291 404629687 779794882 920019666 947143783 92639506 507848245 601367387 640874383 311606694 899873051 495986786 770073316 169691029 523715357 812706166 834996881 12352541 223460265 797456335 847671868 998138234 999522169 25963093 927062596 354756569 653356115 30565704 131502058 672484004 967936508 569331186 906425648 990505751 994156943 243334456 982797258 304885500 792412359 337438346 750876064 560500416 749132558 763549041 836882196 976972766 993432661 695752365 770065139 72053181 721218318 637610627 683683578 806698159 843555539 942165735 997090797 788733349 910896422 828329860 994971117 832838038 879045080 123521321 824287008 600455165 654472490 238845403 503213954 294150179 537812549 30304673 922293058 124491797 935531187 602153948 699587492 585390795 611617945 412579549 890613026 769551196 810712161 338581364 729880698 668436352 975541019 65916779 770781332 371015108 965245266 627604280 691845287 976836353 984619908 136078316 549948172 602802402 785557115 895400869 912299537 958190194 965456302 572913024 600790653 847383205 858536912 858086694 867078534 833664640 908920299 394414171 744197322 349960479 400287270 939664042 997292681 368590777 982604548 942541176 963416993 166044731 177575205 477086843 719713644 670284172 958765063 805618348 961734525 423718584 953241265 285735400 633851426 949581644 991535874 296837462 696030074 126743781 468616251 768687949 978511616 547953219 666448588 534503891 824159612 762529651 800587800 974460313 989256559 396543563 517871053 4415225 437421808 539699456 957867145 780240668 791872325 609226798 654195089 936118378 993627376 772768974 815684603 241070378 522677622 734840895 943397123 585153910 622669707 345060036 479454787 381414508 686424034 505291950 645561527 114779265 447141747 584121159 809094388 549720613 617131509 813158299 957225272 173998960 726027393 345257344 617337401 160655182 428220821 787242841 848705619 967727453 993702387 622385604 979846206 620056594 963130492 383975263 652013405 46248276 984796727 187497814 396523782 206664544 539455235 377481292 834129447 619664893 642583813 1 780612917 717865126 881796480 717619885 755373595 260552712 694128041 634212679 967443492 691556866 850217022 852636654 879141824 686465199 830285150 838239689 969024746 551310095 696206112 832359663 898807896 616154014 775550157 160540963 586125878 211781283 432903957 526895553 770448383 607305584 772820453 101134552 721642262 831648539 940723576 238344904 893636540 262022361 707187104 958749136 958783966 504053084 918280512 440791600 649930218 3525764 339639832 915055993 943323233 642073682 683126892 105010569 987797666 557380726 718101546 856173335 984447696 101488115 767434780 606919732 615741728 465403088 612705177 852605954 973524629 568782785 895441922 80842832 475312294 803230021 833403744 323953726 784090131 620674376 738588418 711788043 794256498 895840993 907382019 840688319 941148016 534594021 767556073 582681707 635263991 473572849 546688270 36792613 710102823 706675941 929721571 972479515 998431735 442896839 664724751 654842102 744523109 564163672 962485516 774577208 989072458 830088261 894100968 834239547 929925828 783409887 912834366 898071943 921955370 92201029 861722787 146541953 471404311 41723639 446404001 366653570 695280068 210901692 788704924 831902823 971340831 858696614 905260667 70151813 654939240 365884577 493267442 733166749 991173256 617206944 858299799 621887138 950215402 484549591 762293606 382446482 584604529 21756825 937095246 434153801 767656173 377415702 922557810 123770292 149088207 239236728 783823062 400878442 551381201 374943866 783709139 23802778 774249400 71581216 810624790 586433550 714364606 324924403 589433276 81788227 456027557 184096014 501284690 966366132 983204094 562770078 720481683 793364584 983138022 961848348 974996746 956069967 997751173 912818534 971503111 773816136 855227725 909688328 930347966 232864108 505580290 923969626 997646566 684553966 758075497 148579556 892538492 913525577 946037645 245272875 998539383 691903189 793245242 68154280 716027521 103829830 158246944 753340945 911765396 723870379 770484679 734007377 855138523 608766457 967788204 620257182 851543188 563882586 733994703 998980205 999130796 675084828 818729458 614121893 945967628 202688702 821657594 914921875 974327876 922059884 999265042 984634485 995176800 836868218 861605987 763275569 808498890 908279184 977999848 33104999 158751324 969224697 990882608 293778596 455582406 36774253 251290519 725060056 819268343 441475857 583226459 345262286 510998556 664536805 939055112 401986315 751900748 35705604 339115384 92142785 525605005 229045731 651887174 367713549 695965115 432848613 950099874 141415558 933404207 46635191 601060988 588951094 920893852 122563787 320014152 40648106 779849468 434737347 743014693 258955160 601641368 394147388 596059776 632533385 904680722 979641669 990206682 471740495 780333301 320845124 585570009 53762154 108509614 402090253 538522570 948533460 959848738 612790206 866540137 131354650 674096427 578189429 870516411 151209240 611729907 431540695 843890777 475373799 708462396 617492050 714181222 322546427 877759879 578074497 981406799 213660190 672349996 273683772 957306895 687604057 696136594 990451356 990870883 401363798 528076885 16209728 419592883 410352491 619439980 836219890 960936777 433006515 660741601 161714316 766274334 59108248 176539994 124363886 801901789 740514810 843798617 185467747 491832502 425278827 848445118 894750813 924759025 475557984 690404531 404195156 602410603 936099406 986286214 135348151 851021055 391216563 900774876 320813511 384259066 996499463 999799310 568859715 613843583 910309295 934910843 257851723 701243251 970649743 990615608 733522163 743063712 794941134 836581194 810987168 901760452 513745581 869765119 535960029 667594796 470581386 768950773 470659605 613581713 9406345 962119449 164998873 633938266 851849896 970898716 97044422 291678727 379641184 608772283 930962322 957360886 418808741 639816674 148920316 990097698 619943099 730022558 730541867 960458202 470383420 973394132 899474320 916354997 819143804 949657829 762878178 783340980 606526042 743612915 195399191 200156620 629345466 643462652 177552333 278727800 320533610 510857794 607409911 709639612 602755571 885797703 425153646 479233067 792452642 920287245 119611423 702261912 664949775 860242914 909140605 938584601 248094580 352764543 978419102 989568614 638390349 951041451 858922662 939494639 700337567 829532334 88674255 962628417 168494189 313298913 899754217 962220021 175626981 953367512 306444948 800815576 261745901 278023615 195104706 971020876 190311252 390464949 700307440 866133382 968222459 979616552 859096893 994262425 441645682 885474645 536002938 750070467 461143080 770244084 937640846 952994109 69132725 825447884 994743801 997728959 334219711 728272031 530583823 555584446 190918643 884840430 392289304 931392282 513701663 679314400 436801813 629606891 660152982 855948501 96015492 941007558 742706237 874091917 10257949 492001933 520360562 542457736 301176403 573418843 928690072 936293929 920966250 952459308 403817435 492636133 19483824 899907220 89553162 715364027 641378712 680628620 358102230 688862009 342500339 844934265 117364476 336759551 222818291 945284555 198950485 210497365 998762996 999861181 478968976 551232426 246265614 520454286 673487871 780762771 178867898 780411941 964260595 969365529 405375626 903565316 476349614 706458019 722068089 733346078 807536719 978754002 201327590 933870482 1 482123866 336108081 590663256 433341811 737086137 764041731 797852610 995160224 998384283 416979546 852582871 582506848 864317854 631093091 766984437 987250312 996095171 909599433 922482118 816402255 852757656 718392198 782958327 3130857 687248896 196411215 881556753 837781113 905811835 948448535 950782585 732525927 758668610 555993464 904511632 242530425 911175120 470891125 984471370 682948712 777137632 883787596 982668802 878769597 957441200 992822146 995850652 775361472 831173357 768734302 830121914 445477306 470802476 353330692 356435535 665232336 978447879 532323657 564447168 365371691 453594655 278382454 796069900 532667993 802952091 766531360 958450725 900817324 912043247 68142553 705102480 566362290 796675967 134566789 862126940 598352807 952235097 1 962715170 673372357 901454849 479804020 843498994 124951330 607945674 778034794 820973151 197152497 760796456 675523337 879994764 909587435 984690684 527562375 769143876 725665605 845695524 418420108 643320290 843193931 990843304 123080751 835714563 600337463 917081521 305775300 974626183 550061477 803080994 830617201 973498555 957777220 990693968 834677140 887534738 959188243 974653794 66131671 470161364 552676187 695723327 359301914 790449071 683913719 732695980 1 232637759 594910612 744607629 866832033 883643678 30668453 230703098 155717087 331060038 238946327 647200024 566492755 961496910 4506227 615384733 875923903 892206977 505547838 990731340 692495460 982313596 752158623 951760815 991638377 996280926 296808766 460930540 886398456 935241181 254334057 705007063 570386188 769230775 299781350 763232821 117429744 781785399 168701405 337627582 852814981 878839877 848698703 893420109 586396248 842414891 519876393 664392441 242943268 499584894 873684421 979117381 815045233 963677465 374749517 958401626 124854375 936943336 928255404 973914816 426428609 621343779 141235011 968506927 371035001 486002578 820807612 858839021 380612869 453126191 704876310 930096106 226509478 881401787 103310183 411948235 367550893 663389545 437693606 637621465 75693933 152846213 634838636 885398814 861675787 994755232 143498231 560209803 354188488 627456487 225359664 870593980 414771926 836762736 239992084 386386916 778257549 802674763 162956723 637025360 25854596 892498776 914971265 944067250 722312930 928722977 53393548 705474651 408811269 869350725 61506516 106059727 65935112 932804743 856890422 929294782 927665167 986995452 887758619 915122691 203457449 240275892 141643847 935867938 597313452 832758173 829397929 925681194 797363789 857590042 360964291 781590019 78994252 786450831 755651608 828518125 933156646 955113578 227126624 364204070 835968095 976871061 870251779 896526255 523275940 689257164 522395274 994623477 5451007 894714193 216338406 628834473 273245304 293414855 230394272 959050913 867653192 877799687 313412895 428935527 967069691 978663178 753896657 895758776 533311815 662722715 7924510 619227821 141758397 392978416 41902174 496835821 40605159 766883242 78543553 184064073 186603361 425473923 876350636 972585565 213242165 959364538 453144272 809920491 65985715 728241217 856726515 912294120 765618547 806000831 831381159 899846200 78176048 116024840 111991984 241866273 986274586 986916691 827834206 900772154 671504979 763979994 484168675 800553546 947378683 993546842 746288341 861813512 108906789 982454338 715101292 854488973 677823160 747822254 390838026 477141146 445677695 819072252 242920630 920500128 137481315 210217701 904392040 973012781 254267864 916452606 805780938 838071894 606064446 974868551 485553052 491680454 961371986 975403864 641199377 731574068 410631507 741708435 524109046 552509814 624506955 700875880 514033175 597280759 577073173 677150652 113548803 403936967 782553876 950549554 477014054 738793506 984437671 996747674 779293991 992273480 202458239 626725361 404663627 989857074 1175365 432947622 978153263 979947558 704531318 978924932 10871297 370722753 880004567 925746809 229743244 777070247 841865757 940663480 314922035 617589754 585840786 856979322 803507319 976593750 985333595 986775519 914149506 935090357 719860414 934876054 461854260 838412915 783880840 936007845 668480376 890094520 756850202 823377357 86136480 520206947 729596063 892452631 646153468 780765119 969131917 994863289 53539622 226726065 452984866 675707668 92992222 960738553 846266768 918020883 587331307 841502920 916588246 990837898 408438943 818780801 55888730 848720523 234481558 946931421 259259141 538300212 75308797 835618859 894260723 899642110 31997494 261020205 218886637 239500274 930395645 986628201 257691298 405780522 804997161 960425990 818110651 919719191 393881883 534611680 677599244 999416987 157357185 870341610 412016580 559116748 902015584 914201877 121554657 662318621 218058606 899632705 861694517 926507709 698385734 816037859 941128754 965388381 873016613 924697068 180742554 398887923 518810667 878832455 235685342 275164122 578238773 594765534 152344948 577555155 253790228 503829583 910870269 926296582 807465675 999724257 621465434 952661167 948226198 991370496 852947699 889291996 264784989 816644038 801407515 850356166 542835135 715589574 371016098 378850814 558480364 885613142 34533274 262327770 663408347 766278910 904542685 979305412 1 566194997 392904562 464917421 884372944 965830089 222119178 297572095 981957224 996696736 107606552 499953580 993598782 995657547 600141577 709524669 560823490 984660069 394807531 782269121 512605431 790082999 215065159 990489554 66617545 163957198 820023196 881401029 619167237 800901814 1 842310262 735425887 979816817 179144899 793576198 514680135 526500926 194954540 930682661 383875639 875374474 398686717 467383677 848117305 849539320 944274419 957077741 610612789 771900336 56505901 477559333 670695651 714302610 202403367 770010719 973809862 997102035 838886022 878288584 253747785 507667789 728781181 777825130 929849328 939614920 959372079 995367414 654487000 835549854 496911224 639890174 413995512 793736971 80843697 462111650 541306365 750982567 588546351 710243207 723120452 793908043 231470098 541014070 734273120 779549767 539753281 651921310 140753602 154260414 181851644 480681116 275304030 517516708 220945131 261945008 858406441 958914415 547472307 949299682 131350805 964166534 362497264 774374446 23235717 418219995 868438740 964126641 712992292 894986764 398191845 726060629 395406580 458497193 834095136 932398202 440320000 979813035 43486596 577874108 772255234 822872925 790142567 833126721 704931819 978599989 483582440 904406327 150871539 428630340 435772452 736939468 415801386 776041318 254988604 657829117 632353017 750789707 766270549 967348830 860373735 958273934 830505415 860280720 62599044 713181756 699301580 911541858 783508908 868896347 523704891 702048901 880457634 933727248 539044223 563930846 516922660 595923856 887999833 943363534 638699804 671397268 11336408 846921067 25183371 553128009 188303177 428995871 698607867 881962080 417658321 677138526 79256807 222438924 541455154 828032332 460202241 811674544 678974467 792366217 971992947 992902669 436882868 439143501 904186042 932375404 91859199 745275183 947339593 991849351 521582516 976049381 764945780 838116875 756250549 762575858 127542760 250784383 711863219 883904753 737746908 993454041 563867467 752316123 676859035 882825797 528677592 707658126 11623850 260378976 799379104 915002302 712968685 906561861 1 381887480 755715681 994393708 507045489 578919020 213858013 262544760 284255631 619989925 226004559 249864442 941134873 966084791 1 758392720 688789205 957792598 530968513 549975111 233379861 542841904 382023553 870872378 73349863 937123365 564688347 774526446 650255354 878679463 406366158 589664782 747174688 927333929 6266402 154433395 313506680 988649954 10528535 940099932 555665759 830340247 3128041 242664143 544148939 561914902 86315668 946109886 309125734 660520079 186529266 981712925 193063214 929399420 874484108 929471168 34419366 954897063 274685498 575550379 965138094 974131162 278396981 520201734 56587289 520981722 582127011 608246465 941729165 957850547 565092159 608691053 419727055 811324996 765042121 842629401 12340149 217923625 811664975 909509293 322593245 460380648 143698801 271921118 246079096 966046731 815978393 866280638 57475333 620992671 862880529 866281486 255108183 867251051 949106233 954863033 278855507 339508799 691522290 837916818 732401156 744534109 301776421 477580743 395966940 595545619 895020543 948715338 810069201 961845626 461863571 718345390 435592738 920230258 580487299 852561267 983310359 991638462 256400436 372910266 210660773 593015216 223232415 449988109 895436261 993194486 449597099 888651537 725536494 935900925 400436962 490962453 343936281 748441558 392427821 602338407 625808711 719384883 379123092 845445396 192079676 447094701 226359198 872643406 397549262 950770467 184934629 581010352 762767668 877085340 794483599 929072888 352830864 639263671 334729258 627479716 5375547 525954493 727652675 899051671 925059929 988800032 959109335 988619259 608353617 637757230 668172280 767035463 926463056 971243058 44036963 612093493 719022805 743849039 467162848 499744497 2802317 769954297 120025213 755803160 614279577 904839607 762439857 849272200 71643654 539772342 598475420 609451071 151651172 951175421 617328911 956775107 996086803 997169850 9941948 738230385 367705529 954388790 389900777 852408033 779846167 863799698 623739808 735291066 229745033 740877108 576522182 879593038 252000234 517375306 9444701 167784249 671563877 673987002 2115570 341354928 217727500 658258572 404421441 669004780 34086332 436477506 645415565 746684976 120887041 741152471 337177678 384007744 580640344 830166826 575062477 684763458 849781801 931029589 57118052 919336336 844264360 922769253 42525941 705986611 182411328 845662591 349500432 420603091 837920763 911151759 260123046 361279781 182579426 267208936 56921372 80115657 238825891 676732037 413317967 602298995 329644646 957736133 53545359 808600744 725022599 785006082 633554716 935226018 832684740 842279541 959335358 997164507 762814157 818739444 998328324 999005760 94675750 528498345 276903976 649888004 733897665 823029451 22758348 635087581 604622585 699493150 76241786 124805642 446103674 951234918 994643670 995224901 760679404 784380710 204980590 746587995 522105389 954196693 203334526 219011315 654360446 898556749 595062133 623979299 11256691 864167713 754357889 775905445 66955624 780942887 747104404 767696759 618231867 965736483 451614969 792631419 278228132 409308704 198101732 760509003 193111491 549883332 994788902 999234284 781460971 784339641 906698654 988150978 165945799 779259965 549813033 611510640 997621665 999143896 855757374 924520094 721647180 805673228 397901853 711097439 885077615 972449301 870700797 936151948 418908649 662137660 112711129 608969726 486408083 944767461 978175611 980263084 155173687 620935713 74382614 607357822 795741034 926007167 876041854 947175940 349644397 441434033 552389276 743587924 595343835 798226321 108855721 707618924 898010331 924485525 635413669 998687659 492023469 978787473 631013750 726611112 389492480 436278507 308531446 912620747 313416404 601844420 98168173 169159102 648285387 994901299 329691659 890953007 719148835 897787036 1 578168671 712135859 718386697 866851281 946194419 322782628 696392896 377656700 667189743 745187741 792692234 302413693 981611942 136198471 842584640 259686240 580568571 422482726 469584848 833108452 922601712 171521701 776116969 799547017 828536936 429891634 557184129 40734778 702708575 865808327 999763838 963358311 967449940 235068007 954173701 713072507 759598578 806706598 938266996 526925068 627891418 578088900 886921604 898924390 983562013 470127254 951815474 796082431 829530318 334501513 525339589 640202991 667342907 682475958 741382375 242236474 827761592 154462170 309896970 112598983 348713866 661193021 838317798 232971826 440143192 434050976 811971593 983651450 993625669 103870516 788727945 57736744 754360772 700910144 701984931 929934287 959155116 154968710 886590738 986096209 988295152 870291248 957516009 606909358 663625853 916839339 982450874 662207159 975769973 939419236 977885129 584998230 797124802 793893072 982585942 10137449 411930153 145821031 572716655 135695267 706347713 659208587 891146674 113299342 771940555 374361186 483992263 538739551 840049895 539869780 835192579 640074781 830435958 496180225 733481579 882998936 934382657 142839804 218069012 155752581 462342649 203625796 258507278 542503600 809563613 385705483 961372581 225706751 465871102 568346609 994383350 41600774 571258166 703596312 770395972 142463728 484125681 997283981 998318016 590431533 798747935 117790600 337488362 776132798 915421790 221043424 459777422 589888810 829375100 952851374 979447660 580821618 885740134 121888959 351196133 475486248 582444119 745672910 919854442 108846555 430460081 290934561 805957401 517255465 942623363 258575162 593434168 907546714 913381713 166991053 884718984 156054571 260838539 229678106 876710411 551262634 686473563 220364257 588914618 159950456 928576593 35046702 275540010 849537260 939228262 914623100 994328022 325009572 373007854 215237920 247452401 1 470130976 141954100 607514563 287835786 913360179 668488693 760090793 815509030 988450601 78114921 615398153 176203794 827496315 378721635 464080001 175377617 861837558 855409379 906666722 793574948 811017455 60528298 156977388 393042480 514656705 354237158 847777795 213748251 656142926 436923830 874860437 421597408 921215279 74082455 699354761 122842056 335807047 183463622 403162656 269986735 567717241 707534594 752082057 932665385 973989277 878287442 879086818 528308507 958988513 221833926 464017962 497042229 879458056 824773566 920260997 841677552 866537491 421620386 587744093 204796351 778583090 378613733 582241410 976933342 979216295 683664385 999239541 97482705 608337864 696236601 838509844 550518261 778250213 573706722 888297653 763738821 917344959 454907048 738427014 541202179 719723030 778607727 818358973 402976559 581638489 427380873 699361328 897616830 921748535 763505126 956182838 353536963 398789549 441684114 676437139 508198705 542298173 675038096 848572423 252974181 686304863 351150962 372728862 62306513 619030001 864099267 949210361 660721640 785945831 694859239 703787594 58371096 899297470 416377811 431973153 753745911 975796824 793817603 925272052 948418791 982346265 294908201 718758776 75155026 975425974 663196679 904690688 686401523 765267211 657203469 839279395 851342353 986431360 660102243 948855202 450198395 494256265 770057795 974451262 308182145 670920823 451727566 563563693 324432241 876903952 936388907 981720782 651680770 917516621 397314107 902130048 932829419 979253200 169674125 650055145 323118344 586591226 925666740 977620646 181913718 497646317 816292226 923325986 483696103 845710833 918993332 945742820 559245398 613634853 256691282 272547929 943136087 959356958 236763838 418201711 595567777 832477007 494579820 851203575 528468261 898759058 812034288 877115835 1 799319105 997764967 998328517 395740333 429431104 351948738 783804177 544024971 891283907 423089755 804682106 942858579 968713204 167999789 892761297 973480709 992534908 676702923 971446988 532800779 770222277 3401253 26553269 852737398 901697562 596441733 661666774 375540332 614845405 879526007 898717032 991386434 993321275 959567098 981755559 110211372 407319580 795486815 867302400 860469428 931277118 392186011 594454861 9129233 453435399 257294355 345997478 727978208 934718972 962478207 964061410 160229946 193421273 322798048 927623806 894641885 954413320 116433878 191503719 105119694 197829782 955242770 969446782 617430249 819102594 326714478 911573363 74531880 910769426 367418353 450751183 154598547 834854670 400036278 918846845 475556144 925699892 821870382 984211600 531847074 586260824 77335016 849210645 170653059 656066184 398724598 556947919 658398238 820468211 645548175 932528532 581352543 945889669 543359350 987245095 513728810 551094210 852913666 989707946 543559490 783145784 267168450 349818212 287552751 658498506 882636055 888144879 110384483 641628530 17459944 347832751 510439843 993946161 626053292 631238630 134601050 359700946 1 163414973 127151487 193537512 848617936 908772403 269803352 601796524 135762878 535666597 46500526 216351138 273610688 695089024 730332896 844137085 789454307 906447464 205062493 790058044 295112476 643312868 401877384 670765733 306447194 718402550 431199993 764354287 350388316 913502839 636032593 905368767 805431780 920181096 732759379 822652617 13346998 731067193 334944052 670092932 462631913 773131736 34524374 388829530 862495694 871545036 766707970 797494108 238284608 780350848 850666610 978416602 121953335 667719106 436904117 528732256 780889630 980598442 886262648 976173138 146906975 177331308 671903869 759831647 462631980 481199796 719515558 725951634 343021261 978177249 471759990 681919282 284069351 996722573 508404503 877594176 655438892 929277452 1 449527802 848135887 852998479 710494585 864646885 431958926 732858213 162192935 512601422 317345909 471906616 882797969 996692583 626209929 788740860 70724922 597332221 779906585 866107788 242847676 340036394 830606556 896668527 712417695 950464157 366370509 522545070 292589981 358625450 246185754 485728913 247229238 488785216 677720874 734173015 598143441 903862283 330381388 385374269 340344713 442344138 834005006 966962680 66492882 774622685 538084071 955514105 796729247 992491568 829325171 911887294 197921412 220639014 337309148 452438332 983969418 998151799 851767403 904598518 960291005 981137551 117953147 829151722 880858095 902221868 327470450 396650098 570300609 649394924 996890041 996891007 748139363 800420773 487402337 914521350 180863619 471419527 905127592 933545384 893944202 991655799 131215142 868347813 428816731 548152366 969983969 993398251 943456197 972419354 52071486 518106440 201462956 408846981 533558296 638282050 934491783 941689076 30818961 116988152 372310704 420974567 844702895 876052747 403355222 460366667 588106724 649388425 875492821 887429934 934320226 993630255 750260147 963329410 276951085 824286652 680492100 775027924 58894167 709351455 752124583 842289134 60550024 785357680 814035143 982239787 165054598 552964482 899277927 934845492 59305107 523424800 58502907 298608996 478687218 772624730 757246679 770089129 233510946 856925105 94378772 716329376 386911107 536564179 55699398 351489140 730470186 963146720 276914037 343130476 21636867 829653634 802487752 877849157 471046479 846689471 298947273 620646388 253146487 969476659 751802559 968210016 524338402 771669592 664053775 781320406 422057099 857524343 68459547 652620939 743666094 996955432 262532347 428179499 974715679 988034260 181020332 897073114 162981977 435813470 240815718 571607475 702940485 784739458 931471472 943056704 368656763 932377510 545186915 897850259 618455821 848900242 506930588 959520064 862031617 878449346 742701989 852419508 40880248 242898443 926039686 939676821 586613520 884015260 281158159 624205959 509372469 852732686 94799047 415007327 51795853 170713890 856781238 940045832 1 63974171 261320864 730368276 652959391 679745134 418474730 987875799 90594500 546661720 543727651 918374570 738425273 958921395 290148923 899480641 731730146 844257944 221799064 534307934 154249010 868296993 915282268 997390877 869882907 965738201 301910714 719956517 477373830 637309659 676426233 744994236 806132528 866229098 453921564 687669374 115743874 993662204 663694171 843238609 118410496 648795281 783184774 901669914 464383268 477615731 252188449 925228744 627260296 738234165 714920911 717252114 143836465 649718179 864379239 989976436 220623836 892710626 895538164 985519396 188493321 786428430 913655535 917703180 958537876 983226189 874699302 922246932 276538160 861360018 711779847 960615130 822560824 982862271 438011703 706326067 423247095 618095235 138012604 895222075 738532608 756670625 441979598 626465991 404879510 816780259 116962937 432073984 334122544 454284059 902064907 937642293 798993096 815978003 337272797 490789074 811649162 834236306 61431481 352804208 483451730 595669994 609071301 753080783 460807991 832429130 327973004 502677204 932683241 975085889 90047061 228471087 14553453 835784823 578509273 606430498 471865726 721349128 318990277 441127005 150537086 504464601 204468381 679905427 897228208 922357985 514371125 638071363 279292192 720076283 977269436 979305776 918199887 944677692 811706970 976660008 688422969 793511437 744385013 858549281 677619766 990090692 24346680 741556843 9230565 895861596 724092946 819660803 711253867 907821535 868744842 888802610 414632779 785149333 800915057 929569782 1 279762769 73768159 111468166 882742710 896522202 568392696 619095430 495340444 842333564 207832124 915474819 915109421 989374065 59351668 978161261 235256804 489259953 75653631 408758919 802527592 987221444 423792973 930924485 788741707 810334618 178717229 488302272 1 997857748 718893676 935210694 250305825 455513879 447617025 987124934 877511564 968552524 540388112 563826196 389439583 395976635 885387912 912578022 173588059 569965055 473350244 622431805 59313120 974019014 381935139 436675493 165816192 398066336 468573352 979137351 894127818 897923464 212695558 246292815 291204099 704934515 752143770 895895402 47596511 83215184 850219496 923382272 378966056 794463039 610638411 885361942 548069416 839504452 573916750 909942499 448768387 519165661 382946997 658654906 230153304 828635500 952468737 994786974 824208003 977634707 238466838 600992469 643442600 753435065 658188459 706902109 367291848 443446454 669422353 690568275 56109408 324535285 3689499 385236185 588212567 939536265 788451175 881478955 339775974 423035536 215431630 928048953 348130921 919189106 21412774 30050624 627737866 703202090 200199343 482549048 990259690 997420957 208489845 389946741 232157710 952836319 671510915 734441067 402793936 805910056 482811344 776571724 288646572 600283022 23698137 434058760 330925290 460759327 36026522 525151915 455992114 966209329 379378717 485692706 385730523 426927912 74090411 281236780 437820175 928862423 174143255 392007506 829473840 830611363 190570452 912390728 216251416 729606159 987973507 997528372 488116385 827796807 789778118 961387214 304611909 808857011 990203491 995937113 624477108 834075216 283688235 459037460 504541665 851088365 234232905 334270431 815293615 853250098 600922418 635153941 983220110 998988906 357257308 589815671 99806996 580956240 375620644 636444556 174840524 322645139 769234878 914918044 776531811 899867931 346278965 984803279 702743785 821571547 63213245 820675371 523885420 826736349 991605647 996216384 308352883 714777689 395080974 899536128 893753573 924061861 367190303 567431975 126252444 993427708 14118296 452318317 43680933 628783552 693457909 791180055 654327551 882894233 991194366 993178863 829382295 962324976 793886365 853435078 767936109 781127644 736296812 850625927 474079297 845685200 392282329 427370053 1843730 256270203 940103656 983823569 172346613 191756084 130072720 980801600 752538000 964435008 575292734 777646979 278584273 860270149 595951816 722832960 535166121 735206770 390167308 473891617 745209050 959590929 312227722 454961586 4688788 623598248 298659373 320582016 771468641 944689740 666518200 682606593 646632780 751494034 499611497 608618293 46705535 870099427 623910050 714924253 184052029 390380934 761488023 830887266 836432001 896137930 679686009 966933326 511559041 587142012 669409711 929122148 750105772 767581904 350361104 834727397 115879564 938107797 416464916 899845415 850104791 858072633 923748509 957864169 909467254 938679670 641519278 891188887 227398292 357455202 350428179 815509073 108904377 456779702 785048513 885874426 57070598 255185978 431746402 580475860 240722157 448575914 420828972 558289716 10566913 668053591 526943336 958557511 436303806 737987752 57095584 450009449 134836166 266337400 60588357 257592342 690679693 967952070 262424270 597385218 411129211 774252394 39858176 461248219 415377588 815056139 716758372 962576486 347432786 674070545 992367398 999260711 252788294 725627933 562593920 695589136 739861780 785930562 363039536 974895778 425648671 654256907 362352487 555245883 543242806 792820639 355851143 712824086 737097651 989761440 25829380 888644581 523893149 835196467 924888082 936278462 794254759 942187780 903313064 910776998 434829339 966308816 32806783 152142921 692647392 935854694 82812732 339545217 318909474 750130337 171350171 919265818 710942633 901302124 742840636 987064587 732674322 839942559 37014091 163550090 81026581 484933114 574884715 814135911 893922596 946579751 825651853 831875933 922573114 966164769 414827341 772570881 795626170 837710752 358378282 465334861 235682222 378954274 222093022 298405029 830115077 995003082 384565858 621413798 356552697 834796774 590374761 988752350 526404313 900969654 46180313 703985555 677777778 769856850 63545991 165696382 187919045 837034761 506547449 661792416 868775660 945966004 496127039 558164516 992800983 997164133 327710588 751372392 464058488 668832769 111641774 409489805 310020713 439995281 588195701 969609155 724094827 912662682 285553151 404786842 772328468 854142056 313147378 618852193 615343119 702090904 811173283 999791618 568437851 804500583 12873919 108587138 19264092 483800938 391085007 456484987 47876166 870643888 135760532 412935403 391355290 696695337 200256263 649576438 656191992 678043720 720659106 737356124 366266084 465807731 579190662 881188648 85372841 741824969 428758087 610424639 915209308 958801340 964280675 983122476 574512053 787665576 308028107 314572348 773504031 869193074 304079970 513076141 875103185 887753991 1 418458474 944938831 986618646 620985763 972025365 227335967 268644980 865583360 873552440 519469393 723017989 580276476 924771999 233707926 497216039 904888712 950968093 16076371 472759977 637806466 737218458 771449595 979030951 294784975 513008514 579747256 722876134 667231120 839564710 165578368 893373413 647105196 880013532 565185801 700244648 528077006 746628920 262958379 940045680 757744400 845111056 788925706 962893703 590433805 647097038 995515373 999261832 714648546 864722809 656351807 755409319 837118254 917097581 797551850 840655008 237721385 681401308 960436790 966459947 380174652 942388064 754842054 841142770 781131421 893121116 916982842 949429482 439601004 791356052 339637286 710811936 316414257 740090785 644573949 961805139 518070661 837620849 659294138 762599899 102414242 911213405 673949734 939178202 88399421 517750760 500456180 823684871 1 799947552 10836480 532066755 689193850 724142050 156990935 160306898 511483199 778151141 789566517 936290892 154619369 990730950 854372854 907377076 553667100 620168713 10252441 811189884 814223628 950896516 605336277 754111403 690347780 884849965 515562940 776709428 960131357 976676156 150839782 835624812 283920578 366720698 319259846 878723845 751847373 906144669 259374786 696731947 522145861 676953777 771495671 781818546 784423493 789794513 393006431 975518727 9766125 718756049 334193384 437963281 176131592 385111214 472126241 831521188 865721366 995613630 821287107 874078515 535529150 625795819 19617276 673915596 492762013 832730832 786868991 985116615 356689677 731144216 672020411 984811755 956700394 970886739 24455177 251780905 345500610 670623499 432366724 803133398 599210666 879178054 164574267 860192675 307515175 707189524 472415759 585378772 609303921 649636808 585252196 587954917 532582628 594074858 490523546 993000991 331793015 728217153 438013802 908366935 454400670 582580744 723864484 746175652 481592367 500598846 430276807 435982894 945522660 969037345 314779162 645681720 970539885 979687712 560663139 570145555 49343575 533789266 383500350 912414461 444362444 721203132 946612118 966946012 732409415 848960803 633571898 757894822 741488889 985603901 885116790 890329382 256342398 823333956 911951240 948207350 797308494 850201229 965539792 969099144 223669224 927517644 670684340 923626475 620544898 675819582 910001413 993037559 407010396 835864480 821427071 881398144 363093092 813135299 17922699 446372621 959744839 995070942 641183596 794856605 20776718 222482384 774737507 926007260 125008494 725381161 358653217 902610566 254256489 380173641 105131267 338600788 158461351 532555722 699197399 715519950 521396257 909627567 653822147 665197438 529205344 688911734 764962800 921001866 738265561 916568392 902929824 973321607 535485879 977948247 728352797 863566229 772339003 795972335 23841193 317852724 1 966259768 89112839 386724948 398396494 661420599 745931296 891262852 425413254 626300778 419840835 461940964 518052843 985748227 996624895 998724367 632566265 846632832 992158077 992233171 863078786 911069242 623130115 767794612 517904959 962571585 655458225 959361268 125767557 581328249 392520186 749924908 470713406 930060429 365210079 488636618 155137248 966494745 582762433 650290412 180433947 652512489 198766444 399040954 675215618 812832854 946962957 987973861 698747777 959701706 658383572 709398827 124807552 954390149 327404085 666602841 357458942 406093713 128408927 417278236 394360173 822780343 877385427 907875314 772653742 777297655 835185827 973343151 523183127 618504770 477175823 871686944 586546321 688723680 696769215 953596590 130277897 385970527 91193314 144929899 653371824 701992704 15206703 755733051 870697918 883011420 650226895 719672506 606842798 951268948 485190133 881343511 714890354 913124683 178296796 464571443 607199513 799065925 501336257 926850448 272323252 611730251 130959102 338820852 514383183 763277810 171601502 770263008 875770937 996032024 349282285 994656166 284886812 922876536 930189563 935041165 364979785 648862618 77211060 332204248 48044490 950655060 430976389 485376802 813995887 871923480 780050666 854891403 169965897 316160590 334326217 831221348 89498757 806429574 595238662 680840965 916876010 944923298 446114759 975103701 239023911 953734531 535292135 769381257 661912536 716271695 846430446 933806018 95638672 943787706 533930734 595358361 705807635 994228828 360511948 579077192 361983480 998451308 275508313 567277951 338964499 817571152 787175556 802303789 62902464 690279596 384043819 826897722 66936053 487343397 646130807 989140070 955539955 964019010 353269769 412167266 149034013 667625524 112531496 707557616 263171086 872173134 569336590 915414438 572152363 870009454 710449927 972412191 688086984 841104760 713239520 983839806 853780680 928707619 617868721 769520821 698648067 710690174 937685658 983379622 828179777 940459669 575439217 634954248 866648477 896236724 981945237 996165492 863000897 974857624 818737627 954265971 44372992 644891996 784570227 872517549 788130 390651807 135504406 758451632 207948472 851279416 494866613 500296052 882551898 933988982 973248547 981328190 242714282 415538320 402761357 416779315 110088602 119939822 685508226 838669219 77455939 196204194 617506606 714236112 391860114 967781022 874532163 995904343 372725917 803812153 941920259 991753081 863080127 871622097 892126747 971139109 589481823 966517257 522262767 689382017 658253419 687988788 367420773 844078030 458075795 512994140 937252424 985504560 168435542 205368331 128660842 453824049 332257828 924450768 902090192 917860807 221990693 752001466 759012757 874845553 753371155 766974496 404005059 608343300 207724095 328886544 592586344 647830256 21595469 903067829 270975583 871441106 71230359 402428801 133423061 347584868 710845114 933887933 595542627 948401104 590401971 888423690 646899585 763736379 399765353 873699060 107713300 858567549 757202043 971321083 929127748 941395107 684628985 737668399 512148768 609039903 1607864 62076566 997244562 998946095 895153306 943554743 953912037 968508829 98074778 691879784 644399168 838084227 575575177 579604035 401188878 668797317 120864565 579977671 602514284 903728635 111211888 754409164 940399158 993242095 1 285767030 941349931 957458101 681486397 797102400 309023280 688124590 265011643 739879543 984276216 986033598 224017788 389122440 957363729 965759142 657725872 917922613 245260857 891421403 972835137 982164741 363826284 499256422 308130334 959918270 404867891 878368578 332178178 356097920 647416206 780021526 701024197 853203622 32296665 819348582 886826651 933175758 275474117 999702772 427462131 767598768 360907245 633973447 93220088 145540296 812328389 899033939 50637399 524122739 993331620 995476493 395483055 451354039 65103527 120525511 151172758 356488958 740813153 977066223 564011491 723230233 721060355 846635853 236853714 605675451 372008579 971440766 226099365 929866141 895692083 931935846 209122845 800360714 724622349 855701531 158011420 297198302 507448443 887287759 103549639 137499866 781404393 788524858 281111537 928482880 791276304 814860226 785557315 936815318 964544411 974941743 417478695 906172923 855609234 999221182 277157178 313735900 824078082 988974778 416519089 519138074 225747757 313477254 726396531 829044743 771180855 930148753 846153143 978412825 240098586 886901823 305243055 364494298 584912994 656620644 376814524 833454099 336612728 928645998 779188189 815945067 185734960 624710647 757037590 901938392 217997578 531407002 186225145 550781017 775997306 815601387 241230167 669201552 74920587 898768391 456400906 745922087 399264331 683874209 365422043 510996045 866906548 937541636 876426085 910910907 193801256 775452273 378528385 681301951 222018980 946986162 49894604 820745834 170940219 871179633 496837966 970950277 500703613 961421056 498362697 828178166 254871226 874849358 824711755 843719809 680670299 965745644 775946048 906606218 575429146 850655482 502405987 727625678 809899228 942860064 859313209 980965856 659733759 938103623 722770755 732534447 819012376 990411125 966487442 994866370 237820694 409027080 217542588 273286827 589727833 963825784 441105290 467825951 734309053 799645415 217199738 733532667 711892341 801182780 183292880 624720911 579750490 589053106 84765433 792211330 931012032 981547568 634576771 816651031 817024030 980703265 667704325 819814480 993421181 997217736 468672469 860597350 470267242 735551117 404004655 633157325 575370707 776468649 427045881 958666486 997828199 999862599 308856431 809712165 459704542 994466376 525890101 699016879 355596439 735161699 177347065 727847179 162113762 674501958 451596076 592986501 242098779 679751800 623162552 945581568 216979578 450024015 571474742 784564936 973337492 998964345 179123007 470934237 709509130 929602745 125043549 626144963 614481930 938574209 664819714 996483376 145066186 743935047 626040137 673803807 457475263 965892125 682034372 858323196 662910824 667611378 938845105 998731326 819792880 896454369 202646884 988994644 76735612 863518195 237008742 472996914 248747665 597527295 798481431 808436769 509967583 547151977 283854650 366536283 678644656 817012815 773177236 837705661 979996841 997986726 111000341 303970989 229095079 661260256 687325963 911210906 136631432 296734822 299856699 991915916 79066657 201642173 599681958 922738766 896913130 986060560 234754107 331033592 856543884 992304466 630916020 783402957 584819835 994534415 791941555 989952833 640813213 987706187 398550684 685005833 949061256 972884008 830882332 855745147 660151931 691867441 38149501 323097039 752953723 842884828 901665809 915855765 351283171 590748697 411537371 498346941 810694203 986588676 346851636 929192284 521574980 560423013 398400670 812260291 993716630 997482813 97143440 685826961 449597784 713557574 999988092 999995733 689583362 725819517 392451325 969618672 636483197 903162521 33394577 75393694 435453467 922422702 196165285 410622358 113478429 628307304 642510619 657278338 36848022 404494658 860691993 968115184 228539761 584890689 515247851 739597267 179020934 816824804 436125775 864770545 131307576 562428451 1 373664074 735702399 882936707 549836147 569657076 59455350 281913295 586025558 835072927 59494197 73164256 728336646 903939799 7924862 494267921 66914057 591501519 346024665 870175580 759257090 861266046 932277067 945037972 798951128 966179595 55289379 257032396 274114353 366086290 17914006 543924558 245540061 711199714 139130346 627209281 441630597 651090916 663591142 788309489 41053580 209650284 212079365 565755478 185109523 942557576 186012718 301320496 656882741 810280071 241313401 596670634 46071818 399916416 516514392 713698953 198874200 567919938 774885817 933747048 556220718 849561589 981201390 999939870 97903923 905264720 50396276 81269444 484359752 824061549 816159937 933831799 223319076 423266127 256414624 819036434 342335911 557867138 828515406 841877787 111745725 478188030 645346590 833079280 877581569 979066929 384232362 515472828 98291316 822101410 585062725 718694579 453536064 540409553 23293390 415091609 322527595 514547097 514658306 522496061 379176811 385837123 71766717 296165335 648091311 731708890 834558681 944760307 767775157 791551946 513071259 967931262 401756999 812131070 784016321 928518060 422192434 723175127 137848832 196543558 70896757 455229947 1 648099570 437960351 970916219 983464619 996371916 1 941920235 448784948 899648954 711744728 942707441 215002205 333310627 70650827 948021517 190573505 300387514 564764288 567722911 427610820 849231497 923765005 943902452 116189869 532156332 23496195 353894560 4594546 864772305 921942576 988826634 849401301 927658287 727953017 741399040 41621779 125692334 886124945 893578716 483915659 993981977 246593596 920261486 790646072 869323953 755462386 847259453 933087248 952736347 324935407 373446013 52030173 717369860 714511187 715708155 366903035 831016576 238710302 693996605 198416649 636098900 688175056 846902343 842688447 922622386 923058160 963238270 476240704 878763243 435375850 734923967 449139138 613275831 990933111 993106129 893624963 968252041 693541422 994085053 274523711 446201808 69053953 503562874 884458548 997913581 500337337 732940881 925303713 925899067 311740697 652173548 935073128 945186489 295898461 497998757 235568650 630654045 922320174 966501991 234793516 691045085 811334885 863425283 471195847 744754792 226206406 376931110 232917856 571860853 183204664 974457023 704900374 852389657 843737669 983002151 627802051 649258771 981108782 989362634 580049829 838490254 368090338 550826392 308726550 680051762 326629182 643828637 916365526 930957375 894257194 931143915 577442892 745695834 795229247 795996132 789214967 863618629 274374988 316766829 984358277 993584777 594620447 714399486 62607723 529619399 223240443 665595875 678532141 771688810 428467170 870921762 438120310 836764900 93944689 129855467 957794132 960480095 519779024 577616747 636301288 660259303 507988109 956143345 750910431 796443002 222701471 970729279 391481733 826743444 962323987 962971220 264386292 342667716 661602164 756854416 211948482 907417317 598526580 773915415 584183157 977520345 354125829 406221113 611858841 924630522 378682672 415850527 780057859 934932610 624224463 968555026 545089593 948162599 744852892 920622762 301854982 927583124 709471470 928565994 348684800 775457121 1 331876712 872137875 884806311 27833872 918590043 156663192 457739390 236335213 300564548 337573539 367822214 839150538 882724884 492789975 896978419 779350926 819560991 122022706 157974728 289867663 319437325 555359607 679939254 462077598 884592141 129780537 741081806 738298177 739274698 77169901 856031024 323640563 794421356 242577075 368428026 946535789 959170096 433072072 911387420 210903940 710089490 38812490 983497242 549103583 829506351 212339617 961517966 83012685 946288745 294836617 966306334 825368621 891106837 460407222 559381188 31561697 510920817 254824203 671367919 433314419 591762107 856979065 874681650 31782176 254170660 880696204 927536048 78213582 202738710 367429824 534328522 229097943 793128414 483654176 648649302 935339556 970282047 217174503 408603978 372966854 618086085 769658144 836969609 751331047 818653202 414260392 966466473 783056429 931360432 354064240 800020646 685332766 987377092 798845028 938454036 944519636 970205714 973992297 983227073 18388132 499791369 959534503 974376196 196794891 734130045 757849793 920389951 876523498 931623787 446509043 736226113 873059885 986234997 525995109 839168941 866993917 883696029 486615691 728015207 399020898 736613655 105817729 231238084 328989890 387838951 810703029 877204257 672061203 700080468 662545376 842072395 593272039 698672163 659349558 666919078 870820953 902529943 884263939 903683676 515158775 744985050 225727245 928606549 695357695 843152087 377840467 740827998 662420928 734848873 692881305 985419657 160127772 456805771 437951621 902266323 256165442 695240782 363525617 986969738 575448558 957820428 788548575 900880999 722095928 735848782 85820669 509479801 37517018 686126727 342081217 663671216 625317140 743453156 316701875 815286538 62868937 176259644 187736201 996419643 955621823 995651398 732431880 991170203 37037818 476529031 910909987 975867860 79766345 794748351 913513964 995914536 278965836 406612051 855355584 917959427 396319947 606596000 187093748 769251089 642760173 925430497 741065754 858920132 548403825 919828363 559215933 865265067 676540124 872662010 748659622 855902541 812136559 915763680 29686895 452132941 73723340 471721552 792190965 912263927 755972205 970393748 632286421 767298111 851258582 911715877 952279767 979540207 746446104 835611645 62994761 583484879 661041609 823899105 801634377 840461211 996674714 996855439 213190387 525301011 602496831 760445630 443472078 859495900 163767717 771459805 801949066 978070744 778356648 805532497 228521598 679802887 324151973 680541843 268177227 547091143 742085285 827649375 175345676 973599337 232750730 367951134 608916693 976104679 141868726 233661902 432976803 964884965 371418562 689760153 416807009 917391339 667926678 997813082 203159704 755587053 427122188 505980276 140673031 464935882 971815140 992563795 756747608 793372470 356643941 974285301 412145255 959623621 394206993 932319923 459328746 790060765 102322920 236714122 697793665 918593346 459199202 775431549 872889305 983818697 372131497 701657693 625209869 945197009 956422054 958723150 639490607 841235805 264115031 507559109 831820201 846357327 285404634 939618709 987942044 996487136 813515674 904785687 701143757 765206829 859823271 997028964 436251982 764183243 102085248 877042531 144523850 529240740 671044834 854460633 771543493 911253522 981616278 993337030 748806034 974504911 579613284 943553935 3429357 969124327 135283304 926707249 845415906 933342102 905268459 948778150 724370384 733560586 269812769 807565497 547117157 568393321 326518632 738878628 828176201 834749694 5938012 359326543 329314944 974272731 834099077 983803890 954126827 988294692 687286232 998584291 262366782 307501715 474784060 714403415 695755693 763727952 35936743 491168236 597669629 817465147 826662342 991186859 546055408 609070774 823644585 838242789 757295818 765250935 782671691 960544579 127674782 683891606 200616649 721168301 238502278 702326485 838856309 902518686 358499290 551108819 953150772 993367011 289767965 627339670 872641146 994040335 796365918 986200551 728936450 927697212 659063712 810291157 953119106 969810347 250648960 813405852 285472498 314965411 613278376 901351731 30022305 472542173 809648720 987665192 979203293 992131875 799788811 851282195 22596750 857846502 36152812 436791345 767611607 833633535 516435923 868251500 67522884 997728200 209862740 784292732 951148418 978707306 41930036 115209549 777343826 900128573 299106313 704542491 368935117 783221324 280483773 980914120 176035518 737877672 231486206 445651039 1 494189204 647313891 987969393 201722101 233169640 783452385 817262110 513732712 719196212 264735528 369471350 283976229 496225416 3839655 884546728 596647874 891713695 887234568 952476490 252193038 553096593 993608988 995316196 742793801 766309532 272016609 867266503 441623608 800303103 443966812 756553398 5433981 611946404 629221229 764171151 551697048 858610789 936212063 974752000 361324024 475401563 93891525 792157850 811224041 856449504 145169033 212202783 350120942 565554382 377128151 543494492 566824844 921989112 741920003 955468367 601358741 834853391 507846757 657553084 282260661 769889931 59686903 274816970 322313773 556947568 903948859 904082469 449612349 962675766 306941698 710497629 965739141 966465132 493921591 649801260 982397648 988338231 157469645 524076911 797357730 837214675 992514812 998864168 567897682 791964237 964363757 985099711 158223746 364975154 164852994 617660388 21109124 462472700 729635830 891441794 602528783 611722815 412766266 598830850 991737600 992928659 452593091 517655864 739291739 772435362 662356365 984030729 646398010 765409687 415160943 905255329 94517509 640746109 399785417 557445997 662990377 702032554 200974400 287459229 544186468 717096573 526952878 684108187 379345814 870265904 991613740 992688037 628682171 785317957 352954275 930582445 736193856 919934495 545684546 665611918 241163909 646701941 274847822 392309894 147101915 951931362 64104699 373672701 551748757 676362984 124929656 459160000 240464308 341831021 874982025 891803599 130052960 549570550 570933142 749082022 728552203 920838406 537131390 705516789 631477262 965969110 862476752 892076993 298070480 728485535 662890990 995696635 86487460 118622196 961257866 987302947 818746582 931230901 329131462 498323782 901513986 906624443 141029403 167580087 761533625 900866608 415694263 910570319 255981775 459370232 718868669 999244692 908536082 987380736 771797886 837936588 536157511 873438294 334003686 440294181 683518429 730597460 938081357 956254905 21992723 285939111 945696686 956005287 20426357 199949481 1 729638327 345741531 820904784 112690899 366623994 598310509 817764455 110429089 160381715 23047687 953218002 68947762 583144124 637837176 802904762 335410938 775803822 245580464 353578092 315451389 322794327 400371152 406355092 648105780 877393371 326913095 592045748 380665359 752454420 541371132 709881262 259111275 987043876 65755653 852376870 999597859 999710986 918571696 934243831 277790339 971929179 916275589 999058511 145687717 584669245 889062025 964545727 1 603037216 849499295 959169318 595795444 714847059 718856962 773670809 421045451 655301041 823474939 897024312 550943322 707175614 831586373 995280471 516547674 925609794 578990280 718055640 729272587 732739705 321454792 499622603 612776480 972784998 362716240 639639201 493687208 834420960 632503647 651200329 266576339 864985470 34662274 50236076 613599479 776866895 474372355 977006050 210949972 285502671 41501242 782518603 990958918 993240608 271998361 539345252 552064956 944752355 859916344 983516224 391600401 912496255 203194707 859682778 370237156 389560727 51046629 352022613 780183899 826513019 748612942 834759237 51374568 584491232 448827234 643507951 695924299 791378864 353098535 902988704 717791694 939775794 122807868 858171885 800230487 954875057 820376450 953601540 985754335 998227514 572916097 665564911 692941710 786118197 894548835 900776296 915844061 995564746 606170743 640861254 726608313 906273733 289030584 982433091 925805717 987992849 779304567 876542193 513963233 890970928 835809945 880668019 347830613 970752450 658485655 760829802 467681425 791386331 168721065 876847684 971891432 991614282 263672508 402593325 995593730 996011735 312079295 472612826 930471372 941037147 375772605 872267326 146501948 787174320 488111955 530431154 363935354 398933674 956784005 965389720 115063295 983003985 561991080 680202233 70708376 546607468 417334998 611912886 173389157 851387308 502579547 715319702 241858573 398630188 455992215 687152908 294001474 751463109 511263425 744235718 832220306 934257598 643814968 685907603 947101937 962179594 372327775 593848826 973540659 998974835 320323145 474004365 876297176 929031719 736127593 954362020 750011218 836718263 362141318 774745076 642302582 743460418 909352784 973116507 802826269 842003685 832038968 906719918 388343513 734498531 241125746 943358173 191225026 963144060 571067856 610557649 6594273 611217096 161636177 757603643 1 542024299 461865712 897844565 223992436 283496764 459210361 611663032 98442950 896713934 317776150 422795315 230914620 637133396 329628760 534033655 711910939 750120611 716870808 909890559 584470543 787867382 680127423 805289093 133300347 321598110 974243345 975884931 28064608 648274307 72361673 157955115 691566461 863807276 941324752 984697471 188988708 397399863 367717230 849531957 969505460 979831732 58554291 917450755 552174047 641650468 333741145 732788816 212885540 853858683 154623305 838059553 612364931 613917447 203752995 339821599 263705185 750525084 884978493 934055065 633504562 812859228 166638236 803747436 612698802 690278054 541255037 624420203 680611780 864091906 621658981 685980882 60287905 949845561 711463576 808161969 715259311 920784003 337601368 885346186 504380296 533117467 147754390 304499176 881048558 915234446 781589641 794418440 775500675 959360732 939052986 952588175 507268790 909925566 413646510 564476015 215821830 981324612 75569521 230348588 74224742 619097006 546407542 931045106 316028088 353986107 960296817 978451342 50974276 376735162 734507784 969140877 502684891 812577033 157508683 356556218 575386601 613491649 905359106 932942148 548769436 551381119 96683616 785182575 765246150 771611545 311411627 621416965 555942816 778227866 576582020 588272277 791511166 939139297 857349985 872956593 318839931 636146876 839021933 996993023 40222969 823812819 112266057 768276134 899197285 991004543 342173480 489699581 428230847 656422205 879643742 949271529 726323568 829804942 105057089 923114339 851114363 915941082 930986563 979150258 910477542 960726361 224531479 830915684 863487823 923869419 584246458 589032415 861478035 981725134 847808927 983525125 711048555 941325978 358382460 959170923 327586880 474338515 488979461 807683168 622121213 812748424 833731669 967123016 795948805 801957527 433456700 625723028 216657005 414466279 139919202 834864105 183467947 663399424 875623069 937815941 255551276 423621781 865178279 905838821 974426002 987094511 49906179 137618855 988263657 996200081 984817443 985645896 662811312 932154062 146171306 954537929 201363603 572892753 971067858 975207784 288040644 498251020 177913669 807903445 987109325 987163061 745720555 756861937 92687516 996499036 55157605 795968414 165091706 679680223 799968753 884058790 702146220 905342759 519751710 994949728 246535909 973663231 578017020 768548525 367261287 442407249 107657715 827939886 177414917 479394686 220257629 807349174 508589375 902322614 171195030 386608557 330853297 856793656 48601255 412966853 634792906 973218716 91818946 126439128 697649154 857927125 879234803 952521807 539638857 705436378 1 682845035 389126207 920657258 510184480 915184400 131554684 775797612 335383093 458874688 316559279 828796711 236626395 988046755 361847794 605862293 172948325 708093060 970014755 972804882 277566433 606176028 861927223 987552850 55511420 864228428 414000604 990014270 973027512 974099284 366360627 745512564 222755237 331627744 788057022 830497012 318888141 759619467 994937036 996171143 566306115 930186163 118033228 964981493 109545200 515210842 26443572 346184895 10979981 120357042 709799730 857493907 289789115 417833105 544419512 738507256 4432692 886672941 811871601 891505177 54434820 588982363 763936830 934598338 458946525 742292003 780618324 891978863 608879361 669266733 888369722 917690469 332816361 859210907 624697064 848089828 763368762 771146711 432632124 737300796 597659880 970090148 615474346 762428488 933944079 987365672 640202261 883629554 897174054 935828515 435371878 484064833 682941211 815437329 509176939 917655200 236145716 632130211 568534518 687095712 61038150 506672395 977676597 988011094 720447346 788427284 792584009 823998327 25741949 796822548 373307589 735727619 34304841 549843705 636384837 726137799 79176300 102608704 688250542 868231804 464997634 728505051 810923780 909508135 728049919 938325596 482102717 904235132 659911036 851790990 473265948 771685093 326147654 698466177 810762096 870804217 108389474 338759267 96004564 660059889 234752256 392659836 202459208 510080697 273171633 604539657 923650804 935216762 932097020 991475516 426323960 777939142 946632019 952735573 795253710 858698976 775881073 958276913 675860916 830434201 365442816 885805655 818505100 849264960 627676777 805627998 546874298 945626390 302631172 839951816 180307247 706157666 609678484 947377995 560863829 965608644 949583082 970907903 583925067 792408008 617575831 692361350 227923276 942825468 539789723 978202393 681873695 960974888 455946059 506424427 40460106 786062127 831210534 947899813 132164245 557407729 17465111 401370173 750943770 803349087 393407245 703917441 11559083 765096043 487149045 672076382 959363048 993609375 401888231 524658741 305741069 684633269 530730277 990154571 2698178 254825568 650940179 998854885 255001598 314447330 51903066 101273436 227930489 491289828 56571521 461472215 300703939 970631058 418424381 737306709 520409119 892787616 736600788 835523828 950382015 960587110 989241800 995841471 442220607 778487225 56548543 224953670 940484088 984269330 766113343 981678655 261123824 984743182 729302120 954603383 806255423 962935664 399099348 950413056 312832508 654667498 615756502 822447663 790808482 823231145 222711108 933236974 439814528 626204886 663855688 787450038 27101247 674560165 639684439 912847556 107731490 683202242 399635559 739805700 867068426 879711666 900366244 945025323 350360148 677290766 241970643 502979141 839097672 943394012 253545152 693024777 404017783 586455182 946567473 961232209 97678362 702566139 338006875 875070160 437996340 467752793 245130528 649361898 938455162 958725004 547080833 997530052 319047833 480203661 302784546 475197081 5643552 615560421 333355214 627090335 684297200 700613168 471058001 553583158 26380338 85891681 356653258 905277278 320058009 648356311 617057540 806374562 583019397 868469105 493832938 927371331 315287156 483215082 835876231 989199862 586830922 824568977 237143834 852082670 669359229 811628889 227442757 298881381 587097406 714755067 7432399 255040260 488070119 707934316 507066971 553304949 304599659 872620146 462564506 633144760 375980994 567547098 606208909 922259928 91543275 636844554 695587794 702268092 933014281 936063919 930464323 969617354 376224365 699484683 85557943 101781617 283782809 870491037 766648357 816691556 41319613 300798188 835373078 931329820 57101352 139420146 481895318 619784282 251702307 331150202 520581118 791053814 247338198 694877267 235090567 240008145 289727691 647324807 762999326 916906863 25229882 914537393 415553339 718655825 720740571 749033837 19234611 585908819 367675105 464848848 769468710 943529934 818957703 988236412 629381998 848675085 619874000 898291496 702626412 816837914 292093624 917226622 197691022 616473668 343054378 876951685 362287098 985201829 105765840 439406613 957595018 960043414 354903465 536262276 345958664 943380473 183822511 902029742 179530937 229153616 463135103 753364639 643926664 670230648 344202164 747626915 981652879 989974022 411184760 763887187 961392574 961553931 658987845 970784208 804783285 857529367 213691803 961123816 737450199 794424718 460283196 731617060 65532661 403943543 786284932 844858372 722667046 745786164 68651422 489719017 490536666 554170840 421152566 463451935 743401384 960338722 415114089 947064777 334273081 338467398 145382979 357116522 423780439 984770711 780060216 870583668 807622116 815927086 345961906 479388383 844008927 897147067 758110017 847825732 979234451 989563883 846387127 938983036 94987782 955434924 518656106 771468135 243629570 512493435 617695548 776160078 98328890 556747691 891516270 950640134 193011456 460701366 567098492 797799194 758611731 865166331 902388957 963189158 396409691 710960765 380367654 410805664 193935708 490227797 995687621 997488852 133490326 222660337 893032916 966200791 633387155 992600754 103806880 413876123 159099861 597203906 868228440 898329896 343027620 725886517 753475898 771688783 461676371 844306320 519224022 630236100 731729993 855686582 715822387 864320495 273153477 796315411 136002729 160361871 757511057 762202950 201663454 300891304 155529220 383191927 999743496 999900051 54913152 412780130 690244578 953546182 383064800 919897842 232805330 290581788 310012169 359245914 405344142 819588920 307004842 375110516 107047556 568772560 1974560 616860630 503494045 740710267 25426941 157706284 459810121 921024300 282256690 492330636 640676707 700562127 660205771 928823445 626973986 760829679 843938487 945351674 211483326 340040918 518380504 541564173 975575598 981946602 188544696 811275747 450686351 567391248 64641160 818744342 772642240 974695115 301175238 804201454 978140413 992401307 731589456 832042540 938975433 992412761 638985713 971229591 103306566 581386128 331295660 723095682 133149140 600909124 479278453 885721499 28897772 187053781 817595228 892519233 748953070 820859405 920075583 960263445 610789179 924514934 756936072 978076729 451256772 622219749 440290469 724226892 170107808 934500819 316545211 893660339 694775644 712221172 642041359 873104373 89955179 299743061 431063849 871345569 435064325 533623832 137156675 183893066 848869021 852956364 943252911 971783052 565601745 768586723 410078133 449259238 987472759 995603732 295180593 662041232 926778678 997548098 291748084 490343537 531822962 904099938 973789661 981697936 453236840 995742975 884858627 964943251 238094285 803243783 878357526 992448626 580522555 950138162 266872575 733434564 591032276 935679999 638676715 757482737 525819022 964054541 139081185 782935179 814187209 910103264 480328842 647656999 748048207 862208538 76501235 268435708 159838359 527145143 268514174 731008614 700914421 900616817 48676322 402035567 245839984 714116328 748415289 913952493 1 14582179 407665440 916091377 611718892 745615101 849509979 873528603 892133408 996955782 858648814 902267640 872479347 914990780 956172026 959331147 448642333 715839737 106543789 752625555 254070929 342385012 923843941 952334667 839191503 998403577 103622157 641622393 357497284 835568565 143260527 937545704 570405202 751220687 856026948 959793874 585750399 931395715 926959751 936666241 935662084 955401094 875684351 890927272 722078520 794062361 165767445 695011298 224646758 297463409 343360526 640249890 673821949 944310990 70158796 423864511 131768590 778658765 727784377 977265489 952516255 976946106 648485159 750556744 809883892 814064929 723252608 761118151 1 174511918 469405312 800875004 313123375 779997392 548759742 592209116 348172649 982595287 193822154 985116453 368144882 881504244 704349133 847979548 77444857 79135121 408677300 674638111 835946319 942318207 628885396 637194896 109512358 559558891 975284376 985215363 616523198 789273674 213818671 392842204 305594286 327416063 935459563 961901878 348087750 348788193 428831696 542766675 479877882 836823737 555273232 805841555 226333016 953617025 82944526 296096229 852861808 959524153 82669732 809265914 557912744 679435878 1697863 904463093 742017055 985078220 62966025 311777807 25418334 358167552 942670533 956047543 779711339 827748138 259590860 579559476 204567623 572421711 102667019 254038496 186234099 681911303 184121932 986890340 468374526 756908109 451671489 512383151 56166463 581402478 411136581 822372740 849431612 886495758 950269516 974908800 164627234 716045752 590810398 952713042 860767832 911457158 243455223 362195745 696772624 859395032 610794418 989994217 199204951 531977137 676365321 915950814 913816590 975630627 564155681 758855050 318242975 675330984 508756870 995229533 353403543 547076335 658730469 994560326 103685202 616816509 714861506 865881399 899969338 902258864 64070623 233172676 500839599 920296674 351865243 507465938 757445446 941551150 875450306 924382924 31657172 441406945 140824826 905836145 618985552 769286122 358327280 393611016 902116323 938234776 439216649 553144210 611663079 955190260 259505534 830253826 581303023 879082817 961707813 990005631 247861019 897907082 228097354 893524431 177651446 785651548 382815056 875942615 599906445 717835550 730260457 862115019 432382801 755208413 634493578 665101473 161254535 224740890 293732134 556054934 937394686 958158675 573185666 902236280 312411708 363611887 382911986 723301237 711599610 965176703 179772384 949543815 233447890 743148637 213563603 985110514 463759681 971966095 954409519 963196192 322336897 482620108 285445168 450057689 864040369 999406188 728272729 933158991 107266597 385294133 204774720 655018191 185226076 691837964 331286780 862715747 191779967 736589012 253381630 657633769 176775695 220097477 537214420 810960332 926355971 967084155 600998317 964737122 556287141 682208800 841728605 936926567 253189639 455161810 210772506 535002999 632518715 832911341 555923288 864201028 408004281 836943238 850978798 989574250 299481658 675486452 351158849 435002099 531316830 785307949 833128654 860385448 408293900 598222922 499171969 620162525 890639613 897686152 942254462 963981033 615867302 950277327 351924940 540260272 1 100505752 106932122 589992713 970742713 971828574 354705372 496628209 681461898 852620387 1 276680090 751817839 978511684 310054714 442157352 419228348 778838890 335315863 675159753 774323494 966918174 422932860 860234001 429886793 581531777 492010027 931066492 598488760 970993512 217351828 580106733 351258836 655036780 28943935 180867231 56166502 660551924 849360093 850355095 235853279 473435969 447175477 544789946 762505103 948326995 77905536 816252403 552989548 684046950 239106865 426156177 933372660 967356866 898951826 923651956 724240357 906245182 212941964 390773302 416331845 928879996 763427567 801286249 24036815 605631881 681945497 853935700 70799172 603538374 323628066 584983882 919473871 953924737 588008315 881514487 808887375 934362873 935246559 957769151 176878153 562702270 352332119 846914096 92996891 423069458 48081266 208635673 116369526 723670975 741440445 823166048 372290763 558641557 558833438 693241851 583675604 899023148 986784254 991659831 699630781 859449937 386141013 513760351 589454760 634655915 365702678 752368139 674892891 953690541 696817487 896058146 926335106 945311686 821803599 865761022 687336743 725588467 443143553 668179752 152878319 885748805 598029898 670325830 552768774 666274844 814188937 969831325 723170186 814346202 914817370 991321213 884310251 909852987 860768456 863423439 33337430 623563115 900037120 918010149 114060355 363090937 283282363 803589795 983574715 986910530 266249405 464405232 170160901 352331253 121992768 302053819 591912838 686110042 5059441 589470836 189169477 198999370 371104680 545215813 621590291 875672316 991194146 995930954 434842063 917967966 133843445 356401957 907255740 934290092 972257456 973096503 812990395 962622436 564912741 975724872 713751295 850064958 998539272 999487377 740748813 761484446 545702415 759969546 882287197 888875820 99947527 609526894 30241700 382740683 45865424 781308059 250175814 747332149 423930359 667518625 1 344557635 428209976 668641053 663845595 980974679 942759915 999655014 962524041 998608567 984748707 989171793 885614127 913640781 348218073 726742998 376183113 613042975 906821386 973640222 166396467 602933609 867342164 973152163 827458939 836913874 837893115 925926113 871163283 996292200 743697618 974172599 725308042 809147751 470375473 870683960 544914235 733579887 118661146 721785305 286425798 902725860 370926750 684702051 895928300 920043469 598157597 735091681 736033219 843785673 50544904 884589859 90897296 358644734 77750189 92620568 1 22793823 86825551 705683864 116236386 389630207 114533649 429648145 495145838 595402743 296239978 524022912 46796637 779861300 324357093 644600744 264991026 333648165 953239210 975550797 44997781 380128437 790879634 971988341 387683697 677719217 911611103 984437841 588845038 896815115 759064683 997069091 828269529 856998383 819259206 837976273 247516989 944135963 294760728 461649345 633386426 897779542 146571757 170172513 583929676 695575568 269583598 527051127 374097590 778062304 260490277 426399222 204237332 213123265 271135806 401110989 660566387 680122033 936272976 936576866 401848037 762760826 310690655 800405908 17703241 122639671 226329512 427178831 255749492 728026804 359880036 550357587 513871173 571031255 48308555 158477849 1426089 602872920 803779181 929283551 768581934 983062542 670886882 735641378 490974630 830962644 640380432 662523480 425034595 797787489 544312484 841194454 757515309 924945154 711285115 783246008 231754616 623474447 829893167 966008828 213713380 387048566 405831880 618585236 716492105 807706326 555544319 654156928 686301556 805694701 591382399 717854200 994205100 994246040 871197004 901661972 438485276 707137430 1 434051044 23841486 487593273 581434618 901756959 935013137 995619022 508243036 581543159 415165222 483275520 736314891 980581354 419259364 792421539 456344376 670304480 236656432 863878312 352502002 816496326 781898903 946415335 311972920 484008720 252775032 916722420 995789550 997259951 597700430 932112694 339055903 759759298 35720951 674306870 948800640 962640927 818828149 878928284 450857689 900312398 430587744 979212095 953999584 996933436 359974527 946714339 877953876 891665432 207001772 541427395 9293448 80692142 335928448 836575653 40814471 858866310 972694548 988652223 93615343 865871447 223383028 372357961 950969099 982287344 560289722 592375205 8351991 968501540 552484787 818437466 518014408 796271125 316704293 451732318 57368303 268617125 464563643 476251896 642850329 881640441 607099658 745055930 149094774 715016631 582078409 969894019 507511448 631334027 938120988 998680177 882348616 924152078 516041712 960582011 368442616 425879483 505786002 768098809 367623140 621358082 339877949 960236528 439478869 985697445 2727786 901383539 345906171 581898810 59648378 601094820 285446282 946881754 673857827 703935224 173495517 881900212 286350321 532306830 775541682 869955212 816872276 875135238 414908071 632165629 754848174 974872501 401177631 901913696 98694580 621187766 82135388 905210810 864078997 929002613 242792510 840215238 526877386 921408532 645063768 982195684 870063681 940050462 552872883 898657428 1 926332193 412854007 844447483 989739729 994544147 52240592 410162916 670486993 980799238 358443280 815401592 613965512 970562932 663917198 895602545 505030049 889386118 650480215 828223907 648831295 727508486 591679524 794575307 488812058 731591551 246200699 419598358 177049982 573144721 660566725 707601319 378871563 552934837 351075576 658819886 646614845 781792962 607401515 793362463 105043741 239964065 646363764 762710768 673229222 955403000 708285527 949025125 382609056 602910920 855051056 869692296 981054707 997449274 267293921 848385551 287441146 597884983 707157253 750818656 394757778 467866840 134270565 482844889 170793215 348087444 710246557 827044990 884111562 912122012 306400051 970737180 717282876 802507973 955393642 971560261 161411654 744518417 817183789 871585675 89510270 176086365 114920391 456186616 798863664 810730435 387305567 933061527 819150960 990434106 271834589 376288587 189271557 842777799 585143506 654548291 89690270 853822396 296525420 727925864 635410698 722833019 381063746 486165535 854438802 924712537 150207825 502282793 569496293 853509748 296016840 715269006 233549982 862062969 796955458 878175258 746221099 797903761 364026232 394965923 54771680 558622095 215914150 383816449 784404313 871848333 768768624 942790793 166028564 319169308 433677050 543529681 627630025 742974107 156763107 626852506 286235809 987194997 261492952 736408774 233492292 597910175 649464127 696245942 437920525 949028201 508887779 700182887 388543570 791431317 419148653 551339764 958451882 960778036 35062999 385839166 751861601 990788984 266713526 866624870 283773028 510406312 909317166 926974150 133010431 910692865 239926940 661500479 884184874 978383208 961059835 982060559 268683054 513955458 780307025 841482865 642043617 737172469 294220503 863542987 296855734 565939853 318589502 380767871 230785328 906468396 277914677 921029635 357540160 636058429 938159782 980915817 542063307 729889571 263071512 608107751 982392944 996164669 305894578 804055452 129848057 825948258 636740225 947940571 180095662 896746040 170569412 792508164 787135850 937863109 821036143 901141951 177853390 185339253 24379082 30387908 815549454 925341389 868450389 898131332 744261661 926935908 39977364 294791499 679913109 712099556 1 101105360 80039230 780963610 354665795 871388695 198078322 962408444 723223786 969289505 159365476 199736698 842613751 844033786 149743440 378983575 125458701 368806699 435628473 672026691 778577034 931993338 389845296 492668226 979212492 999800765 145074624 181861826 697233500 863367829 592820248 917715495 705733289 728484818 507339368 756258614 758423542 916329703 70958463 952785701 486869879 543569076 167109003 403427971 343345851 709748308 577708997 881362676 73968477 107461230 739860275 743232018 606598291 849274840 577274044 812395796 368667080 987817032 104664406 868319616 695392767 885652128 246765714 318735273 113708354 329596203 964552129 983854060 896279236 919707746 786916871 867366539 7663202 246863622 466750853 698665228 659075719 991323161 859276928 930372633 912445206 992444755 82991467 752025733 478217164 674794633 496401453 649274191 493891783 665214704 952845145 978860685 50085836 947017449 305633928 464372473 122293485 339417949 173548613 982761882 249696567 732830509 714511110 823359772 468604152 973216352 213875643 697414523 971866256 972103655 90640996 972103124 583917641 659770047 19382833 325508171 581963013 712789519 504116561 683722828 337576763 864813172 442546488 713040591 135396335 600572759 105010556 651573065 776188380 802505415 521174765 848242477 500713897 713774233 874389400 881126658 552538567 579739292 87274545 102775304 446286396 895301053 584582648 690664151 968821433 985976636 823452442 950723236 235600798 755438465 900149899 923880069 37609109 824056666 791520508 961847418 978021852 993132698 785362293 892409665 855340953 926632203 620124044 784581912 675667511 902264589 10177555 129000220 1237307 13237170 124495718 307428652 761071920 961393903 207416661 584656112 1198455 648197056 643971486 722735984 578889010 903136164 505186889 925149173 90345372 393893623 830567819 834077265 494641172 599141163 797126906 839683565 71176995 425332667 641793484 791331467 143571622 306145646 107795162 135589871 426383548 610460010 103020020 435932283 534943427 882027571 391773314 826593794 289526445 529900222 883704404 954730595 510203620 937083313 414740210 802995763 452715938 918235473 898279640 969335520 927966470 930120234 261268532 833319096 836921541 859544299 592682428 680475023 359089159 676819088 333457665 822577367 130772848 838183264 584205791 845029275 727645809 743068802 912142251 933460318 893240011 914178671 214725276 961533524 213446000 554896105 262489545 739412846 816357209 972365536 394418908 691103463 165936579 358486978 446103512 870758492 6596717 191685241 879299749 960150922 14297456 721301569 347560362 495405017 852016513 959928307 413634681 829838754 892575402 919993399 822422062 842552096 716236177 891622738 426221880 638413490 137556176 441719134 979967488 982666450 40761443 632540116 493612114 632405676 1 868627245 516226372 721609525 847625272 865186613 949107088 960223486 626527893 991013613 956285622 983228249 813587643 854680807 818128352 818890122 165926098 379890548 582299351 602477093 48476648 633457787 706341989 958985817 795918367 824630859 144876099 790693277 238981751 825862837 236088903 512897122 358509768 857779910 195498165 937191793 266386580 651779862 468222034 481320535 928654572 979548962 623716997 646082266 427202591 734869209 192521408 458125550 365487608 989280485 135438852 853034897 607828173 976174102 560826489 910175611 410560631 871723224 426810314 498956736 830587102 838390080 828259015 912418768 796783863 953673341 11942054 196425304 912807343 913614885 330424366 406517912 842126489 989077393 687792379 793127280 417282917 737819604 105785880 690034143 257252208 925127341 939357387 976184053 224925821 542076471 107070083 769719428 535482327 821428997 861875197 890119058 14460919 51041895 239605308 494633437 436377001 790995613 563308311 733983435 887847984 990822287 201362659 504410436 231134881 752477598 259840431 290556531 616397371 922445187 224321350 859863970 597268099 788623559 841664387 905793922 624774639 644754542 845840859 918148956 363062317 416402591 466287302 944771138 282695268 458123103 785468732 819652291 289669063 345390164 735571937 782929837 447200550 846130125 695613493 926765582 344998291 652232699 635418943 738894189 210034741 281486143 974589999 981713413 375962405 506120615 29743165 451892534 734687131 821096764 39506055 472702459 674145959 860493941 991717506 999933453 863783905 950580280 617597109 712406710 529432009 911900310 946931760 989590932 363616741 414477433 697504308 924714251 735124779 866425531 932596289 987272258 219393315 940365959 525685674 939824321 450961456 480122843 564422283 710693097 336464037 877540144 768144496 966053012 869093688 960937143 935973823 996298946 639146714 780692016 373349529 694319171 950180742 986894414 180753699 184648024 289049631 291647962 644391916 744246134 385663602 698603916 357292680 555955783 626960772 784875974 420479267 723540903 371062681 896694408 910163679 944220567 455483714 853297195 270481803 456862025 210082167 264359957 799933904 853202272 910440970 925130262 819333247 950245781 959606590 979314698 709441362 852312953 22428561 815744424 410160145 567458691 228257906 766662684 414041397 722852697 515070743 831517202 730213680 813647784 41792474 476788759 691642823 855295071 823940826 859986491 981321690 981370932 942739051 985175304 388930814 392143047 103256593 315696250 407825233 540769661 150075589 854753277 539932353 676903200 840699567 921431965 933169516 940799429 408064387 431039967 121510975 536280952 83689855 513171722 529476648 813444843 786477231 840064742 755018029 896207269 439684479 787781246 551623652 821520889 355702751 733930607 405242181 486428344 260715918 601949062 63260112 141162722 678532248 857078947 958355964 958871873 373099474 736409282 835271668 909676514 893866483 915836465 177788644 838344723 512799017 764943691 19897813 180623585 375721220 880841253 427467781 973674114 775482183 805347263 981054077 991893526 479199197 874463453 744309109 938781480 767476540 888961207 154212947 420712497 433954350 867298044 755229396 771378973 798315358 949064611 837416865 993289223 248311459 979481574 363332470 425144633 214216356 368297347 423201486 476176334 809238973 921671641 205375467 320662366 232247319 761938256 656401264 775079664 562760844 711227411 189016847 546449622 556990530 643399333 341345534 750808316 128789128 410179954 602951540 796658040 407980938 763822501 577235239 986400380 478676563 950201097 517779743 763675071 146150630 242330377 427456112 842287697 622216000 930527875 167106522 847888971 43132344 795173190 61358359 386499869 680986587 731174484 424361019 827441630 33610204 936793241 586266094 752642314 714384167 916858905 238573557 898761785 62815323 203217344 210547558 579895134 961706429 994708897 613434529 834618780 506050164 533023711 793751436 803574512 651528299 771381461 187722790 637987710 327013780 905174447 117660344 930773644 1 24449687 792008867 798764324 70039711 499935229 132790068 602143415 466698139 852146397 787487715 815960354 280329460 591051736 777917205 960249662 43112168 991832579 384984080 509834712 366844696 687433144 166674136 547750712 777674334 929445728 427233886 785514526 59187509 623723810 535593668 850875585 189145246 819458770 83062338 582889158 392903527 968991663 967919278 980708633 218806924 904631680 509277880 985688523 171491203 343013845 841447312 879506385 101684187 152292674 103850342 681534849 563212045 758466560 446156519 822185006 178565448 532661593 306924722 500382134 674292080 736943476 615516422 867644110 475321266 747229100 827511597 927830336 700860929 907769141 709229464 939578762 283199276 552237052 671470572 760953542 581282800 856294979 487056287 870857958 605580101 726989675 544111005 974316212 507044699 589340275 396656859 931917912 293780835 382492442 415398289 615981575 249402531 656467023 440268709 730478663 347164461 640574743 379501271 520259459 462815605 747620328 168829611 937397044 573149634 734837213 78122651 412105988 576552077 837130541 752971779 862009477 439552535 484856839 445515898 513508173 699158223 840181143 860583076 948062929 801452337 937216314 815362635 921421562 530174588 617004803 899166131 938579028 388720465 455577849 754893085 758929990 267190652 792262599 592419057 649535123 381035506 456759680 197370251 872875843 560701104 739351857 443046076 701169030 847730059 969582652 668610838 816287534 896253801 928158074 193526766 503638170 255928107 741748393 941649017 982922744 271526755 363846129 246839941 734485270 656961871 807727916 1 677378381 444494032 907502630 245916369 296237529 413234419 524759669 690356649 717739580 980517725 998244912 883316553 890028865 924922447 970913012 744221449 765864350 827432870 854527764 802210015 881209561 508749185 941743074 893135646 914290027 514327252 842082347 157962497 529668123 829878655 864753210 155509693 895542595 969995601 987482359 752713889 969563335 89572326 429739452 879051374 939352746 625900736 770235228 134534724 644126330 545313758 555555055 360574067 489907842 128309563 620190690 876621477 992988217 82111616 514750461 334626791 678007793 193172915 451854569 333674856 976259965 703781620 866646223 696018587 821389560 875856294 899474931 784417831 908085538 741902894 990166960 597794963 868610557 288930476 778805072 709035217 977104429 498238700 893443449 974264814 975997782 500194926 792486313 366140345 819029534 146377768 675686083 108694963 712351777 522329507 667851363 184704310 291937658 319025606 625698064 892891224 918500853 566519238 870342252 283870204 644868575 705925495 827359504 607346199 848766732 342485349 484091767 306815337 607398057 393699381 551148442 156644415 400908351 778714109 881762722 114560710 813758606 820357305 881591941 171138441 424212163 17014507 212770616 721161590 782714324 268844019 319742451 664162476 928927831 239606727 919946889 888874626 924159118 242004073 610238867 851594055 861244934 100850086 198235838 12288167 870030346 191854307 517394087 124516123 605394064 1 664235201 80493959 936979727 947968035 956601780 461493340 650772615 242537334 422320401 706569361 836197747 779442837 818421765 279298536 498459521 149926813 950253231 736052738 736488016 961987982 982815357 606492735 608708063 358413699 935288857 124032516 514543986 1 278471446 902766509 931294368 74143243 595067787 863619763 970335727 718886677 861280289 759035358 774562481 843442812 964471480 885992736 971577879 273761125 528560580 379680464 678371033 34109884 775459595 611435444 731045425 763887375 899097911 54564804 329860229 727884633 762236321 886132322 997749632 75817452 231471155 260300775 822387843 661482968 824653309 542807691 720124874 17985315 875608128 817752889 918083503 899761114 999282036 596189409 686959168 241165907 438378595 642572111 823295023 787923781 927623883 617449221 899613384 936160290 936619214 253268355 710695798 48314081 244973406 119562910 787913774 265915707 445675117 870990451 939656073 463615099 564171097 534688341 824569907 802999393 824320077 748496616 802658019 875714925 914481839 252658036 949509583 552457033 963220331 58513253 811632510 782942773 846603215 638396512 875307994 524596495 793988983 965099219 969308979 531842158 763398557 990930455 997513051 933843312 942848129 384914068 924327662 278985254 609755394 407782177 735862284 645294346 872372350 212358117 806759928 58925257 575866097 185999134 427789892 382510415 799101871 89644454 729470157 479110498 733365046 668219074 806098522 954114636 997472994 242839437 814195069 44935256 989247886 434484540 724300259 686839449 978013153 672863257 790859172 669820691 767400627 140705870 569564859 148647741 959636584 431026638 707437445 498662093 743589546 259876061 805851231 11885829 298652460 282786724 396108570 374105733 860630567 171311597 605489148 313320625 985680043 167409580 215701073 519944135 616692924 632814514 702789325 721781646 848186824 535591235 792280551 900682799 956496234 572325640 815794877 305024580 626153527 520865648 603789602 991916539 997643014 152117674 640537657 829603682 976083688 910631121 984236230 857312441 885056350 434929271 443026632 896120118 959057001 96285457 217518817 824818244 969195292 473400286 793205343 465275479 485851418 874498929 884476381 743855907 848380779 170064203 177788792 566562814 817803882 1782818 413053080 941393701 963368739 754741740 979453373 700591393 766388539 124187365 536516835 196415232 460448328 685543749 972386059 638394367 703990912 531902256 883971811 163924898 179185197 836301623 946844133 65299879 477136505 300501149 548130318 767882790 834598403 120323352 322016132 246786875 554429205 919219731 940769570 474228788 593869439 910069629 935912844 937824825 985826033 902172213 913070853 50834920 683054372 37534863 875589365 548856724 966918595 587026915 953156494 870592781 945675762 734372907 982475643 758948980 841236330 813035761 918340996 817517784 940537474 280073725 455563762 57763067 229949736 586643202 776792004 284015472 725489997 166612096 281662441 250006745 268370417 876464659 904725280 566513505 722367527 507085009 598204135 438650617 938171547 756567685 889213345 18664209 927397463 466098260 573296915 629619449 878746257 351535534 420064076 284919390 718887543 434617371 540292166 516364415 904061923 748499213 969267844 891766032 986391743 663692386 884309958 783164249 792020684 914047360 989914652 16028456 272924289 679932423 904974342 887311237 994176128 80915138 774947246 765218697 977744755 273395073 665833925 822578615 922714719 548824064 913443685 135818623 137788401 430450771 592597766 788189348 901590984 468088729 858540693 681327338 936597080 315034646 834564579 15802802 371922382 79667141 920138713 891646141 944529791 375872314 823906693 675722797 726875541 541999131 571285565 570181136 694531455 344791071 967321988 471464008 715181138 424604330 463951662 966134016 971362670 845733767 982985224 102837672 732172169 504420285 944363342 797386878 873660542 282173585 802705362 999911315 999960163 678644128 721724504 244846063 306250122 434337425 757244306 848799369 869446484 702997478 871688290 672447548 988119738 427019307 646610898 192520244 562481707 14137796 594125411 289391469 652901844 623515014 787824663 695161625 935433552 473189183 845472152 62228236 217941518 633063706 830577811 322985787 915690107 119390774 186288804 47431641 829193911 376397858 917486600 246823739 636971022 288870448 483883777 786652144 991665071 720932981 968529381 1 200080793 93097427 570936218 43047797 353187288 984222323 996907700 768377290 960143504 7225023 321320549 453325725 754491317 973708504 974578818 449436133 888870409 783550502 923198158 44847681 794822783 45632652 287750317 463659227 518588868 354354755 691645260 788778069 795577395 877368901 961943481 132490853 661196618 381684539 814545506 507933922 855693815 477042517 816042026 158072053 450197438 760051589 762281813 714082416 871505122 30186960 98048132 840302554 858630864 417975308 488725408 767633261 771461925 530995635 846511721 994119813 997565557 228180949 934073828 16353222 733894638 329417288 807648382 256020714 695424307 498062166 687836939 95043693 682160104 794856064 932991895 812793137 993711325 689676196 731186240 291548176 575557222 169173926 786580086 33852678 496729891 414778383 497231342 534714765 840747977 798841040 998877167 494470359 657776960 735019911 993262986 352910644 995339522 850307961 898607872 177146765 222331875 422336012 617669438 860191299 877602934 974841987 990361013 835218653 942690237 90245464 522079479 266371776 970171430 903176165 996638353 482710847 881028943 292500486 860165055 163344758 596702172 748152216 912812925 597157735 846576297 125986279 690471016 53826863 713409380 73801975 772444514 645644410 754777526 327484096 938493539 337094978 640834612 834893627 973521645 860940289 908768971 632360654 795487562 429638697 550725018 985735175 995245723 357988092 369224316 107471139 594203457 157867505 393526028 400855227 571539562 447605437 832963471 769950364 928282057 569114447 788766539 568628339 942201295 144816889 367912616 162766411 382544404 626424033 929979773 733167415 780050090 145842723 357546476 936381511 984478594 771804632 799561484 790961942 921799226 371677318 438373310 163154306 697766820 3623536 655024823 44089527 978713943 1 134813229 944745089 969133585 539008948 874327969 897508000 974343435 219331546 495205246 656512771 798559939 361859304 515184096 38309694 563993555 854375623 996539504 952914127 985909772 932376198 954508905 410822677 499207113 920224544 966824707 960064416 999138148 488355549 575388325 827360809 831650212 651588483 910136956 458623082 785390923 233217574 792911522 976686712 977003570 545586523 935877094 461941986 673423343 87443992 782140522 35837260 569935116 138422798 784454941 389136401 702610466 820115648 827337396 122605445 860022133 875893405 949881484 281785402 852367649 624732649 649839036 963037416 996227786 838680403 934904422 788415599 865984577 195819244 944320636 748667724 996497477 835736789 963539260 767412191 829041338 896592984 944270756 632984259 969251010 101148958 967879085 482940842 649007831 19194879 495003998 52443040 980260040 702403746 931315724 109969762 725962958 333700953 763295817 506403427 691024792 414041319 996488814 594074902 886151735 226811048 891917398 898628694 986036707 132081487 243781127 701799910 771207897 248739103 402494522 500023539 500517927 91343108 371006800 619321923 991122169 900799773 946300935 102557121 160308436 814645438 978175257 605002696 884263906 474822882 481605796 44470504 461690387 825671261 991236830 562154948 589892947 532068944 609285561 807146403 991698707 8024739 24413838 67284204 929983435 670790606 935689021 211475872 595517027 190813913 530228684 866120539 966830687 489006365 956327543 24686307 46455755 977494142 992253084 827045851 971605355 294819058 694067303 61183910 664579553 59225503 127083241 650984912 955800832 885230951 907750931 861231185 923968271 916687432 957688230 707599419 711737362 247255569 771540272 669539432 956262038 235006889 565311018 982479346 990197776 626029517 874581560 1 656259280 60583814 343018095 217477292 560077200 253221476 588948664 719068057 883469776 273990232 553335874 698724759 804700815 290560890 340903672 390618771 536240369 303801732 482128090 753471527 977655746 37860659 802750957 230336776 767205677 239514830 852661272 657946209 774501336 502568843 631314011 880174062 963229335 769463916 927640033 360861559 873839290 353147377 696620648 910842077 957490199 874091794 944372164 212034839 269081957 242538510 412408886 323040400 627160575 224425410 569980079 17881587 467116517 976561670 982094092 277701878 576432340 694814133 753703532 720533996 971220860 270656667 472130572 331172335 467018166 314424477 756016210 596623349 660238855 254600850 272163970 742669715 979794314 858242072 899146837 592699781 836615533 731652042 962148795 680276124 971333356 569191554 708214278 149705524 198620252 922278858 959269897 88650167 346270760 746900554 810892926 675165522 779053106 300726068 970113163 212698924 403482779 366991447 683904872 809540537 838818942 607340358 999943239 516159263 715562041 125143614 960040323 209853437 719439189 554432022 584202963 286259148 971158025 787454847 807750504 240533419 711266243 596855449 966727983 780282742 959636942 333927387 929067673 266815939 798438584 373334959 931954483 579660843 797578042 886468655 969547747 38502031 885779035 907261148 925864351 291341258 542442078 207920508 525826137 35400659 299804549 337650140 637458047 207117703 813140449 138409027 620072370 898556913 900414432 371174 583076007 115427448 407466896 445529742 622288842 987001881 997669434 462507468 802025218 301646844 915421516 290125901 425105793 956582676 957764506 472497409 897293930 274097241 527921785 309839910 709117034 849728782 881719831 347656698 998399065 687611396 818640836 828430422 964883230 797078981 876157962 514994696 964575017 923882414 976087206 286936932 642740910 818006447 962434262 710885005 712801116 244884734 724922021 293150967 606391216 788824242 929538554 411219919 671419073 535950711 732919510 645490881 967042407 88933005 692708075 241105123 744514943 24743187 732155873 505821072 597909548 7060307 259014628 544032291 664280237 846538577 864814305 347321052 595828752 597120074 743279599 183816033 472137395 434614615 697772598 338370700 920428566 677723689 773467007 303168196 625077959 617132280 942502012 348230932 811604262 176424332 457763852 246814559 399183846 881658064 974642166 167280335 174991551 150700586 811780532 427250302 449729801 812767751 938784375 963688780 987611489 634149346 990443007 586035236 803042178 192689972 535762591 185740752 540092068 791106012 940355513 316824275 915361463 91168845 321188453 770703667 869048112 142397709 348827894 134853822 158243088 648894431 765473787 589526762 620125050 394166875 793839452 560138120 655449648 529726882 740737336 40686830 831825608 141350496 406402718 723760420 757664313 738297417 912811826 305725688 584193157 358918560 404513473 311672680 979947838 193954296 676778496 974441981 990169775 344202457 483368264 277944119 291517340 605909445 607210072 954581711 965019424 727170416 782097878 492267858 798401563 800260106 968897688 721096439 952057572 469720733 527528813 408306944 574010653 44228208 493296358 831198101 979865181 509826687 793732332 476538016 539753992 852812514 914204226 565636120 626094774 31184033 868739134 517298885 792698884 925852771 988118628 829395509 986079868 936417292 961517766 635454869 749012129 564805094 906819906 518206678 652097972 386621606 944121968 405171382 814690212 501886798 812341962 416167370 597918083 984811976 996003490 704150313 803884230 544318617 597155400 882341443 999407511 741943957 990429390 805070501 986641191 929175743 938597189 6277266 475882396 803026874 880065367 615008726 715872100 197475220 429505168 614181608 922054595 591763803 712140714 259782777 281470603 90304646 962865163 166209867 376117896 306203033 871105509 259589533 732789445 505348644 874132918 197818269 457357268 172974180 544982638 369435424 736025452 511269208 867978886 512296253 581291207 46690352 103604535 260449725 848030505 434843330 767073400 645564856 861961240 239202660 792511062 241541362 958810915 89785421 170327043 492395733 832432901 140421084 565426835 817840801 998549080 596478828 656092053 422426656 651973484 807385523 855689488 144823035 580470164 577656715 793824687 540597801 811820932 168733570 980508060 206040482 390834041 368966790 726871162 207823892 306232846 978136216 985776826 863859205 999648981 132056813 323955094 238193475 283786018 857998838 942743209 614420000 767736466 602460677 751682687 587600467 728596707 320517363 960527425 95069063 432827901 800530539 868454254 363850675 664043079 15609231 281872003 729770581 800646297 349580680 572515412 578766659 830147819 517449620 846296986 903204002 923634355 9250914 359317165 903711907 975371095 427578528 853410060 356826742 991441902 930193983 947441669 133919959 464725107 981339573 986488658 329158810 983142588 1 286528027 869308642 912189676 807102984 884954678 871211491 941145032 789766430 928934334 945451464 995763016 58895709 326654160 440754164 780029080 998207147 999839452 516144085 932681111 76318498 517736766 861841926 992289232 701513630 820728099 166349143 493089528 89168460 429425617 434254943 777091723 926897303 990543382 485204897 866590190 777421459 888245621 944970958 973526511 816556228 849046298 450935167 903705101 548017486 779388064 682943824 898560308 110195512 594123551 582125515 681366035 461633756 953202306 420641554 760533266 904835570 945283393 937500087 985713750 16163825 118395516 167452353 424877919 815061396 841732106 910821320 957964715 502231902 641721784 325038253 802968116 130513497 517571290 338328743 864028625 512514548 587873285 631859919 711599498 336671298 447590894 85243495 94087569 770763422 859641488 168521112 822938110 808410387 966012118 555448980 743107759 300955842 766522205 991678938 993270804 155865750 828153887 26669086 809616366 871376898 961675871 506961503 721323012 505726389 812744035 145619832 782505147 38135284 379485599 84245758 263794002 140652276 510342586 198728929 572717478 493328498 782434195 279297379 634518933 152255265 699621381 240625628 956571833 819035356 932306101 5964645 214612842 609121809 951498679 306438069 375454680 324597855 505294295 972175535 984615620 903408925 904451229 223491484 741118891 171673311 372148967 921821874 922308136 643409318 807291981 619189173 728002875 89354388 748451596 428200779 983456395 139895083 244220945 297733441 392521942 747948617 814056049 359060215 571100420 455243127 597801354 836571038 921587579 630660999 801121711 150974234 366677115 596075662 623350887 996997949 997783889 469557601 837551955 1 492362116 617542253 837963539 750334253 866588685 286264041 736263984 18740289 863481807 200740361 905607552 583018111 782920819 637326374 900813791 753501064 791462909 208041347 368087258 885646236 955961424 318386739 745701332 642636642 990813516 27446286 663596788 922735017 950348897 658943138 798724066 581718665 653625743 763058671 961638989 258560117 723254866 454237396 826642771 909484725 925092837 487274659 556752636 322040183 741805853 293487968 330619607 219081791 702229247 188777304 491488830 69290066 276260806 990536064 992593047 793190609 860267896 124317734 382508053 847887939 989967553 214534978 946624808 261369239 706743913 169838639 425454018 987500657 996997880 192276192 940488789 147336146 179077873 562354955 867560904 933743085 949706435 791573506 905350566 499014100 751210824 761558693 793600567 515863316 584709319 912381031 940721463 836960523 926923116 810693078 889971286 748808679 808719659 56967709 612800746 142282192 473698920 222678645 769498155 474968272 601434907 74641024 901295399 8424956 735020614 768242038 809537997 271359867 691528280 103894775 284786148 358221013 627059281 782362500 958682810 624687151 994709343 262810223 731198178 468965961 599189117 494888748 872302355 9389582 456528709 890165685 988297478 596920962 740688457 676794920 698501423 416211324 782739324 599812579 893998693 694859163 854709700 41335481 593821060 921726395 921917811 1 963057438 502782258 704129224 786157445 942524463 846687419 873187010 859754040 953702853 937366489 954919918 758408987 878603000 515803235 516247130 282272916 767652136 567681146 997830128 81711807 823850416 519515678 784004387 690530754 839135758 36716116 339792760 456416114 767840457 740959986 838723615 687503610 854561590 100078946 590129320 512069839 907559996 362561439 903763365 500806462 765809961 695934527 749147336 26983150 504496130 688071454 810517866 273199251 602882901 735798682 902075612 752054820 797045289 269306953 874948849 245150433 741580659 646471329 675700170 611444447 940319619 271590317 953653762 220929980 868145241 533345601 996389843 866126628 964430925 505166725 894970735 656584956 790809273 539428449 685199339 932766180 962237826 386604280 475984427 333657020 537958389 565796641 741517287 972878043 975850671 535619336 772967701 531561091 855531489 810417747 831979909 322804510 692551439 332248620 940921579 822515313 860080828 450206453 693012940 93194232 635658842 790196652 830101773 172710109 871741313 581936450 963615320 923287849 996622472 279968587 593008621 551552765 852123154 709501675 812689465 926445325 944714265 361201560 771287396 59995388 893897297 899123601 955438851 947042183 984324173 459409469 591171115 953184248 961491709 373830249 893330870 492727505 812994382 340460530 916549956 626302291 744055717 110874465 849038839 788343842 807092422 476434796 976440363 176782260 417025126 833294285 888919927 177551354 366682904 35091527 656996303 600928602 965493713 191050141 925428589 889384110 978800014 767024418 847636698 958163171 969287497 557423951 577392379 13168666 48736642 58694357 437233614 821254926 946074217 109190538 960235222 953279191 970417242 252996412 800516676 603447760 768540846 508908830 886770377 895989656 961571482 845601686 931733381 994397004 996744093 187542253 665765633 833390884 867519745 579179393 761806930 431535644 912081915 108168104 867722058 286103272 546687781 837032570 882454793 539280476 967402171 612044480 886437021 348535016 539915176 184668319 626427903 159216026 508407156 756636225 881044738 175143812 237811864 302215702 877886129 397957910 693265531 62276248 178390639 646468681 901241588 195355078 364862627 667588700 788485891 730422944 862546842 538488271 878988621 512186379 902858054 868852059 912618592 662008140 771378119 724999277 801198133 802649831 963328024 112547505 796651763 455383789 660821564 525589562 873183327 132650591 767856470 504988271 935448018 663330977 892629611 669607260 991252833 109571343 862294299 818691915 839752515 910977527 913515805 50245632 289075499 181455773 268798185 342582539 937294713 639693877 988362828 745070193 885506345 712647298 838573229 610993988 980208850 120527307 385296414 745327014 991969991 162134791 490072914 345598847 473111947 771351319 844924551 861095433 924580691 217789860 509042980 167027788 674182491 860841447 910631995 79143390 487669062 614944033 740557368 390103361 562887456 576931852 698924940 215057567 595892622 547527046 624694130 263278245 998641666 425788990 514942616 127755075 221523147 134921996 177679533 807875152 849581017 302862642 648197037 185997123 217065432 659979382 984419579 163861570 431088944 983965569 991829087 221449356 787554445 831910984 839752300 58924381 448509762 477359175 626807962 150498649 599782420 16854714 924893243 513970351 613819184 302067656 511854318 995733472 997136139 407727635 595225714 671029269 970406779 741066472 885646066 646201831 797714310 576577790 769454982 433441575 488266284 997160417 999822833 729725992 839717861 417504598 749197672 842962277 845015544 403387505 432140512 507042542 855964383 849149448 897636140 109141926 937071365 218715147 654793068 25631895 62432028 294137378 837936064 368293764 939362600 318806213 563353163 781788350 959315335 410686257 696511005 760061853 797259449 230034788 822493621 116125428 698114301 40775158 615290853 585404603 912913487 347401043 485910415 792081090 961135596 332799203 703315605 752521001 962924641 136127032 609794202 741462587 833205526 260819549 402103746 791056284 820937200 138541161 463267490 570215955 607869638 160085437 759486674 340556902 744495569 480067525 626296903 284967330 549998748 435743093 459687194 497796857 561591734 151070247 585641356 450633188 897406187 237843976 257231491 865975208 990647815 173517745 464481710 130085434 334211451 391633293 422647333 750350503 880483939 247102891 524524047 567602298 585791977 517358557 880752130 733715712 908704471 409291293 645337006 701507356 941381597 284620853 716527218 796943552 855460875 681906472 931308179 582850005 976996709 591737384 848334438 373236458 735467976 391766733 549513524 597549430 736842267 796276297 826959703 186690730 590016737 586024206 812082458 84498929 553564258 407684889 615134217 661924794 847146296 175504765 772416034 556198648 775156852 176242649 530745608 308787665 664532343 140885872 157418587 454503653 707194441 243646309 290916214 832331565 909170691 683153443 983160861 527691344 888174584 728764415 779526306 864330527 934030824 718951922 863901711 355587938 790455929 445957882 860933729 914321702 947449002 572772353 891085732 398298939 793188039 934431207 959840908 894667564 946503123 179741480 927915812 956075621 989139803 137730291 428288650 758328330 998447498 952368474 972642739 316887443 702832404 776082831 929575756 14630589 628145524 549162605 909847205 600616329 749726563 491116312 723792464 23147570 47262569 967706176 979649561 49923325 147848288 772419986 980148933 980965516 984402357 92041757 809319619 237887807 327407982 663621522 873215299 806556944 906832557 25192821 306561289 719431317 735163547 955526806 979047469 352517421 543573979 325367845 358843794 976566295 994720273 735406342 735645755 951159383 958792319 59738890 912852787 657082694 787702853 908989889 967649081 64782152 985853404 851068556 919999418 638687239 702908294 105428697 355979294 428607801 992333102 254458159 455208198 266454421 854726067 534669244 661393572 498489466 725546975 622548278 960176156 152411828 407714405 148954500 552460083 206636710 869608710 799882398 841496031 662028155 699939526 744109230 746371355 332235166 591075161 457151153 966941842 295845897 305480408 461545760 532826499 613675678 856827764 789082486 802600302 696479898 874795816 87093174 565751896 102563116 941518163 593378861 909474596 105583410 835543938 608519026 967162013 190199747 582366429 342018147 558288237 991670337 995073152 312648159 393807438 421983237 889108192 655652838 662101241 942643508 966865870 931156086 949704512 2670001 411259540 159622141 175283981 324123811 424278702 182492169 639558031 156361548 822244252 878405749 926337828 792648419 906504372 43662328 399438528 992831628 997262195 856470896 864115141 147406425 688253863 424737113 745793318 361599898 537974573 562164007 958382534 635029068 962444151 831034369 925255657 358671830 993927565 152267422 647590115 21832325 302737244 527706939 644241915 81542796 594017703 555722611 662244428 860544143 949673611 938473471 972938053 372634065 709542692 605633492 999311688 814416243 867587835 461156497 664795607 470317375 986053178 845561790 953325133 248135636 439938220 1475441 101928936 732851506 985364844 94169585 880894760 15761223 825519645 302786984 665121516 560275937 692094406 151330232 395847503 684774780 833646642 925523800 955950251 850115765 984312144 816946674 925706285 570650492 703090539 93216143 247200076 284680860 605441985 765650633 868406641 931507726 932926421 898389093 961326910 970727889 992238586 168127778 246211233 7132990 844199213 930136004 982177462 1 419514737 623571194 952201767 84551605 365948526 100393998 228387804 6919737 142830093 565902774 644239276 304828610 439881688 355566520 856986823 644276710 995253407 641797077 991924400 321653781 657841436 927708177 969343737 442247579 739721789 976375586 994653565 692298075 807364466 419635476 437517094 864162365 912744715 296862915 774636328 56972904 971576893 32370173 882330957 575137518 801264594 662058368 804643762 270334449 735792397 517736997 850257737 555504483 689092643 596202857 599285525 13070147 929353174 669368970 943891970 567208701 594545428 489047097 582786261 74040523 481411243 828876898 835106203 453661506 934352978 163799984 371678145 746177429 886831923 905216041 978453655 163633907 796116544 635658110 696131287 187833279 506808802 975727485 976136254 988796407 992354796 289255725 884583986 771295471 953204344 364660628 390073813 967280480 978631579 333788669 545835642 656071457 954962768 321205809 735787986 16711520 723801815 588019594 997552823 474214163 922452827 604169069 903863609 752853447 862161323 111838628 976823244 608650463 964165418 13515568 768631514 676505897 780281712 968451380 987255974 70195918 988993023 369366642 482455828 360535576 913337206 674108943 686410180 298518793 523895732 418336224 789382277 388188038 833483516 163119300 778097612 574801960 894980371 916767763 994746737 340164837 400847365 957122162 981890843 400931959 800680064 892761399 994349883 538442040 938909457 642108596 849285280 625225001 936229255 436427467 529487911 926247104 986677583 310528648 378904244 852888766 948295240 305505886 752314369 336502103 759245607 581090061 662982626 4254301 928482428 49429255 585138279 566736799 809106240 9733734 208938582 214035834 231639284 35908083 717651148 639802135 919383442 393975884 624733942 141707814 775340201 476902078 625082631 784176159 952269916 442966532 735595499 37643970 176223191 918196253 950323927 420004341 599619218 683552062 815561521 652795745 708191376 664634846 734567938 286495182 970509104 897266091 911604178 611951136 955198134 797063786 998699114 583989193 966899053 51100332 103962572 875445999 898067869 602282346 878968394 564918451 935275048 865388345 908442070 586329635 696906273 198419849 712621058 358552669 959801777 728685328 774594169 870335095 893548031 280773877 349125354 236450114 902981231 680286639 983283596 751678749 898102873 849825744 885693814 24815311 31765883 836466739 974631786 348566437 959886477 137155504 588402183 179561513 589161579 521449719 841301212 735768434 988812208 826417550 867148028 1 579573862 857055293 880196688 75938418 195754955 136570584 674523970 196276803 708853008 391227686 567758648 233215949 722278285 760530170 877030301 794344888 909347624 403858249 965654698 380978718 907607079 715691328 756093750 418769047 922456250 631739691 726339782 846935422 973304214 943338975 976856297 325800737 596765962 730818356 845728011 957670571 988855705 283994246 999668273 808045122 868768558 200095102 937649781 575434724 729446919 772014571 795643265 582992466 670188857 33170017 767927319 912034707 947719230 55814813 228671854 355029140 488394060 447433594 860131766 835063386 891194549 378585670 547568364 114341715 995203811 861812981 907887872 43178967 647321584 156580437 496797498 317183696 789616175 399702880 826790510 62157832 771893263 187852586 590753914 829920951 902331984 572573056 757669121 309739911 827335107 775149066 936551124 760402574 960119173 258702029 563979642 425756784 500135063 25626097 125269550 428719290 908477967 322332898 435262047 417482782 514274969 321441399 781176455 733180346 779221747 517340146 939556735 180013058 363206650 258431251 738893854 668610023 695505693 637484565 871634625 40126037 911308201 607215766 892872668 839869195 850684049 323017461 773181394 136976890 414483956 272306071 665502647 830054150 954741842 695157064 967378464 900160939 997815264 62702496 752006168 921881502 974072301 237471332 855470524 200757045 437616684 63646076 379268208 465740865 676313240 867107759 948006494 544359887 847882357 136144053 741020734 706667829 816895406 601439644 934093410 371526144 990582501 837326495 987999166 774581325 954851687 556419141 832863777 716280665 897796294 553066318 796542603 556399061 695130751 457518476 881614299 286003259 464968152 130748382 748714138 276930787 530441768 295762418 766954483 148658401 153097042 889876305 983474045 801186286 963926926 623492331 743197610 761452856 830216912 437197399 687787935 820359183 894132774 845536115 933985443 348414109 722675192 261805733 831633724 543243630 796237446 804211619 827499125 883765451 958278371 400740086 680876342 62986172 701605579 1 729667090 716053982 916991925 150557898 208121726 993548516 996759492 714804151 877928296 248371034 543432392 165862182 194107266 828684997 887478258 363173040 871772049 956745719 993928941 738607230 805386896 352396237 524247173 480730749 561236065 694496159 907830395 807767201 917623394 955279336 964995620 161183176 516088353 891414790 930279611 668418985 731820765 952350763 981439868 279265692 294482184 783221497 907384327 753953774 844649517 921494999 944322751 608215098 753915051 376712312 538942536 943347221 998241202 844429940 999574471 294664266 959044826 282219860 709353531 986017086 997905978 236411557 661802944 343198744 706114891 226839677 891561558 765707462 956059401 747182349 817322995 886003598 964034373 367871550 750658931 203265441 384537123 800233565 817548764 25393395 226329386 319962389 989683470 627092120 931660283 417837425 926973500 717432553 809039647 768240890 948533458 668810228 944409166 298001961 677151682 172543183 805894986 358552506 395802180 111835291 579940457 178305621 300750484 577591978 863229531 428290428 666230507 554410245 576496391 481899933 634167944 491493946 835732490 991661612 993518410 643925307 874542064 789863153 956622682 355603676 484447486 717239710 724309850 152174445 834227215 280338069 791897952 243399355 497247082 489973824 972044318 106408044 575068634 562846237 988037056 322261534 459891254 549697733 649188077 624202715 759569092 858654768 940079751 855235008 887855342 598242491 667209222 478014090 860853642 424736928 624750772 869823638 949423898 330716730 468727478 797658956 813096089 223688036 745553231 868763036 911784224 900433712 951563648 896376924 924383216 866458598 887415790 272051413 886454641 262963317 583167744 807413815 944889025 157402117 653145879 414567279 773256888 799696831 885506520 76894128 253083854 324591158 688261334 346247947 407574234 135036744 421217427 944981375 997159840 125661952 982402115 870803836 892442633 661914979 826097294 219412532 361387265 183662780 522727823 789234130 956851036 727857433 745264122 982786483 993539566 56030893 151919403 313285492 635303897 992032841 994086827 511018342 701360916 288256144 540852903 42607090 804023370 279804287 697066087 88309113 672812492 260038987 998307509 617974754 840395777 807752727 886421324 497140040 766210285 309607623 871818561 985562021 991610354 603190565 812742540 1 207481116 956337991 961820286 455070299 664844314 462875472 819448155 815915819 922990971 86448672 396329179 89316905 322517303 902547610 925723904 148781986 675612303 241300779 736330491 99937200 903286835 851549862 904761922 43550098 980167044 6754657 536082003 228650355 935455396 487904392 697666345 480634471 929684462 584807951 744900808 183722389 975923296 271072031 502220934 413695599 857823460 885688380 993948808 841636922 906974682 424652779 512919524 40280222 147415151 43230597 674320120 248975184 458175419 39813139 160535596 514471453 560714319 438681114 806987723 858441444 942804167 899629374 926301680 957045361 985093630 250453090 492890416 246872316 485495007 940905399 983601001 748781964 791326329 940689742 963918146 701973405 880168617 812888066 939046402 592239247 789402998 907137713 909178463 567557434 656462914 300411934 753287106 455723323 730416227 354956641 790041083 573043808 781483248 569142972 820539336 558801889 711948700 220370356 479169988 686635776 903133477 50710599 98183630 993110432 999012077 552592088 975969931 549717821 902195093 628131431 899592707 166131948 627313429 186915872 438497041 461870296 660343838 736632718 923480907 284577425 791663948 187513730 421909960 777670921 847373696 528723465 791946252 478940423 807343982 91388355 155365560 157459187 469375802 240648270 887771619 537489312 886191549 312854409 350102075 340792220 495905205 665016574 695821943 686533016 764667290 343597188 662490810 843870127 902673031 129576157 489152767 873644567 932856093 228628596 822146007 789642746 889860062 437444689 729774451 12146891 196214030 352202851 487971322 19568056 430930752 650203519 666952899 211092269 718696851 771827766 786705612 521303918 980331995 339712329 819883736 253277336 755547746 564283000 910524763 431198966 856159658 448017726 673475987 739661950 813244190 851354635 948538028 995152974 998572224 5750307 964965477 991344416 998293981 171157568 959685409 547223848 846805728