939 266940749 654858760 973511925 981813369 650050960 776214701 120222890 563320711 563358889 972152963 661030139 770927669 458295669 851907373 335338032 930563185 225898629 338745695 675045304 685380558 419099855 748542858 197207241 809082683 201783737 401505907 522012579 708733621 354492792 898101975 540866352 831875412 942704323 981727921 975297568 977171187 533724144 578947234 464113802 590328765 418422285 847675246 610890771 716374876 226154440 296953361 512157908 557289751 786386448 867060225 265272017 378216257 579324908 670490438 720310083 737986617 109918133 723406279 455155051 852908231 475943023 997105523 960264716 978988582 378660511 785363743 868913182 881498069 485453737 544619419 279301043 506316294 401003094 659939089 416336515 777889122 414987932 764994983 358872187 590501645 128932735 455696088 264795307 988203986 741325635 969131321 669933659 915158977 268532659 933965731 884361173 988328965 499500662 806059389 781075042 912405329 571020617 735235927 348353734 576565062 863404441 871069301 621768235 858796113 583237223 859816951 517615295 804664167 493511884 661006985 404247418 586212033 983945365 997689159 869287493 895936698 373729109 586346234 576847515 583157115 27881272 981147755 465864607 930426269 63887732 627966613 465246965 655682076 61131547 106184360 817548781 939943611 802831980 909650025 512081082 682482191 868113968 948332562 539536411 647231097 878624337 900447442 284692161 993845599 751975428 804020097 614338074 821305532 158961476 907404662 107716304 172372005 745471260 872319120 234674100 719414550 694353493 768789318 894333842 993000939 481751799 815897480 395588581 511851101 643642696 818956200 848607714 977548380 202699922 917282969 491424774 670810241 117450065 592000381 671250506 997474967 415465931 808888447 800117780 875397167 867303845 909579233 546628070 841469427 801157263 873612387 848940613 971434624 232645666 372797634 330816069 971506208 89424752 666171290 103461125 288567773 829844304 932336983 569818124 978456399 956825234 959102214 485046635 652976378 121546725 944345094 691659609 697004079 766840789 992468958 674240823 880310166 758614575 854092480 617829008 797247420 904732967 958059817 143449310 404029717 471347850 636124302 792513567 909969721 705156196 720325015 550640994 750056118 166162580 337737950 685182494 952742258 122084531 560178703 368991838 602126188 823328181 993384905 587116798 638760569 888176762 977123969 720403589 750951743 222948988 662147458 715562087 830535776 576610276 651247625 141985460 647431385 986050102 995695898 543320396 982381773 107367385 682371849 408086136 855891446 839861450 985744300 74175405 444770647 252607949 307644780 290989875 829595336 732310710 995251466 153798282 530147468 463406115 761400033 24215666 315992863 533089557 587416399 764555978 876941576 537332525 919485266 943495058 944083400 732634245 896237563 186962523 480944538 315844777 959384670 179993017 793291202 225853014 398410513 308457657 769977578 52121767 972269362 782170926 987122129 224243908 975288822 712902260 952398155 389463322 884230905 320993950 422357116 423455513 927898641 27783516 237286399 927055285 939594383 159438488 405562786 206675611 831988490 371065140 736139254 449526193 571765783 553692663 807992748 904392494 936285169 666457130 675809256 730616346 975238352 477509703 617414820 920671094 957489106 647003255 803502487 636326423 752216173 142689945 397690689 997021334 998361960 682118340 689678429 141731986 534524528 452877805 766059007 815499259 865696919 437593406 719357378 473032322 523655193 890549639 894772027 690408530 934279597 645282765 772625970 181083057 862837601 645088706 887942180 268050315 871713944 388742794 650578567 978203817 982915873 682584376 892348879 57906227 285345798 119470287 290831621 111482667 974988852 363929632 642557540 413700256 840438054 799718868 946854592 528327775 786470119 523299896 975408161 39571133 194552594 84178179 798891309 582295699 845528923 133674133 462653664 297928476 312610217 820198449 963328630 144932154 586997796 168296419 478325391 519916091 942695890 961618628 998314655 530427973 604861944 147338742 206243606 156580851 888788627 923016960 981163138 361306985 491852430 661889300 745324963 175917316 908508292 226882912 870980121 368156756 802634358 93646888 537963434 61871860 212500633 337387083 463770802 404665001 624373949 798178061 989865584 356045157 630588090 680546121 881120198 271015745 360022100 466137183 710998091 424455254 555167839 215136547 753830085 473393623 507490688 452554073 878851862 409249510 727393573 323972563 820859864 647415408 900990194 775631438 801299955 318680475 474192525 440235816 527610160 79912722 847787643 239597912 506134983 450019837 966687128 223797550 636468990 835690517 869011702 835732075 850584093 149915905 831456888 262725657 922715891 714696840 813711353 729235443 732901714 417891562 568923528 249032234 664887133 341989886 471785352 360801914 480248957 658816539 952059903 934679284 972776012 235144694 938224719 654152129 667278373 197547022 771553428 894377536 978113525 807590224 994998690 161061681 902514332 767850558 828894232 532466415 946894530 953452597 964912020 464067007 715747802 892050498 973739966 488252447 646608096 709596802 764425311 520622960 988556878 984816558 994100083 721957242 803685937 407120517 630133620 236878795 795790028 942802993 979013231 600568191 905359790 553600332 755152705 576120994 756585341 747269868 809034808 173665926 820393244 687129768 787491905 31219146 80923973 547250386 666322601 628542039 857348452 792062941 952674224 338514109 701588257 668943285 976739012 241393904 370823670 496216599 766192423 210051289 335121298 603908250 900436290 892757800 954659874 966445919 978900009 941256096 966122379 393937674 629829532 20206607 174412190 689956980 760022197 246255771 365447468 833695070 882748071 331880530 364434222 428215718 733165268 669571333 932704021 224666623 345528701 721243513 874156090 522212646 946675647 332689097 420144550 965912896 966000129 549403109 937625172 415074515 708235400 73754811 523778038 742240408 885495505 563811304 659752495 308997226 384614036 341411054 828043899 189441647 934136279 531524083 612005740 897131254 928314354 670815727 954708654 719826508 915800559 80089607 337078541 830865959 865995778 467616632 660607152 629424477 705086853 241091934 947742768 353802956 435201437 332911137 863927360 702926639 785240567 10810620 226805357 148681256 430529306 510191105 833227389 129883489 612143045 600388227 868299786 649681542 797361542 463156917 536565630 306493871 363692797 403908862 719769110 549611126 695380531 286185459 848320509 343891120 628789086 228821858 343327257 592947421 786073593 739208869 747820559 434237992 562030050 430289551 939344942 524260353 708587976 491989085 564778953 564355877 637801523 231889265 633187989 503942405 818006925 530542453 843906565 566904776 735370256 831595736 876576012 275320190 772590515 963172165 990966783 541359868 645274940 220514014 793047422 910692816 913590023 154784336 461053784 95068465 931309798 219850468 761816797 358823194 380393421 182665245 916809279 267919337 983080037 226912234 938856193 432518988 685361451 217517682 766927540 39718811 950596318 592795020 677173420 358938059 779332980 116733898 894582020 381325814 595619188 263719329 523366430 510824034 531100357 478283252 772552161 709561491 919886967 743203671 802952320 909059969 999514278 421604757 751352009 388784196 767313110 919013081 988923381 903105579 925547716 446955674 759107294 831029614 940628118 185962286 777487074 985400743 998537990 49654119 378080034 596187497 953222351 149562790 157731768 607949366 955793070 762977590 764815643 24598058 364790024 730284028 773456331 106486383 928296363 782731169 822527770 89396215 668892821 527095449 551203405 147659636 446405235 849052556 928300578 35624284 519114352 292101840 442380597 356346650 479685471 937993657 966288440 391579634 940192450 792280065 876833256 903360480 934404872 670228147 824547354 185593142 983199387 991944407 997339756 787835081 930106773 938658894 967267539 206770272 803369653 751273789 853025911 68883675 156536629 289061748 776766778 264642104 728621849 584906450 630393838 570398103 717278378 947523453 983412751 476325416 711775505 571672636 785969069 499516699 613652405 743227739 897744396 394830804 548626459 168984864 536493383 650370755 745878894 246807728 888193924 139056624 906577289 984056292 990673241 851368243 857954268 776547624 986767602 870106521 956322890 238352167 911247859 11580110 618028996 999193231 999909235 433456708 483998196 407156156 440855573 171044506 582067676 659836565 824398429 970222595 985088221 660688438 858148795 953399269 987488455 632084209 829805999 369740143 938472842 72524383 956474420 631632614 939905845 712294872 837625465 799490391 956781033 850843195 874110728 636708957 727984540 974349379 979489244 705104352 937152024 466673826 708141820 304805989 691099533 887899742 985464415 113206732 585795413 400110679 620234292 985357020 989192870 522234295 817125560 752547984 791247758 618874850 714104164 380629460 544552919 57521316 740423651 536962815 746499601 165132382 924568651 356022271 711794945 29637421 44171577 459059519 626381714 322647939 650215966 573246695 698483189 724553862 951988212 318207689 945098705 600332206 753953147 554823709 793949074 489346604 540966425 886232103 938416188 225268184 315263058 218456411 430898192 832826041 915563013 150916913 883325095 750856236 892198188 291746621 949158378 188360232 741783396 955391466 966633559 718934367 854061563 89670449 187612859 67827661 181771756 110353693 686909214 995889151 997541008 570856451 701758017 418425009 955334128 625144583 807800544 345014517 962872812 259954770 377148930 24853561 377144083 556059073 754024350 106069004 658922569 865683747 962406481 51306234 342169845 590718854 846893332 790990178 809528832 424505485 867913932 728204469 752975432 434012512 907988793 297921219 780608672 474867102 945988782 629689033 952614230 277724741 510994925 428535385 721344666 532883889 735534536 982328668 990285551 986028284 999988614 412493531 754618279 105791460 935621661 644862656 675725203 500019228 942341573 657556257 844345950 978107851 994237782 915480311 930549069 256369388 328254217 581660677 745488831 401097453 776750551 921790088 954739356 184332023 196091458 260018782 795500094 602096804 834812062 124787647 872697371 99855462 143912688 908708580 960717506 44650903 165199592 326894310 363810130 839661244 909970167 543766433 913541662 862879117 984084043 551578163 862880121 592948156 746194235 863744543 993556499 313706627 926553136 118331687 422491622 243565395 650497649 237497021 840559079 318234356 354626041 453681831 661058841 540493441 684787143 58444981 846207098 437744325 448818650 284024973 515670643 430794256 565842231 239916845 622712086 76467910 491429263 513247573 842599206 483596702 627584825 136898843 844073191 901979829 974475449 844402896 982452399 294585883 396162355 140108398 172138320 59429859 418158411 189835719 628808849 940549357 944770659 151869340 328945314 46935630 718241503 216527217 378115775 425805642 591268304 29961345 944145419 759888702 846900309 520577234 531128679 283054632 402412982 697034943 735697593 420927254 728061177 625883265 676720704 26812424 194261939 576031762 838465303 169928290 430206109 102876897 618695631 950470559 970297044 487765292 863388373 204361261 662745012 204708488 859904768 544125521 610312475 432562084 723601756 966518394 993013462 478303049 763379733 685981973 751017788 645767584 742175508 281107916 342609289 810966944 965619426 850526517 984046707 298198747 345159789 765268041 827875079 452465942 536056033 922979786 930664613 818564126 859891362 982939917 987040920 230435129 250258138 59557260 230147594 543409149 547211758 500295768 545093136 915886033 939788075 769069798 951945971 776055820 824476937 36577120 303916643 772475123 930395202 265767370 378127809 561670989 886721940 676873559 936729175 141094461 416568864 195687254 520858952 499626311 737397530 262408010 449961322 460554942 852491573 969857677 974681237 584928686 825478141 235673702 773078638 913076999 973129006 858710909 988946246 195054062 798800754 284345175 645868339 200326706 560817142 927126833 986897729 22082811 267666351 298651595 643379400 378508107 538682586 467714175 537169209 457053607 746453041 326456070 701502754 141323008 735095329 735642996 779756112 339771475 455493790 581934492 840635024 62316225 71805940 480621914 736927475 509825979 727726971 847095442 883947366 892728100 943877550 253835878 254795302 569222516 704604779 351334469 632951405 101792318 954692834 838899253 951993220 916131845 939888376 560786405 569495879 766167975 771963511 738920863 968473134 936720645 979953051 123539828 358655183 59717384 445895675 605369874 967170844 490764181 940031247 632713037 633715568 741959572 944251281 83395157 372325817 18069292 64232747 308386872 421075855 21887296 244296216 868338666 997280956 196867158 506342753 970967134 991187930 225637820 331402521 888909874 921449169 571909130 603317036 599300177 703776012 457630486 707730649 880200279 962081214 166251106 331381571 248875456 637687346 994560702 994711012 918157821 970020569 598229349 752533610 991116937 993264365 931431840 993606052 717243899 947057768 642077222 777058441 410802921 653240855 513890453 771020388 917699913 999469777 313070633 459729547 523229794 844771310 258933784 902913292 122663492 353263186 83411502 672889257 778108766 968071815 26746661 100346718 270387114 528591661 814309968 909511802 342275137 571929250 367857418 412824772 977148047 999299163 49766288 449289987 362397177 846068146 113209818 359268357 668974135 921489602 375417922 783262796 902522574 961803677 735330203 761661426 79124271 147293775 751970449 936749532 639133807 695312053 489874796 888787112 683696040 731952085 276296452 945743257 307423526 913158130 473937643 705724081 598164038 943329416 297869783 877310687 484578521 819085130 113419643 571299058 124320504 303736000 307328631 355894696 332966110 421461747 598576213 994834381 546454799 967986327 350458014 648255492 926586225 969782068 687507839 864478587 754185771 986244437 64617536 969620243 609492428 963386452 408045320 869173598 453943910 459859084 959391920 963791913 609962346 802026729 387536188 802151502 761425664 838364632 159267435 753665608 954011705 968839428 493011921 684227841 947342118 956138378 333092182 624841025 290439946 450166135 684789636 822692637 640374304 996219478 915165691 922344533 288432529 444067672 70915944 693150197 264539740 566575135 168475028 793118971 332427792 778531515 227489560 800889635 902300251 944600368 538286998 817401075 794333812 870265454 61855349 214477813 553258277 637213816 294917423 759903506 765107152 835851316 902847714 936334161 576902620 967130400 401054968 410897408 283737069 410183122 756988263 988715843 865835005 937555071 678653723 836647365 742971724 885557411 942573984 957960056 507561465 830733382 271831176 637572788 258907598 697019587 545485461 924846189 279653969 323226406 690180423 880845731 279145724 885692372 947006782 966109899 891729343 963276800 66638464 209140640 144653838 569691180 529213717 770223328 306545753 791194463 835934998 873654585 247032511 451824125 956721006 965858028 692935851 780296689 506367077 752908212 289286218 305742338 940392629 962028023 621951224 974170650 770622875 810063742 583348691 716285110 540794685 548482821 508253550 696888535 618139987 744105686 792361546 793283279 216511497 375197156 899516388 940227694 543186839 875805163 136292039 702386024 19273841 949375025 933633810 960270214 493362511 754328780 736220759 801016552 367807937 864379822 36475404 781899412 506507102 851743102 172314697 324158827 41160942 234216700 105957072 753779833 212697433 688876633 653441247 839375480 462547379 856698503 564962576 978108094 491756765 531692921 411452917 493426452 790292032 994251623 164563734 979014146 68851588 725925903 886068830 985598819 215990748 918957906 966644746 979231365 466686066 538005703 230337890 622882735 315299361 485280451 697856640 853280628 822590203 922931754 26794614 377992140 642561993 879358101 969966826 979114051 596329594 864286259 849782143 984719224 691544504 983189068 876271814 969409666 333717415 383309913 491864677 954409399 296827207 825234633 735393838 788352668 708684807 937344420 181729361 926360958 995286571 997414319 321320023 440980055 909975076 947326150 120665154 635091490 334478756 692740449 213999978 985794002 182478172 484844897 313693710 594672685 228363370 692257778 322284060 697869797 645874653 898569253 371895522 700282253 547733763 769029229 827913410 944397581 797644673 862156206 349157089 420637901 360728397 761054171 437742590 879652752 436273781 842559489 177391561 233762717 541349268 828013491 225391891 255213919 481040454 609931816 111049776 296293786 99609581 436094112 165071436 832718348 123088668 795897159 76394999 569792355 512851732 944416071 385828006 470145657 286488252 464916652 785858808 969039401 915759022 974943148 662753954 779980425 473883594 667373952 997930814 998852705 426177184 953992566 964374558 980101727 362138609 444280677 536403011 695502938 79947895 869046110 885930827 996075792 729559266 991122504 276990048 376417076 420797645 454183770 827601651 925557378 611636954 653797828 390297818 517718745 242632923 848534259 154734816 550318925 191634864 484555753 238144733 967022558 886792265 953375008 451429076 982071100 127095421 238337714 633198835 785091865 669293258 674683061 528330270 570494637 906587630 932361001 580610029 960536187 284640827 536189449 78337238 998262642 474286942 671851496 393890427 508254682 94963784 829192685 438806080 475997252 313439862 897659278 992498539 992604852 346554043 507759245 883095602 992905900 410288361 457100422 948564600 978741003 587612995 950845625 592292825 763485334 445933201 974009335 603197961 938646490 113308964 670659107 302511594 341630791 936666484 980522488 404359422 789282991 153623833 617298331 513262826 989397759 238134302 967669454 486860105 539796921 523273374 998852264 249768739 669470921 909658235 982288664 739701890 968017412 429174948 988393995 510320620 837851719 618796996 873427540 433596074 973887803 451388985 863641179 430545338 936657145 44259930 938517014 219369675 478456129 822567734 849453650 348389058 504071005 609460784 966094527 690724642 860381198 884198864 896102091 303691247 365915294 198043676 879081629 175105207 530921008 39274486 952660570 932815498 999124950 79906485 171868124 155654058 914178447 92068648 918641643 122689647 403030541 626233052 889981996 108287965 545667725 403272964 843705548 591725647 910677316 73063062 754239077 409697947 569976576 397133444 412539171 644911295 808008708 272935582 312490238 479437316 546648600 618650793 871221894 106116319 335981281 187297734 563088210 357423438 557610824 85664553 622899486 871974564 915341819 436593494 618410375 770796021 824804395 180834122 927485132 626186380 942147459 503402530 706955224 492840370 810941827 322174496 948431674 701536663 876632899 313087685 565585186 501192404 516697132 864306412 984575835 674829441 982285509 545558622 835683984 272366586 428648106 686149760 759994996 117599487 122879941 53311895 878009133 123017912 248247268 240688357 739912536 286391132 803738256 262826978 785411454 91418083 439775340 987827113 990240075 662135030 837303656 691326177 723830904 745511103 915620326 430621098 470863208 994323181 994809396 120520976 780295205 276764867 699215020 566771124 807715948 929820797 949186469 601100442 763358068 739502716 820397223 609266791 670012973 992896380 999760015 431157717 802610293 569214413 655308614 192440967 936244067 905394081 986058027 677739163 879369598 857775085 890343280 691368009 813248328 167408695 568297498 695205476 773093315 170374346 981829837 870777418 980185525 62262955 484323000 901800820 996375628 542159777 971954444 732694770 807609805 187362789 201253377 394182202 698850060 59205615 181223390 805017096 807719493 136613047 137235866 251582200 297983486 476461477 637559149 933865777 956512087 844453514 969050642 82443110 822202778 705655450 957624176 549645142 951511089 313997952 671623676 389144783 546733265 901261656 912398040 416419757 540984278 261652851 870733661 729248892 908216371 373502307 745356398 807751974 876761085 941844900 974401890 108933805 460610131 619595304 804436691 694357425 809427096 751131154 986367281 65598315 116130329 923259406 981862324 582625394 795035005 565327441 832625992 244179897 627484792 439699086 916893908 316891136 540508424 146142460 325668254 848196182 915478528 562934025 963891470 131958065 672321627 894134503 977961195 907973310 962558726 31621542 728110468 773034759 865068321 563473129 653443405 317419238 939223257 840784625 930675014 145034260 406433358 916962960 963860213 807943922 952900373 130561140 328415349 837437346 998392813 167326486 387916428 249118602 808136283 991876371 997568624 46440199 716846191 306015785 700828547 334731650 855674480 295104244 871536694 860781214 898938083 883887376 898644599 139377496 710493415 664761344 887164946 515886006 910968913 325273818 429776839 297140332 872263151 728250877 889479409 835651645 900709252 858503849 948479705 702569723 838811756 553097267 746537998 716120597 914280813 952311897 993396761 910599689 971113451 730125217 825406630 566656921 798969289 770801738 921221859 639975209 865378631 395297965 407070523 242097351 260570086 226215789 323790104 114700375 318657909 14706006 113791107 954771742 986235696 500928031 996355493 571755663 966927372 730671265 886512921 417207618 781970942 240621561 753552543 482762874 513813740 421253964 439506656 605597439 771089178 618670372 679284778 15415095 291066520 894707970 987915142 679013633 983127124 659954585 801970397 989993870 992450476 248019195 911354593 753623984 993944959 193464591 792064804 821482334 962407368 534868329 726680291 741035078 796035651 738164375 906665783 355267366 510645474 392891441 814836153 256110013 401541847 550722117 710733431 753941995 941695859 170374202 508568456 859667970 927718726 383830962 996359669 805104902 888392990 664449367 682536995 114453143 334189957 112682599 797135423 248027949 443878148 307070212 964994195 986897464 990905334 388404956 727126706 786062797 953232587 29086194 438120575 897287783 977260867 921804348 988614324 24559535 146298442 690936286 865175353 473107851 900058369 580486227 822327826 744055839 826849720 311242751 342127422 883658499 958677250 543404494 877637968 909322189 975262225 87422239 104246070 281019201 582128185 561247503 769111381 324496681 527395382 390516732 498780851 359138807 581892867 42682506 675999365 884958329 898372229 454243667 545169690 966620928 981479548 107418920 962915871 188210374 810073850 529521012 847098602 106175732 763750393 132740479 474500582 97777727 747184142 707765792 710111873 663156879 784022589 882418749 987724702 710524638 845319110 989293697 989850527 665780904 903734655 402462055 530914835 871126913 953387146 993893214 997231247 399104155 457060976 394159564 826848846 469804983 596015014 215831626 319209599 719853214 998998654 438333531 963833856 222797891 797605247 590419564 617471754 919242418 984886347 786429225 998532978 971776849 997140160 90541385 602750638 458291390 921458369 998654561 998942375 789425596 976789660 537679190 780582074 233241367 265760026 395218791 801424585 421319959 795925845 795123733 927839449 632013988 998715477 34483968 881587733 646291507 818118930 464611603 599838329 847309323 876667068 376098660 596403875 401449765 402190167 826886624 827412987 273842032 660913061 33808156 161946768 685307159 934271812 896240411 960530181 500112771 545007382 331863125 370733393 927648464 951851920 958144709 984816635 691750293 887914427 138948894 391591215 244636114 762047746 584685613 781208432 694635813 946179378 80217819 148097680 474271418 642269757 619693405 757527080 293885426 444016995 844110172 880457589 924345964 975339412 849707205 979457636 492586602 812630799 154785481 662452431 910911512 939582893 734985093 965441465 837154806 878122075 166586444 982596160 901529526 936094695 227912093 536242938 308621427 863883745 216440448 221824335 903211529 997304860 316892091 569396262 275152029 418022586 359785996 990103067 638461620 885225370 845988410 946849835 577417547 954675905 622347425 670650972 109946683 508647038 869022156 908494366 24234855 686831908 836687964 950191711 516896822 751869277 178292066 990985525 81843090 621409968 787261818 959010020 556232991 792020250 330186567 742668212 228011205 822612975 157523694 423254941 101196536 374526588 617834739 734415569 888186546 969652172 732356874 941343988 602308573 996162457 433425349 467433052 539541142 576312169 714397523 828390978 162808211 627182416 560224285 595199088 293119622 438304175 46597985 488898681 930446650 948849389 539373999 773497559 326451854 728429730 697624439 742946336 220326546 313350195 565708856 736857952 663467548 932442147 74686129 855258713 186913936 256427066 176495579 219070996 29939602 449782606 584445458 883615411 293772453 623024167 703850810 987513040 686589412 902536347 116774199 129924175 689297177 750658381 969402265 974365566 688303547 979185377 99244112 276437306 63032764 826615755 696136583 882931729 314019514 769472460 945435807 986563955 243958813 736299688 64051006 698140807 257184646 267297289 78244542 96729095 597285243 923507438 431014070 750377930 442070398 629693181 676482055 805882593 719942031 962716322 301185393 565333441 310061581 543953998 287050245 487683174 352974882 817923490 12047574 77813113 478332665 885567511 924220338 976390462 382666798 425297147 213821787 603372533 70959594 572995469 476683488 762887121 921632175 938671746 702657376 936812739 515174669 686333899 648450734 877308118 173720153 816312662 866761853 985728274 405496383 445407980 982664166 995922818 271576873 885554035 653836427 936446556 516251800 805469116 695860866 808266582 913156417 975759364 523272106 546720948 365222120 822478241 114532033 682107006 647648010 776843448 292232461 703978611 146683083 585442166 101165801 261093923 352973271 840984716 578653013 849377618 886748134 905143746 620593588 839244898 504086858 700009283 608610669 689007485 389896169 974735105 218307622 338150490 605201388 786139909 54458412 95331187 737887601 942528968 312874673 631154781 43254998 790746300 939991501 942769426 91815251 653326801 425127792 863811863 29236885 997239281 454718306 506928584 164548960 221810019 251927647 719852974 121280260 921133844 891314338 900104497 80485193 562890929 189409121 302112078 978506581 986648519 170511784 331995582 811533751 874096586 241563334 653098823 284347911 582306761 889566601 985745214 477144840 683732245 252848864 373712296 958844436 996875230 192564487 842750539 770985885 863501318 819387548 825255046 436957840 771186929 751130553 916185240 432149561 906911360 890782682 927272298 149485985 523275779 857585553 861889724 112106276 485960810 858774101 922071994 490812679 910389030 545969597 654117973 161112897 471364440 378633444 454920742 377735185 885554378 624231262 980975338 223849290 793753089 129738005 371623263 479149132 673631377 18509861 201820813 345614871 742572359 544833694 870690130 588391085 650378789 321368155 758200381 363810291 910655202 540119724 859898015 463589497 955215938 714621572 715351984 533692252 746972227 289605226 551634478 384991250 567588509 607303569 845110741 384411029 488107192 876726277 947126102 365800410 789326873 252209525 783402495 855663247 972554750 538232009 734277762 612199382 949871363 577349011 907767106 55612398 66606262 685814021 721079432 75368242 257604301 21046408 909079891 241458644 325976252 727033081 990268263 655103025 897307043 949037101 989482929 860621779 943769395 263535415 704974329 751049533 958953176 630699506 749700317 241989882 270652248 451816367 499713499 601254910 784764934 935672669 991881492 353454134 741569703 795993607 812470276 582403030 810632593 160737744 811460939 886345900 944656037 646486265 813992036 550720936 649861789 990406672 991023905 777555016 972145294 430484733 494573796 869185666 989830412 348410341 518903215 112656321 675577462 776662990 831145294 618389423 625732606 547632826 840300663 95009879 641717088 757022354 820155870 696181845 878896734 856685308 955476185 647848200 862903739 108684662 249417485 498423688 650745626 62939483 706787459 62980835 913817072 527036744 929710922 845804785 934910823 692018244 942983553 90800677 571636781 797109039 987443907 242690739 834574280 64436442 982054719 905996822 942097021 782349004 924037872 632063215 799222902 131952534 599697829 111036426 745645592 587832141 897273484 434498834 638784829 549671008 714428445 864857197 924196002 625594956 772169826 389341230 905901925 76490011 614699177 474377369 863395660 11432357 596885787 924582478 964712910 875829006 898119427 812943787 886539327 729452028 908387797 213109519 359042966 348396037 896184286 185006198 765874682 291976874 442675951 934316829 990182776 306145859 896962599 885952830 895287621 252663096 720780516 187778862 833535429 862288899 917103129 656498003 716805519 988452963 989553763 487233296 895810973 720097740 756747509 252819621 403132938 16949970 510857303 996703113 998351258 17259402 287795560 44287799 835817807 855108320 906153788 694844369 911049825 24013553 777211113 571561609 963531695 80176412 234037002 567679212 969280808 417932807 687064033 629411484 982282559 137080567 480230452 399457839 815124310 622053505 820065114 463445979 851073863 791081488 903770419 631698307 840995160 21546511 601628622 657317863 875463139 851591880 957376178 621380374 911809498 803832509 828816010 329628003 999400929 990560166 997749985 838647078 901307072 976409967 981852508 211189602 418236087 790801902 902644025 409006222 462487800 323034658 701017194 988193662 995237446 996060648 998582395 543601902 575867359 154727456 936226671 41824270 679428705 975120476 977692439 303304541 820947055 459761959 981609370 803727725 831550837 20992555 316613414 274027617 801566769 393766167 751424018 797898618 820202368 66094913 879339473 818749463 832399896 681813604 879532574 342940774 490481330 545456091 612159753 371727301 854240092 722377190 892178051 355129435 606581540 684272469 948433468 361547356 561405039 110450350 466393617 565965901 962307627 10961259 584556709 520175162 998520062 788439577 930982474 600725137 967159783 208714011 223298450 192609781 459729400 768032820 880759193 722365393 937747057 920784147 965514422 633903177 652777970 50619540 517850182 744643951 958779006 169960729 738144722 999309595 999573437 261967469 543933210 730855654 733787587 879589050 990252746 141489421 508188502 446684387 971468665 97077994 179186753 229838264 905638994 596177290 872360994 46784135 188575256 507683096 788500300 365752837 479406340 954951388 994745218 707991076 917945760 216881226 602445987 45221608 878098166 366163637 719424405 585663967 613071432 331290438 422505449 170810432 913286550 602661901 780149821 67153992 212391110 143797521 703534232 835827648 869217454 236671582 602786713 565767853 660988708 183536313 909422000 278548643 503713478 850903928 893317848 738772038 850400308 382660515 848489137 471058980 512428836 413623147 629532870 880258288 951619563 567087670 706242258 586359565 661666931 311870480 939674596 789716773 985013763 768317656 901492359 595843975 673383820 356892783 986782747 26118992 945682827 74807440 847171433 93543153 94957101 861587063 963414415 152088841 180530326 382824871 437005444 686910624 944751201 553998654 849855993 439610632 589899126 985648253 996050973 485198360 985768068 611253366 728248711 96976778 746135370 659221110 806839375 589820056 785375563 111366376 342553854 397259026 446985207 928838469 950756103 729809288 912252197 498720336 869212344 747385099 938902088 605976107 708286312 341161283 466814055 490329481 607386676 21841668 494570148 747879675 960644504 466951546 508281693 877021725 944123098 96722103 147533061 912586082 931588163 886674901 962078591 245355265 992248697 790384158 944148760 701813392 790834821 227370029 384204844 315237510 888076359 258034438 740215093 721625078 988610114 818589399 932983120 120768777 977776786 694898542 834202637 510570623 993984741 975484944 998418153 994787534 998287095 124240584 418310161 136516084 961844784 628686690 694565846 833503340 870674754 470369386 966543324 531625116 968283538 122322654 824966020 413908869 605389242 26432549 679384186 147010064 148840013 657524478 702790779 134018333 977916045 284835989 752733374 556221917 833813334 280492913 537637859 643697226 969391032 16186960 568257676 449937052 594169799 211567724 616643372 582171922 841690055 656079606 990625680 444456257 967137236 823493890 899648370 262281235 945571991 774826305 957382756 365240038 415627601 472127457 717933543 162438235 422796746 781890180 909559137 904475005 931961416 836113985 890424905 503476412 989611679 257660476 701561652 111704793 447663084 350583048 350609204 961589150 970379982 416531421 797741314 690659150 778240385 17418072 872468020 932907887 975004876 759166954 888565346 727550494 963623811 147244145 965588572 584351421 901293316 97203968 112171068 248644890 594469811 151933091 906134068 410918954 967245062 159969997 827419926 216277175 983173036 862994162 936241881 110723795 324482643 108778562 712993589 467578183 888280349 641970325 850327283 819732070 964702904 60041265 230631063 200428246 295614174 610155575 889907874 905759183 962065805 286583028 868536770 700398401 989167757 868490990 922960484 745322630 783043791 741746409 942371895 57303470 111591292 678604175 700359626 618845826 868943430 137890772 347080215 242868606 872133200 899110466 900508690 127330539 136198683 919091614 979325183 912096828 934943750 946549967 977048920 447929963 615334190 56006204 289979135 212351401 285894950 103916898 125260676 800592555 816694397 888675846 952250336 771382370 971564293 509426982 944948812 765098111 790189778 26722988 736384684 355022332 873840130 938940796 950874635 383722009 820543540 10388613 567714787 254596584 644530501 913452107 949194141 589791189 782640261 876915852 974228748 642520114 828961590 314510709 984340470 669355694 862427507 13546693 177908013 840805451 996676948 446920876 509118635 851970307 902451279 899931335 935887282 62617505 161001092 515085072 532743945 498686083 723024865 655477310 827526391 267048896 876772788 750759492 823518023 488917296 930801909 698282790 861674036 170931556 848204257 13953290 909841728 941575351 954611212 18371963 184148782 354807115 624576318 552525193 701855728 939214520 991939815 271376167 706018038 270066762 356213504 351923040 696747358 633052133 750728521 478310976 737597284 978776326 979638368 939760110 978026530 260758485 643593820 559205023 727234985 349031761 971136692 793395247 914181097 208314994 282874907 49035905 554685551 29850534 627141787 287653414 416632624 10949241 797679709 917842579 923567463 191836687 248077271 358646171 823523160 969069951 996581735 122930534 518937896 167709669 755498802 749253784 897474377 163277405 239104074 977642637 997462164 71874942 331741099 886304349 967802509 798329571 801914470 435207459 645078862 645811097 837314696 512414954 738212122 59276338 215135700 435439156 772079539 698367399 826945810 54578008 261497875 844778556 974143783 881188165 902120332 373078799 462574157 689969073 767346471 57148368 327186451 193496661 415478342 382896508 583077774 117600925 495190953 342736715 926214176 674928767 889021532 482548124 898647912 79102928 253070979 822166533 980377763 313594367 472179839 658407969 688079035 903099151 990301248 312229396 532027026 934846576 939999574 164453273 435630274 275810664 453417065 349198072 560052139 42227242 810332582 60518528 475259802 765621487 975054646 71540469 445381327 480305393 502295915 124378325 275924627 544064992 967250141 92831353 919132325 809547155 985642935 311178945 688915487 498992242 565164448 669466844 868840718 859381794 951955522 348732398 569250643 530540195 900731306 100812826 759746441 316544173 344311243 864244743 890946986 445231738 843419104 588897261 864253137 67779225 142223641 523054990 914726698 14485852 351259052 788079219 997259116 415343899 671983786 181724526 986708065 743206497 844881078 576208048 986705266 730658653 949499024 423015098 838986745 659328474 747881555 721576542 983245883 888948795 997606790 817945228 869958311 911145622 985943032 890520025 984135370 695941499 967955544 20134388 103330321 87885602 999259167 587221594 591789728 131400384 827998179 924889243 975608406 786567223 908743635 413799185 431008750 138565079 615512237 58089670 800855290 321397684 787874446 339207552 576669541 779286041 989884183 388211616 552058376 893655009 898964491 562705380 990551093 197278970 697834754 93702788 982292905 907096615 918445285 35934489 478826091 242388351 935862405 787156070 994497294 77293056 185885602 698687011 846779373 305035507 378270085 51608592 59702853 113869046 195987885 618821419 784949316 518117986 828241140 868154893 922692499 57549460 130041808 241141186 750845882 753496776 914878189 929730577 978148522 590054359 747041795 281635254 727218191 522649661 775463841 954467956 976412306 219647631 646898344 816630811 894244064 367567086 649115316 716264160 895042524 419007220 725808930 859301185 868752457 594010760 674711866 918856890 923327852 414994202 817906505 534071621 679055034 16157535 294189792 250155204 650626076 667651371 697558122 282402710 445349887 562801502 830413862 482440032 576209747 685162000 696256194 11006037 852264876 150504818 936032350 800905731 807501440