981 224851184 920295595 542852453 925129023 272868639 775225288 456336703 913402622 389869143 567372523 459242191 730420763 825804614 991530946 188223825 223218104 362071183 878998121 168090534 839342084 834349748 859931690 642614198 977789364 725151986 959823716 62973183 494894233 777052110 968413965 243077835 764726845 449057204 717092845 835925001 960544412 228553222 566438568 297026162 679746075 832086939 889820102 817349906 919945392 382461125 426918462 373027883 633640487 546345475 891444308 213237906 644159897 753391759 948602563 760344395 975150750 312934109 837884724 384719476 596110848 380171606 994880018 628324844 701601210 617394174 904404316 442959568 604640974 446237420 523761608 479357509 750772289 280468839 886772376 641858156 697403008 328473251 375633726 715360838 779524993 721958732 875724895 600932267 963163136 703231094 828657477 865342111 878910962 608892883 998753536 562011789 872965735 879038956 936192295 799355736 888043910 372068997 956024487 275196865 568345050 445821846 834428771 166509958 183843124 703054809 746126524 700377218 767017110 934630004 998806092 824798206 910111649 906411502 990744768 136118780 311143323 416343792 778266835 580750658 848536792 872553284 876243608 727850817 773053717 715833309 879198571 668244637 928328584 85181035 926374359 816291313 937289728 870547758 982153946 125735381 864463340 803340260 956845616 376573602 802157825 937273803 982030956 580712822 840507106 275016162 614872526 583183546 728181479 675209835 897482715 888115696 952142789 315562400 372242093 582100122 626193030 523800845 695978273 791570577 864214402 199510015 766626773 159000335 769560707 951024606 956168376 668096741 843501171 275318876 410548800 603146334 894447843 250578237 595081817 785480719 955409369 230497717 815572503 286343111 541938854 301573760 470611025 469139306 565018927 770859574 777368812 878450061 976012716 337326628 498947092 291008210 908932521 313749144 506913369 339112545 428920879 382657533 912779157 294536843 652341834 979539053 986068196 594197509 735609866 91247921 554427060 978477382 985530519 571292676 917074342 846718484 924719341 205919522 785331316 352521011 666748132 756304717 865226854 207039093 291919669 584676465 881572992 620737101 935693092 420356327 831854646 413413562 720788175 948408027 954312625 764880286 850289590 256181620 873618977 700293932 982327601 443921222 714969130 326808286 781951356 71542678 737562504 255753620 453261041 781225933 949971677 146653020 548291994 543085750 989016631 139896868 881518862 579213750 969417016 682495981 951277990 246519014 267395106 166763900 639440462 12216303 707157643 402752116 562845153 533262006 842057617 565228139 620089803 140243640 766620432 705022013 803334367 564598235 993736502 750359756 890780425 854012604 856355005 161405855 575447318 379691086 891632663 439858457 634254306 916391054 958598730 902289917 916617903 433314868 821607405 414440188 567859252 173329455 912545486 97710633 738310854 434414094 871566402 510801903 845237406 215702093 853995677 775878925 779832026 239448944 719882596 527078551 750926748 533778145 881505422 64052862 115026824 432378985 968176776 177499921 247567619 568092366 586903687 871134159 996981897 818143129 853324729 274018247 496904373 827406747 911127077 588501577 633371484 92995377 434733398 938047275 965459843 104245528 614052373 963419896 994200886 539184943 584579789 700466442 979314051 562709419 771831324 887796807 984847127 250462976 871028989 781341274 906673157 120441677 168848410 399457283 930325727 282081369 411214494 678078374 823958117 85634523 191930714 278296908 603305177 626309076 702889276 618087832 717605480 689404706 781659612 783046596 992268178 640159692 867244649 592960429 977813494 50263996 376788596 368959944 877011767 544884610 565278462 507284474 730947178 427187537 868387509 937940745 973078591 810630460 905163198 753720148 964787659 785390837 849451126 133595502 184434411 672997439 993859682 151606162 163380673 130129174 608946702 713485903 939662603 389613741 933604687 700176927 817436573 176955281 430098147 641309876 821095332 618795642 905171311 866543041 972364406 851935305 938496951 107075045 498519618 762297669 919052390 721384434 999455745 822467737 936118325 365259433 625900439 438063445 455568417 314885228 623238785 458047984 847426175 754992201 828773823 462136217 736115316 34385772 113939715 121287204 833753933 475171353 912805932 263639841 428855591 393166073 852197055 534698699 608022144 398545907 686327213 664254179 967380342 104514606 958240005 384392501 754122972 195392891 272444840 202472379 848237423 441306568 972385009 663911338 845954394 957306674 969576286 186681837 526845745 734267636 877580628 906266142 915190487 167605765 251293243 519524449 960255853 720456995 932566225 542777792 670375833 621563264 949928165 467885000 818193951 730215640 826427510 49387357 627639723 339910825 715088708 786986558 877143495 419769397 451676371 571140453 643392999 946457066 977986841 793491492 832385912 125902844 660407914 18628104 245999669 543053060 591506519 342100954 642595021 721660179 912891635 753175376 895008403 327519122 724881074 604854000 972900313 56262469 404066629 268349008 904941310 228388228 441532725 330146604 876483406 698099351 747661558 805122138 902528764 534784117 817850742 934167536 982193606 686200232 799109233 411314968 946560468 785517842 856568571 292532653 830465735 148367474 653815424 651471124 811838225 78873634 373050147 75333027 407742126 650353338 812476384 960390018 984283962 831125483 998846829 108475047 745585935 936182138 964397529 76145273 592966487 533743158 675076960 757484594 758983217 766232083 909517692 415825635 457338256 334928807 846991667 808313081 929002557 128400393 559889299 129111998 784213218 542171330 660893908 900545749 967122958 445392182 708616750 805054478 820853533 712384461 714714857 233334494 250497488 248504798 573049780 246823267 723736623 262355109 976930364 154265279 644127484 737410844 939717558 262562877 872194731 922928426 945294343 606418905 679728475 952260226 972314152 846174049 897562696 83856204 394968375 345342595 682857006 877794440 946711902 634714101 697619744 655966129 788311938 872570669 907684661 188880135 985311843 747539228 866685809 704582194 741506948 141733014 150881978 708519580 729901654 314867604 984310489 745667739 748613041 333822641 772445489 147022219 157935645 643929661 794494801 429083363 836197150 669580422 739042477 225022979 956882839 596854002 817850944 821270162 989299631 355401408 362325066 777466240 945370630 445086282 891872383 37005418 793273421 360100972 946679489 68066576 191603167 989403048 993746598 377407217 768765979 174619734 791816042 594115875 597638522 292487669 373742635 326629671 495429045 882637296 948635150 400056629 619201948 118182135 989667009 36664355 275812667 612304924 693312533 695195298 703729593 149199761 783088508 22702149 737407388 72805522 629436357 221434568 931444901 360955436 555249432 477328390 872598999 344744780 444432707 809343137 993978057 76874159 800810735 642993343 706002502 93022651 656484987 738534521 916572731 337492498 482579578 588139294 624508662 997911402 998144285 22169811 805457329 103904486 506090026 578759622 827598346 464057146 664672232 729897281 974329005 266350960 865194468 16817754 527217549 67475823 835453188 89440346 275090592 214265331 870097864 743711832 811641633 938654431 960251466 158339297 477771392 859214074 960563087 754379112 912958398 448230448 911604560 698871533 763870929 198108968 613563613 934633921 947959416 396355511 486002164 834958505 907669166 296497585 718952701 207601544 625701212 155971341 197899846 168949221 234880366 551130000 935083556 10479211 846196250 878307839 914726528 182265949 393761271 81516230 829580991 377501601 544756062 408503696 803080356 409759815 568513033 533754842 977630571 820354836 886648916 634133331 777641900 721991363 920423958 253907883 572071768 293822456 839768989 574831075 977786046 411662387 980459220 944776670 974396916 815042311 881253399 148580182 813947360 254161542 544592232 118362570 407849430 89277361 290344474 385826367 492060165 533518947 842803134 551882929 917092334 784929630 894644839 34755942 447697722 504881630 739558771 927844449 944017752 144874215 736011410 213012978 511276760 202743064 238762805 750573557 853838324 978829527 992870766 28489538 96489276 832769085 935181365 25486683 396141450 663705480 740118394 948381167 995017615 415276235 475989744 827757388 908513449 308422701 821445947 496139651 744606079 843566845 898018175 162025182 909433589 794109847 865746927 359003729 647942994 165099047 513798287 504469035 966711072 841746933 892391011 87942606 716917646 359858014 996145050 610564216 976180818 507363020 676723469 202376632 445953189 91895791 693682677 682687693 845793162 145113591 340808628 794896315 824783845 777675829 879999500 433938060 553965436 653940031 767101001 191255344 902021194 671415425 978020481 246392995 723374839 236384717 307785602 516463050 683875212 60998319 101978030 147671088 937907060 287662511 335761067 744572332 984943559 651875417 657789164 277232669 774870943 746406116 785255582 920769066 938975276 921967200 971852677 284917259 571688722 469194116 536272121 75346916 518809628 195494897 209443058 644124760 731669402 904050969 969246962 179788274 339885103 500096181 968791549 645073794 776752227 645807011 781381428 329774384 966065811 322892900 671458746 120041786 419322803 445693908 843067237 468725963 912022790 594471025 954685393 644146406 966080885 756759763 817720153 480954818 820528424 492949276 601377376 711971183 974078910 479295836 693939111 770537362 835155859 364711745 477584978 539332735 765178503 604699688 948897182 416007445 994255009 979043593 988809587 10982444 788249883 406349289 971325328 804555398 807502512 147730614 991726428 814750238 988331166 308553903 810100814 410662809 660893410 908458332 918350051 439463731 763939787 36573790 235253993 970661885 981496256 841730724 868667055 444880182 760359973 707197611 793362992 634708801 681696982 877684608 973330641 893715639 933931873 927273738 964964195 739366396 882117639 340164992 709053802 846932527 865544026 804737353 862632316 63605230 555168640 53897796 149266321 829643631 921641601 773777170 810391244 117188483 431086325 227598661 615923730 55934741 79443001 320508404 844405241 621551108 896752959 633374209 938898224 242995879 624430139 938818968 987680002 159662039 442276549 500083599 942161835 989749990 994307322 925221634 976824791 284650722 649023584 556654682 912578139 346614963 557382173 396675330 925413999 70598994 741486159 210996543 428610777 128178228 307982914 951804409 988837353 603632203 613598781 622811624 886912500 53237755 58204900 769005079 959853648 496399404 874067872 996795556 996925730 317610126 470588886 517082629 923099288 213206752 385776986 262049363 355011430 828918597 907378797 228551067 778523038 706775869 779806713 139457729 349240358 735228426 839704004 832853173 903551311 756513599 951982778 619146500 733746853 649692128 841464794 855200014 864593446 518645189 841456399 947757523 971522628 77086541 350927739 786932846 959894837 824357306 919383532 722459988 724863578 182620849 668207705 472004800 791169133 672797562 854295603 287555787 403901930 162106056 600484704 128692083 348073099 642595618 912318987 134125579 144829616 367679031 584549669 107511295 185271012 952236613 955059841 43841893 372246450 729049295 746583020 320298406 334679094 17631155 924128454 341220585 821780078 211631615 423749177 516167108 645215765 334881404 816134380 605823377 902304919 52692285 357807976 628611018 827017066 154358655 239086673 548409886 699588572 41511761 184231626 30042615 973317020 41251875 896608486 525555035 657474801 326158266 456011196 509167254 986228997 974607995 990254684 999698298 999826896 407701260 736467758 183830876 673311726 327128399 763929135 808854550 963274037 816205369 907281332 322143587 831286060 861786817 950195898 763926671 908334030 881898152 993339496 954690776 967060130 750660945 857243935 64357487 537459873 553676283 809359877 455633191 964005839 102567277 451093027 568004218 619233336 47324604 454626719 468068730 483775887 288001424 772903829 552355255 804207706 892368317 926897445 626857731 672242487 760130130 913818966 725382084 738203716 943709836 953886817 713377563 906776504 458211692 679703993 494983748 967001008 726965969 810033318 816823697 853700534 285661165 419694625 857028423 970950528 450926408 819917912 267922027 387426381 416401537 433238191 513834168 853385819 217456358 766621626 267412701 722378938 931772027 971919968 650108592 754922141 709527108 824825173 344492692 756590018 763768267 828276116 804714604 865243021 159356618 625626606 566030549 895120008 973476274 997220968 213635169 821528217 594771904 765252818 37159824 713932270 31910909 876847219 756703215 919185736 540307274 580096353 626756718 900931152 348778400 748451141 173272240 681052445 625254506 625413267 954482489 973003382 580959548 614966374 841882890 932602242 592618002 652554567 154158508 505536869 194012720 674464755 410291939 682244594 649860324 725734727 130118168 591491603 319835979 591292086 498199027 594266664 76848350 87718037 749587931 761231596 320546133 729200074 94690230 543115137 841942274 915017760 98700550 751672784 176302726 849406357 639666836 979955905 286542729 484560139 840394273 856967744 607760999 666884850 232303305 755448701 386671837 992417161 736365730 915838392 407626570 799903938 237518787 481093741 280789427 997734516 673837560 966704459 573184959 697272489 586689028 876185269 474268460 497264534 573577915 724237461 759286677 792975740 539292810 902551276 763138737 765961055 949637627 949956174 260255599 571106447 889271737 944991047 897721330 998015705 532582354 816008165 660267750 881067872 111993866 929363601 289512623 561270690 262351592 385185102 532656706 636353163 400278423 492548200 683745618 704414973 539885425 973204433 983274943 987976172 79550521 555282059 406877726 639104758 148960582 811420519 469150488 780422707 137960569 930041248 775578316 881807209 396063961 969418357 179915260 506080174 24697519 99714883 176640052 879491345 463081933 808271455 837946467 973728568 436168445 698185862 789121343 810685975 775905825 962656209 149003981 450050516 696895571 863954764 396932047 936041785 436517984 734874621 537671157 657926595 482966333 753098688 804460840 867038111 829283483 886619372 351990706 790755055 94815841 289588001 98410615 412441366 535644726 922109062 823311174 926069871 706295616 922869829 800229297 827196780 645216545 920146171 799857517 953273126 57020410 224062793 278660311 596459825 558394694 784676174 376810169 514404333 290359045 344170214 669070412 993347009 446930150 613235664 818730480 957868007 358053493 646982318 387987038 488036651 808700043 888944183 34785057 733433557 901935205 997831396 314297866 492203952 190663839 456746116 149411184 470448060 128284576 456061392 402088696 580254113 127587330 897513750 800010758 968011729 102819459 889393913 953897475 973160090 262332189 528764260 702102636 925234222 241813225 885467714 759389793 873364064 38406068 750759858 501258907 595664908 643156333 789378651 960379737 967403598 960184856 986572864 850615676 928351388 51430702 700149035 240956995 955794508 589203056 616861695 909300768 913007981 929212198 983406246 796289220 914361251 601884478 939908122 14055530 966202978 604580040 953411142 660712242 698622985 547577618 944892089 763858940 877606863 622791231 897031745 279075782 854233607 859694481 955296102 463468487 753954867 885104588 910563612 621716107 698567319 925458543 940983598 979749503 982774260 323534614 508743758 953228951 966508928 106745652 682636440 981911461 996977783 712896422 888012464 798856170 952721349 474714672 746075771 258112277 640924808 278261074 835297913 838066515 890313958 166854981 407960857 611015226 782463434 389366486 691924826 896233532 958545500 131885281 282789633 608984395 736590520 700574679 701232184 960127894 976684870 477757245 938837656 870594679 957961642 554198357 658523420 190620761 623306647 481868837 850476129 230991679 349267068 217868841 772234681 490299902 708349599 985479028 991967116 146979738 506242000 711263961 934775169 716407784 750415741 436902349 831687753 975104489 985960796 446723226 726477544 341199522 836105082 581703619 961373175 41176797 155299121 270771768 688463642 335719325 527444481 867997922 869325178 439232758 903523776 357309479 532633499 218858511 326125006 979003994 982834997 391121196 914635513 160147871 891210325 497808502 811074267 684753722 800451151 188533807 649219028 171937089 259685294 151618126 167941927 527593626 689230172 311923702 540251581 252530196 321479109 206042779 264579790 30730817 439692271 883026183 907019758 502077117 804625939 220975298 969229531 27739071 223476164 614766763 692284554 794671591 946913999 84050399 315272625 907082580 936687910 563938724 825425731 414264123 680594973 240593880 882885091 708644017 972835932 962338337 963747610 593983408 785536283 547099663 555661684 121823467 392370994 892301521 927370589 197376118 638122677 673896245 680784998 728432528 864888746 175277728 557892151 244191271 488810548 581831871 586289847 398862233 970571742 534412083 721163247 653045662 681586868 457834970 761151033 725567788 953963395 374070848 386292330 312910359 347150476 283677453 386119062 665851241 918058348 52526639 72978336 299914189 315681870 612203133 973392612 129906105 458688067 887292779 900116134 941413733 970659974 482719884 521654818 326362628 712977679 457057843 789258747 70733940 768989781 603452003 888824541 299060108 447516144 17835448 569747190 702404987 817181450 454567283 821806517 32578931 205893697 320134186 447278616 22194398 863710055 675588319 698451897 517841815 975860468 781232156 819902454 128383785 347986623 797503462 961653144 361207953 822005095 907141694 996296680 291412291 487053020 959624785 959671318 141348164 559521722 178711448 759390611 316786935 499021895 858331203 894471414 827180450 966613422 398948640 461662572 423454317 601362568 732830372 772626254 275917636 429196001 283840270 826040569 634494790 711410700 63961237 811555612 301819046 558153546 773056587 794377617 727202240 976725768 101674458 805706665 600626107 759852011 645462993 685311423 440326409 851742289 322725571 891857132 273246204 888773786 287368309 965442361 968114212 991731328 517127654 986448619 296810947 671283580 840616029 900493706 722816874 737312390 268525333 706203313 157628947 514074897 264690526 404812432 998207274 999477090 132464130 922771676 360957865 871314854 723597685 793304052 49750131 770014550 665205012 801968542 668606378 874502991 468614076 670686115 929392186 983160051 969644979 979074400 349351734 789528019 797041121 806599657 974741616 995433540 160851660 457368492 407946032 907347965 154390867 866490852 739134639 865338135 976678520 997321554 213195584 348819948 477158055 759299826 480305465 791888025 937304112 946456727 31390798 153444908 831572236 891809480 625179702 639158384 697084677 701888216 166964787 960140586 297196721 623305643 125746274 355308069 159574481 550771141 110623672 182294354 248586633 271701098 967215050 977729640 476764276 491666879 761124362 828071120 536420781 595619268 318305830 623619206 385885920 786212036 632301456 999525631 686629775 951300343 672589623 764097847 269570647 600369711 555042551 698325240 918730257 962292412 322113210 750701532 278733571 679956864 779203010 794418511 290107105 690007412 179057589 396634883 278127386 981473408 175587203 446779208 584750726 638661251 210781004 891884805 294032500 571557684 373841847 381798729 460012098 621467433 183180881 893074149 375207514 493505717 854970925 878779264 711673266 755911446 911711548 996862220 202419859 535224745 317283630 920639328 898382460 917603181 953783496 998143882 677173983 700260164 19155790 215811597 210903155 799698256 912636627 912979208 398383221 508887426 580568932 769674248 23259080 503382897 263328104 795774730 195920084 541938567 877305682 879148331 310939715 575227843 421644241 426455431 304496067 487320744 950253581 977401809 121384845 672775156 188200125 384279772 717017076 790149775 780926209 877154501 389966058 578039351 768041365 989650735 788387515 858226908 949797870 981884751 247605648 833614240 395714825 549770315 853672148 981469117 267752491 887185230 688797661 964768287 396932894 959339184 683357402 980429659 588896018 822007360 358622896 678242636 364957399 378154320 796401498 861047291 526087172 606732720 512166538 850573201 905068250 991961339 96178277 466143631 654300026 807654302 690491734 720336148 64935871 367341292 553075472 815032007 211283572 827881242 86638521 543964527 851995060 946565716 365555390 816639827 115858482 666997078 464048737 861574633 670524981 755964607 975361923 987838517 779037551 781634938 942296147 951973557 329086141 927955506 951077479 951337412 34342165 892543481 766801463 977097156 293648838 765390503 42678232 715309707 448940262 756003461 790934151 840494808 342742215 725194530 519534001 761056084 427900289 919171411 763541372 890162539 900128627 937812158 755632325 862299220 326985532 556881225 756441993 996577710 659427815 844629965 906880201 914056938 932888927 937671957 811804742 964833132 95382076 194270492 496210419 797278587 654272494 947924857 970086872 995702801 182165935 358462798 782895166 819461977 380657857 515237497 743865541 900171778 136080483 200433542 444525818 522409389 752597181 822440103 979966833 996128295 299280164 808218816 312699155 390833494 42217978 205091046 559797030 590017373 40526195 939354724 164658840 342466878 75403081 493607317 65923292 492934174 82739338 323075220 200768367 280001261 703921173 707559620 343549719 408561945 826218945 894172621 537986428 721913712 852284827 909677505 950462259 953475216 491154574 941044295 973914570 987745990 419945188 739810959 50663537 481711385 808537543 905713893 873865245 949378266 489725724 743291787 398339666 961486532 320753372 915634361 476675102 809126212 836277804 863551848 423611638 954852994 171116183 409264570 725926008 978292773 753443496 851780131 81274357 143562905 40318117 561047908 608630337 838616893 707278654 775287633 183847931 865795058 967942868 982933226 342017536 572286279 365816776 926726051 693151974 750525481 562890746 747528202 156880453 486734458 524333322 879463898 966234180 972315997 568483834 859284669 704124312 911302752 152720165 707904708 990296946 999280082 140118989 300817321 989552858 995980843 835159748 949231020 644587885 790666217 668005841 795956591 180240463 439614013 201694209 842812192 223897286 732936239 422546622 726322902 189790494 546865956 788360161 918637963 913303833 977417577 15271089 191976129 833829682 872030118 254360586 656529772 241356718 297646876 350458993 712940344 401642118 963818956 711491986 777547599 120832406 309381980 549327625 816996891 535665348 554307605 586635754 801771237 811676782 997129353 630608532 702565636 587650098 841013209 140390351 751762219 924035958 987226012 460595136 793238128 988257594 997033864 987874413 991382827 597679782 742209536 969800085 994260724 133323144 972539655 355963074 827368838 254263655 758822244 644016193 929363245 752518760 966560633 792575040 972265417 365450965 850264975 594480875 912605524 817803149 906503221 494955490 715444851 204416939 412438919 919686067 955149954 589312834 901862760 984506991 991489767 862370104 947327743 830731710 961634350 416076807 967966997 619713270 700443335 905312439 921284991 51512267 106419478 224551824 394498176 553284243 700161574 44154554 895289184 378932778 396556963 163453232 267264938 255467976 329826955 851240679 979071652 501009143 514002121 820241602 924158838 110544630 556690819 59386239 801702157 596046488 987047061 801747198 997014014 633248961 967422983 163374784 408163626 953953605 980086630 118630253 843412346 772685878 791470759 361956306 774721319 402150008 605768225 221952799 223578753 149779603 175058762 505703925 855668672 414577953 485917291 556052599 980358852 202220181 341204032 903227513 977509541 736250603 843010533 22078664 702462746 507451648 895139361 797578508 979270654 935996056 957382481 592768511 746945540 549452465 628384310 306664764 841562352 230978240 774041678 245265312 969947349 720793977 759701451 754155441 794716961 60433105 791869931 569439468 793631386 785450309 848079172 615829621 933216366 231187650 298157758 978638685 991713893 115915904 967219197 121747311 693638996 912024331 974718724 677429097 879841203 689513873 859491228 878022176 924006690 659951920 770238257 946630132 974169521 939536164 959482073 345992602 537002390 380624114 825855103 615375897 703675858 245285871 474753397 497043632 611843207 600999803 674410700 78418107 927171231 54842570 733769442 963083522 987154358 474670257 624734684 599556180 984810450 893407427 965616366 740174434 874213900 221907837 638500872 467928195 950046162 241300675 579681008 393478627 556058471 886882652 905237822 852825239 924381745 554798436 595871162 949778512 991089676 314582676 452667147 261210908 844167893 59100102 939908454 578384491 650613058 694220561 982584905 971092876 992556808 844563747 968841531 127772480 782773186 271063971 993665102 534676024 544766854 504266745 674936515 49682861 867710737 325373412 951373220 18440499 893675512 968709492 971119328 608354612 628207054 729159378 893526155 533860550 862508769 178292429 694473352 607521353 701668435 886892906 970947693 620077261 697859848 51432247 675621402 148111419 779973386 962804299 973920528 592436820 993718570 591395777 753260973 351574382 907230231 944643390 978322582 528527577 889994083 160320255 214660347 653979072 817352413 579205047 952950950 173080421 377887589 190740198 937146009 346602817 433333800 389479310 609540257 933549358 982167924 251549809 520728197 158291108 346073235 999164639 999966090 239423414 303177355 174839731 984508120 393313457 480359095 590783403 849995794 262544603 995171024 405618786 838469118 786006458 840223528 911580569 961849700 814351515 973988192 953284916 961871734 260338517 672043626 925166173 993842433 614299348 823107634 218671286 313408496 55352809 942338155 140236217 808179652 632534083 674365512 281077390 310100509 884416471 917835406 705942963 717369306 713951714 905627936 883348653 927631014 150285177 176047772 912803256 960696890 428460889 582907200 363710873 647151617 650892754 756484165 206670723 655510233 157643734 494611575 556620104 559780264 198071999 542334165 234063518 830727103 579459142 710526242 558394413 843855441 982013090 990117312 514364456 815716900 428612872 600345172 69754586 740744736 205913073 865136048 913886306 971141058 822823519 970375297 117089366 495018941 421542917 869876753 53564468 991479564 695693903 914377487 587483370 591617627 520727558 675764091 135919849 813417812 484735451 994854088 958421429 976112634 418236321 853838569 228227282 292932863 272605656 322414314 870414086 886808980 455009373 556164150 468973590 678760549 880932955 926966057 415566919 609411985 652791386 979512949 730662204 993021395 671928904 798000918 378120726 623317360 110632081 874445979 781398279 899298628 108655912 387190016 898425869 972744880 188370883 670303789 874970467 991233751 797601642 951064409 395096244 657860688 632317209 735059521 889096765 893731162 516995611 857687617 778458219 942990020 852103945 962322143 599502475 632004144 142690669 844489965 540713401 976724835 48623658 562302283 337234642 820794244 627336278 974240497 644956959 858862673 318781819 441707049 435892135 587379889 572276212 614928581 471027490 483021978 309147844 682275467 70496697 723659210 309591513 590312825 559417931 914823627 675928830 761375335 166468871 754467785 204961714 764896758 119792559 857776064 116699082 162814644 369119165 635830159 17569405 791664111 890366060 991453694 258987947 315339540 689471635 860300866 642173624 994610866 627265583 930638960 976848448 990484503 313900472 752706449 780432645 912625453 649018108 855315883 762846303 946578256 187745668 253581566 381039786 716379697 837375351 888027051 788213479 839453581 715124186 947498135 631070687 964400454 446463797 633678757 257846906 565825308 798060536 898844028 513235753 872108949 365540926 379189098 40336012 273053424 546899329 626593519 128103705 161920086 954948122 975384246 409696394 432980668 500170272 932758195 179249904 748288888 424726200 569071128 55268081 93027083 971220584 975683894 328494118 816589337 573228586 675142232 711342663 749665560 449370199 653598158 358588599 788935372 967722272 990974268 842242897 894828166 691268639 853559243 167114062 700603333 401363260 934755710 82445281 886170653 428347794 744642473 935375148 990810654 997090927 997987125 149427662 618257520 981642802 994310397 530834606 932258927 251226785 938115464 390819796 645782529 466221433 707801043 270349087 589558004 118454317 731085900 654165186 853091107 947527373 949941232 682829016 828820002 700559598 824638219 539463965 830474790 900870502 980742170 324561724 517157344 659069050 782500891 12389122 939189743 100372801 973386109 495623923 750733799 827713620 830836853 943227941 977922700 141105920 195591436 467106170 687157402 321222067 432231938 487709235 513668784 396982346 460250812 170242698 246484941 886311251 934302360 243486694 292024982 505957608 765013227 124206287 225690653 36268095 696354341 315518513 904010528 832753181 947264629 541282760 700723015 721823055 735293760 209157438 406496870 293336038 578956460 419309161 664265525 324503146 915689110 230170490 623518760 983374660 991995607 228361617 430278431 796502493 944765397 671810642 777524886 948344967 967833788 882537526 936127781 14835597 154717848 146971591 367450935 881183132 991053998 765974875 985482760 779475580 988941159 723250281 735816738 119192546 221507765 15935832 174953789 808679839 822877569 695944776 762261147 180548020 473608834 411996928 856152337 843396031 890141966 278087594 649584738 841889682 903972260 680672695 781954899 562954022 610872185 462752959 790397445 909283762 965401236 311165633 922075143 622826666 934038694 721616976 736549968 665649741 841203845 99777511 687761615 691791011 964146368 13114139 927012380 211353476 684072186 107690158 207784611 374455559 683672794 515045717 642255785 402606394 689910367 956707728 977789078 146459486 573464074 741412076 968947182 411614552 591480973 793008924 900930352 187185711 939310247 409871326 929263307 266860924 909203812 451115028 865435692 293777092 864082803 820367618 889629381 655940919 803157530 496842755 806724907 389300040 832782927 481567837 630293359 383384818 471322931 680917915 987339143 516440327 629553141 238724171 935096150 71849385 253271265 940210853 974304189 609096470 867426315 776189346 849317916 765968267 865447788 381944017 792137858 862950503 952962573 86778244 160463364 580745153 862905291 564001097 941903022 665553584 844910586 958668826 978758582 23751843 873947773 854950324 903461079 198193828 766913869 145061549 676823493 861229007 910208260 507946317 732704223 775428526 805929450 577980567 995906306 694998750 962692163 672744332 781111618 964944170 977188103 30994739 497078638 201358506 302451530 688316271 838338559 345269111 953473039 950771256 992847108 333125118 508516078 632035861 783508167 992161979 997860800 147383314 206818518 776324982 820905339 926350148 979390751 934683848 968401500 754396059 953074800 333801846 967465684 557445490 810777505 378268157 945432072 539012600 971751346 215013131 613820658 506430757 851594506 594579653 771731561 323525790 971796345 73289608 809965423 493390074 865263596 293685980 811134921 130762721 743087489 549980795 692389698 87329844 886246430 171878729 248713468 680042932 819643272 275476718 907482254 984738777 987517066 464750316 708471626 372282874 625086299 55645431 433399624 467311257 682556534 549347625 975932967 954250718 996938108 339105811 928301953 328418091 864277475 546801927 995263175 355374897 774971084 283221340 981395119 270304964 646217584 360022308 385091785 968204566 983297103 485255231 626955649 890837090 901377816 158248543 812262513 243939062 986761022 405125475 698776498 957222110 966570214 169698500 869968816 450737524 498907745 961421705 992017712 482126398 535164444 651203357 981440277 543530418 630150306 679397755 796608045 834175375 903604774 160215000 162465105 297591787 726246763 914741265 997966752 496732704 988399620 417115793 701012100 171904931 817715689 646172351 817033885 928833029 941220832 126539094 406151399 565932349 652112539 101316098 267305084 126862342 827035603 352702940 389021507 384826697 666375026 936896662 980442678 854533246 912741456 907474981 974420710 476837052 923424514 153530891 835438624 103415690 839859033 661313259 738661926 386409746 764114420 241823592 265546381 814214603 825995683 299709025 603060326 833034762 854016781 643472160 700530357 132796898 350764216 761220171 894247067 121431537 154458632 610386712 672498892 368543396 912289040 949072386 961408909 285101220 836497337 368863776 724331670 627141194 746479417 859385732 991401709 791584637 938343823 194928406 694604847 456217622 984313460 489750477 924836352 897851525 946835885 865296534 974695341 851408429 922493323 559297351 826764402 160276263 479927205 781574949 817987419 318650863 994267060 315137571 629287194 245496069 377257702 649663073 856627391 673168116 781010696 127250235 684429822 70001048 521006127 483416508 627368663 480637186 585186023 798831605 923117173 93396490 177594889 157079572 308643977 972145102 989736924 367391575 528782771 673629400 917838972 593435832 981166301 143218634 977757553 232638197 950623940 587314799 810915929 807632950 961308928 732968472 938154555 176078691 562313336 101415588 136609352 693517843 770050606 572393476 832000179 400664586 492907365 526398482 945030995 865637350 889048211 113964688 208225772 379338873 938487911 829824063 975176906 301343768 523500532 749092781 901573039 433093567 792380633 662334441 943649437 454113947 814021372 938718272 985342654 937126689 983882717 321284081 854091849 166386595 568080872 677101563 926063648 183545911 469816406 927406451 995187632 669853059 781943117 657588433 987991200 718811920 782461856 493544803 697361994 112177709 816040870 798156783 904946981 896238343 967547091 695757999 766307837 366570702 927831796 208464418 835705806 101240678 878779701 703874712 927138056 362249963 607086835 85150412 937339693 806574004 941368468 943012202 987983496 389778665 524329811 567483680 703216460 672133958 945943016 867447773 907157138 359308735 962837330 240265644 479500865 277705010 745532593 85745203 593298681 169787776 843945545 416045939 777394314 701942757 881694353 639397045 986473698 546145814 626996875 98522451 448069725 144774854 330594154 90235989 599974982 813709043 839023074 934867406 969162424 111674279 435477551 884664183 992876988 326153655 424673792 113387184 438115291 886448682 931347665 591874889 682423533 276627546 772803327 79216463 326308572 967598872 981633026 772748064 947840543 709105394 875638878 115719398 455225029 937396871 991788755 846964974 874320879 552962389 979619212 449584111 599870552 191813290 917289016 950189081 951992690 207018782 877724093 914913006 987877753 938334968 957933705 928227862 942879929 978120524 983984252 439125764 490697722 605639528 756205301 399361023 926215928 227096335 633205007 918630149 929666552 728769462 972600188 563458173 832226418 749551941 848283270 809452794 846130793 83638271 154182948 585589448 664821157 307332727 918562285 140969010 266968650 129952643 204323989 790896906 826904239 949301334 952065087 44898430 827677870 252571744 857028338 575385089 853133646 596203804 630790578 752209811 817930139 224670276 242380705 492540117 902565305 658356887 716520945 967279869 994189992 755471160 937142977 24014869 267121045 111312645 290218445 149681490 193212715 466641200 799616014 370747596 622243343 873750508 917380439 973344745 993515085 542879352 829686677 793583842 849547614 803441583 835146988 786180024 792269551 916181390 942669671 777154851 912733052 330147510 931473099 625902318 754644539 503121527 672969774 670396187 846111831 558190609 632162665 750696616 901754038 768395003 839210843 341065659 585521234 252174182 755494414 24902406 740879277 306324168 823044779 582517407 723436718 744202743 841654818 91084026 196375447 144149131 536318795 486503824 736600185 281097239 837779170 421643265 748185003 34908275 989199055 800824156 872393695 637065730 774318488 671237507 719410818 999962901 999969390 991099517 998352538 289140828 891150191 278406148 873002257 501627769 582197226 161046543 428610245 815641573 820673086 278743608 554770965 270564010 419911654 72909751 89679018 665749208 698838580 966093995 999300072 33679794 66519086 420162427 717832618 52662751 198739446 319790651 732804282 901663671 940285502 219646960 980889974 363759531 835415658 359248817 409385336 508240882 583138064 923544965 932415694 701718401 935464185 843423264 856229217 944123439 968445529 588126040 871644626 727087642 937654608 78343458 384977014 884052680 945927633 922596150 964381636 503574650 934707710 56363501 818195600 250436050 640235760 432356650 521303748 277628552 566080710 651314572 704152787 970422179 972461776 600166696 656340594 568332102 841359922 218254997 947425963 855580722 857492520 181787891 551553304 197105387 878489976 345853389 495796953 127071120 219877602 693686413 897382287 141711571 884011373 448182099 825809026 149442573 461262728 313848528 810947829 886322645 996442809 591443835 684325810 629012282 679702496 223925704 672251145 384234767 918635540 53902832 333259294 708864542 964825038 114953855 600770252 288316978 727215493 835536151 865534673 680904474 696245468 622362235 964068167 543156246 708197354 481021117 657791429 337555186 425811476 776360980 924386803 673604816 965098762 782151605 861305307 481436070 686129647 637293565 929162092 235996790 651070240 999438599 999715311 423111011 644364425 715584624 791663052 563130492 999224291 137463691 274534213 968646146 997828261 191379519 439043229 424940185 602923458 809348934 922562013 570815149 811690359 716793622 951257229 739280066 994204362 276555329 800948896 906931176 979327075 745345128 876538145 525529305 631895910 750477788 830061721 121951516 603351576 221531743 528135090 10062376 107728094 377044421 818322396 368197330 624051979 579093036 937079263 632939820 721312546 325705034 647358248 173994440 892794758 194785139 449251679 834299691 967120000 973348399 981338757 785744002 816607083 396765598 636219286 999538098 999643102 657562179 875995802 374669627 783111461 838782237 999191547 506105987 812582585 897386204 977092357 466581643 787669798 571030939 863239937 69559446 352298993 65049578 353558555 291479014 441926670 634577016 778043414 733465483 851033161 835255236 999878405 965683525 972468425 695399085 964833517 555454853 649640886 237147372 584147093 994624717 999596602 229557865 507439207 193415513 628835480 967563737 996931284 144360574 571036714 385030102 669775013 107552268 855056403 541190618 879305154 457641287 676186108 975758660 985445581 966921179 975694881 758164232 957832738 426337723 582684077 694551776 828669436 198740834 860487635 525311105 553299511 169994100 550713157 464280436 841899165 74965050 412000063 130311093 473772929 602836355 896063207 637298364 791540513 528663405 648715855