943 913302379 948638597 94014789 741879764 44844149 824240605 616398136 652784391 282692719 586005032 915233598 997843900 131501524 621612002 264113224 669996431 299769996 593290900 809449860 874246222 406325507 612772998 35193136 226394993 788330025 908786256 836901915 902010188 564206035 690051778 926107580 934329083 814044347 831907016 111026166 838740428 96532023 924086707 686935270 908502495 544423882 702851859 492613952 670411604 570179574 918255424 73307678 674290051 128499790 374948483 63947494 366857837 572397128 844441718 668283434 919818415 563751606 788410345 982941124 993744345 27629467 831371970 427525870 873037605 634519172 696727628 792300319 866139434 583326035 628399825 127290679 996652975 274553511 394872091 536660748 956770814 323754828 750140325 55729930 893409728 254306259 382008987 797814026 872491062 646030511 948095538 363338918 465363964 750777341 943862196 579718101 952684675 181224473 506681386 371241063 409705002 994519648 998205094 52872258 515942702 202368145 352630435 49876546 628866085 872932804 926252576 854346761 935197236 216798200 384607023 855580745 906928298 514150080 754775860 706202760 830303028 97938040 796644716 46149571 599305567 185531972 699247975 412515310 553474813 25381346 281216766 292540547 306442467 147078691 571691969 749376962 993107662 308811252 534354558 40504486 239633630 646985047 955255904 719958457 999922576 460695230 735132340 944181450 952908521 471269128 828971258 692851577 876679482 19818719 663426365 778560718 942097323 881725610 888263094 134610120 655313990 693242064 863089716 619288389 762629391 280962300 632416347 151165622 780265768 493213830 790340553 299519406 758750780 963321970 983890930 969476162 986789840 466712820 597828673 349323830 715755619 603714351 665904775 257130882 870331397 275387299 672957093 53185031 246919528 62497711 251580223 251711817 613474837 970358483 983583091 12501302 533364616 967533931 967992974 318020679 954474911 94065317 723573578 477185765 516408070 162635499 635346290 425169430 615726770 367675210 971250602 552554295 822956149 765752877 960097498 229742083 792720021 735318670 991352987 447476454 584637675 178345757 580117438 623998070 837630840 978661428 985091735 579500497 854163572 63537359 688893189 268920683 902203590 781586897 925571110 648310041 982691099 925279130 989041223 569327052 892765490 202189301 299600068 640331716 961022130 922946079 969609805 813063666 836920122 763502379 967051175 16143029 396787733 821967253 970863206 79971895 96023844 304040703 353047436 141498979 428990408 367512939 950349967 796917798 807137051 390509339 583913915 598346993 794428038 807076885 936425508 47799040 192308401 847914489 953143099 475262612 673269223 938351489 950332609 915484750 985684673 85270131 367141866 934167817 994280732 287186654 438984026 837591977 925874673 794936119 828612099 656187290 952953264 839798287 850785439 174671216 920034074 217807463 613352381 649692548 859837103 821090560 957232270 811116620 991157747 195835305 460199535 31108842 48351353 940956353 948045743 891933140 931190824 56248806 807145895 706834234 884548388 87660202 976383341 480323862 625723015 235828529 980010117 134606540 223722457 105573027 728218201 11706462 397582235 401554115 454913297 476108314 490761179 900408629 939674506 934639104 935430819 31045725 790535896 413587282 621102179 387566058 754572716 541059050 821498326 938549619 992239492 741766299 939292668 263655064 709248422 698693908 842275945 72048628 884186514 138999782 847380139 777060040 878812514 165565562 384244424 400163359 606165730 628752929 703006186 936113546 969659002 715536296 776646112 38810979 151259142 40716049 185650898 163201107 339744656 196021582 328152968 263237039 682378770 209218135 938753213 482799318 808883012 391404016 839017767 929531516 967456339 296638532 681901412 664028719 798453251 281950889 834335129 322526254 831130747 971088953 991088474 866013388 965380175 252835895 958808446 798186500 961882405 936764165 972160712 434496938 948724061 887065145 891272364 340211787 759216012 523371600 800263474 251471709 497964015 522888518 979695877 324222525 829221584 672350906 797398063 466036747 737842061 994803793 996648660 640145528 651776167 369924489 459419411 272148243 819054696 637023553 910135601 178134117 724582062 725766988 731045945 456146495 737996281 902550634 971343972 600710770 821275735 393961288 983219007 474109007 695759624 256498451 954222811 553076585 681222173 452506853 712126140 601049426 953836603 284471117 647983587 343058437 728082768 922222646 972348913 618919286 817160672 484775140 513902706 176610273 981331646 693227671 825931666 624611281 783074985 472126276 799064542 297342777 487709877 359758198 574555725 265684328 464645653 247599087 359486627 397138891 961304575 720246859 825568062 865536180 969248314 637224493 860380186 288804812 364842461 690258048 816713514 626365735 829461230 764763805 959387862 793590600 884299551 756705851 914549459 311085791 670913857 55610190 553889354 391975539 452323187 944204181 974322754 665215683 851302858 798995805 920671985 725240118 789492305 540143307 714510825 720342963 993806934 805293060 841757615 50108965 187549710 344244319 890612514 806889539 906421645 819448217 960616989 675387887 955661754 399952418 470766362 839780161 979935684 55882732 317654878 842157569 968516879 291873533 948797639 307697537 950496284 882036553 994483605 343957571 979323355 13849814 504640497 92204787 617134315 545984185 946883542 727364423 843361637 245718769 885478642 928764567 991782885 924568835 964039724 511507646 689451304 196491550 259508576 452959264 908400441 901994500 936279892 138041896 876938520 58503667 275437413 800549265 906170051 743445565 767974588 276853940 607967447 811072231 947299811 484899464 638323563 422958570 654140122 889982961 989979436 924365633 982273567 109030810 928003698 760019566 850808016 286727567 288192425 909891066 922862582 108978409 117731167 661802605 774711819 383961771 776193606 650428564 810321663 896159980 952882645 776269821 786955710 166641933 187816481 604963022 910611429 30162130 808282030 709685730 972495776 107635720 249697858 385216185 934806779 226820002 786659421 865606047 886306764 77640311 689245739 894869170 910841631 899524512 907036971 954450459 961465743 668038353 897943642 916934605 930760635 553880875 687829758 608576880 963750712 472872140 950337367 964658475 969801820 770478989 833018046 294749486 343738769 332035896 402375264 462136518 840636855 410927185 506013393 300064533 625079950 135732601 337764562 692107115 739842486 329196347 457450526 375826922 912818793 40578712 661811934 606043709 837862177 268101747 816171300 119109594 183442510 452500265 614239349 25456874 828056990 593800057 841762932 98184320 448174487 270694726 575005234 245118644 490013060 250903056 320877963 620051005 936221270 546194315 737799487 825414054 919762447 854041173 994399911 364697055 500490440 585569969 655463123 31197012 295111969 554689037 832040874 119140559 877019655 684128783 898292532 73751375 361656158 686094641 752606622 458181368 625660485 529477407 931659033 216914436 809212588 64889647 954407967 704607045 853274070 318402029 470572471 322134413 630875549 109730359 280477826 687332675 817200035 307321028 612888327 842773378 901607700 162098711 870685221 118324036 202639348 887076590 919231411 618088701 686666208 62317909 146261528 462118301 883530982 485623192 784244759 388172815 428448707 746780692 821601077 921500935 996545031 579613051 922871345 256560396 614025199 683566365 902398222 859596351 969077710 486718094 598091992 123285480 856499687 983765932 999454793 418863885 968035635 172247392 320307223 239560967 645902648 60181225 875812215 209514527 219534659 791746536 982370156 701652070 868507466 901842223 983344737 655728594 812135992 929949952 977489598 648451249 668027132 718745478 953782249 505287926 718957458 561575322 630948656 983213548 984048393 593880446 808931154 547419295 556089038 442579880 618827588 150327325 925311715 984791876 993272393 138079467 656706183 216113710 467106524 930356584 949435210 606595786 641219564 277182938 837518243 937306001 982555562 276048727 458537269 388763990 779628384 760015399 808491132 239224907 501015783 716998869 859878671 930021891 949544153 691181986 886012673 832059330 844406676 208929696 926893423 408866425 818674965 232175634 765884146 457883769 684841542 890406621 936517336 950892356 977587412 283567756 901791093 294565010 395341838 943201114 951902871 206657866 871126481 929820807 990402459 886783922 986057657 956699037 963570824 223724756 330554563 915323882 985805960 494449865 741985171 297487359 843283019 447150103 758110639 489318956 631605002 589307875 711415797 231946979 990151701 73617499 577212226 444083344 527475764 347640456 749414884 527597133 903311537 24051335 39716801 480335181 713608486 53568695 168164609 236065922 663866784 987291469 991773369 481745399 624968002 512182453 969952787 477309300 696907766 339190925 835875513 343974378 958319133 312234921 930690854 604011527 733042938 830945562 856643797 994306706 998957061 176003738 474798536 814108046 952180380 923336845 949420598 507309892 685860647 53035149 644848452 579469608 973754371 539654486 769756406 284449287 387606247 323045300 958438009 160597757 683954414 146221239 227660108 644267703 970797264 36893353 798743470 584590179 757560828 87475043 800194092 237276954 247178097 824343794 879023179 195582280 727735336 96564749 155333563 372248626 475039322 716660037 747979712 214247185 877875143 852466833 919513385 103664344 252147105 878812540 923853051 781131537 861137409 755412995 861435952 723427392 815706775 790571630 841739740 546452860 891225665 496428060 933832202 396092451 822977138 62420135 174715128 518044749 839155371 245191947 904808593 432868347 496439132 409897677 637492201 519095347 823417624 362463834 437285520 497380651 855426258 176534923 988878019 179743449 846776884 239247183 782885321 876232611 884359626 231331762 800371292 567455296 579065352 368294839 559150429 243733857 998360980 369913736 785281126 770036099 920423629 975282371 998698446 985153185 986544061 622316151 655326829 566472123 911389438 756984791 947538458 817673789 909724500 356647773 806438107 49958485 489453066 594155681 953340703 976541555 996767057 909292811 937389981 436747618 500338316 809206661 815735755 705037238 934012296 179379228 774598326 139462850 621818862 165831638 506786820 596607860 742574329 640451763 669179993 88432711 596268970 123243613 234368520 934052581 977541007 895785894 919455320 240207793 680173784 960892195 961613009 942667762 992518171 655634206 732070052 629525340 778123450 618883646 866590451 562340850 854579816 153856606 759421103 337795347 539579914 838094907 917669159 525441705 774060472 726065859 961971745 184097017 351860602 224826941 594197607 515300198 597507551 256029074 988917043 98337631 840592720 811226826 874316542 878082872 915581177 271195739 564248716 471075574 580265930 454533530 590302017 891825354 919954354 232941735 786111740 395110752 686897925 104559506 198569271 898606295 920067434 812819228 814117239 986299693 998594558 234169706 680708352 755568272 796481444 388076419 730152811 167643015 206102150 484067586 918438170 610599517 708642799 847631744 882705588 622668590 820572394 988768968 998115043 637969082 775204868 724988525 743738753 709050912 847110933 405600877 931935477 345845111 880856123 554766817 596046879 737531025 811748432 517218459 747904435 825557699 932802719 742331453 837742041 134482809 228377208 798859585 977666039 738524147 861538857 721407031 738505396 474465242 803400922 378538738 886625606 770255120 904356925 213043723 839734363 306530926 725236912 625934485 673336929 792004864 851893877 720763916 755688665 680856399 925718223 345390718 764305548 751025451 827218164 296239175 846282520 178576467 261276532 433426865 534443579 120223515 160375628 318448285 701858077 202212211 324456943 37459419 777445594 670765349 762799265 892815973 943429726 530952597 691152761 202038216 649974716 108543159 425608439 945154067 972062577 686127996 784234845 778325422 882931418 934856936 977603213 295657781 892847934 821126188 825020217 478105427 770111709 515190407 518368994 794290692 894398943 404748631 722481715 647423687 898142718 870599086 896604832 991810906 994730805 354787644 510750683 290969382 380570696 309459166 940754339 656290758 797059288 333295811 888510735 575863037 868831142 61044444 188599084 707515403 733081439 667285196 837168697 30258235 956027236 466736545 744965357 201935627 718784019 90131922 812827427 939734833 988223283 666876710 799509028 658738711 760927547 448058729 977880720 968836639 978113358 538226625 975766823 495700436 703192604 360635588 596121096 309083903 830130967 875061449 983439037 705575587 754341784 384358022 664907356 320649198 653307016 21370547 80376376 204510191 609796093 937083721 945151868 876188630 886798887 294923872 636816554 35856166 174821938 472225834 630322578 516296833 665900408 157819266 264310285 78120089 509537572 797873168 964786392 260144232 821849848 11029380 700600775 216438926 965346682 39574069 603506751 174357058 968591584 404967212 565779872 221797758 910527738 638260826 689157320 188056983 592146732 72901469 719962304 781208408 930136607 789856867 972688092 598353625 675674982 95426644 855072169 844103277 963963403 697882198 785733406 39053730 791759628 65303927 491295322 531153794 866787824 20374760 284823912 522214123 667643824 573453177 594011577 296129601 435430083 503606969 546758382 93548224 210718613 650252761 799476413 443445495 941871254 422158613 519952571 685067881 982796952 335374017 396720835 375092990 621540648 374648497 433682600 292088661 946322823 425197365 920878144 297055038 929533759 632569462 703223445 735045869 929306248 917683226 993047362 406502687 683880374 926041241 994508677 120554232 150213243 94064624 98894659 557315211 729997687 618171629 887295369 175947197 293413698 941402219 980175945 289749487 303532585 486773184 776272150 50162191 781972071 410678786 451867766 186744538 199005776 815026398 819288035 930812461 938251045 780765550 869176594 718270244 726288650 963295607 989055766 549721379 888483905 717211646 925956222 470291015 992906530 707038906 866454453 737064366 820036871 890817039 903250708 161235245 931097899 673992969 684470163 408363799 780576821 262851428 290030326 254468635 806623367 626020019 674092273 865509217 988567588 414724107 451489416 188956984 642330072 525100927 644031227 169715246 176149905 525533878 557670282 727772439 901036597 110510433 386624734 243336404 996300979 952089681 991221023 85377763 606784566 709434175 752338164 777320802 842270494 296903371 500226243 382924211 522379971 541190944 784726815 680631840 769993406 417014251 513746538 799194686 943298665 157301476 334043688 390002605 567822327 920241775 956954731 356687413 919376739 389558577 876106776 865059397 875811455 678907553 948705626 200194735 797047253 243241907 658030302 686007185 864466220 471965018 802015242 973792545 998332807 937320536 973507266 618716548 987131067 166514751 637933078 880893659 914002929 321277177 644267808 488305032 882221365 207431052 499919901 829639499 912922887 15034958 207584380 395079967 669388477 825879700 969009996 313610508 401047329 847498775 956786524 386967811 804599896 48168239 274946003 497090864 860310146 96342429 393541803 143046648 231831790 212611135 241671725 302698204 723557282 572951433 583707356 336682929 440692473 482351264 974156772 829119551 888020921 756183550 809125159 232781804 836213892 583011346 767488215 805172861 836709889 843534323 932986791 964855189 978136423 335372790 744045104 436735882 466040116 584460376 861030282 959028793 968505150 325234835 522332625 10246332 819034200 277738344 349843252 656532487 798021258 82734847 277209867 860079071 952571309 560650119 944980011 425960801 540825294 657679248 945989350 128228474 774577663 337601986 508348568 176231641 509137228 749096139 841474708 384676827 472050763 759917262 952137843 96885162 522807596 898555946 924424385 555177094 826656297 271961610 391547669 802963934 993313086 60724146 117923933 280534776 987289395 689545718 701075754 725499981 962740915 843780258 857222703 462328786 713221949 451348662 549334111 836304486 851278487 459115414 848815760 928518906 956430250 246829651 939079038 334064303 360588137 376235831 429224218 525986813 842762290 929953470 975631960 257151572 411857252 592112871 902558121 891243028 918824066 66926838 949730998 273971218 441246976 57474370 219339675 936201111 966200386 723589583 836654848 814835740 899788463 132639487 241824157 649077407 780480395 858292048 895233132 157610338 777039827 327994301 772302270 210855244 382814167 630694597 940945253 744841716 857401495 713933186 813118029 296631809 994633319 507904950 626222079 183119030 459223008 154399058 408785306 187606158 762927535 763256595 804221412 684373400 965382725 197732677 946195582 345322494 864173983 812811239 924301189 171237572 608274805 759304167 803766761 499216438 598576090 553931821 905259643 758401620 999659414 893465252 935487355 655270914 900308541 47152540 878410967 325066433 915503893 446975631 793564409 238777648 284907719 629150921 765438337 389664813 934068701 950885775 973334134 850796428 850907276 775628142 825558757 890187510 980398761 212664881 938012228 86209253 639994984 797020972 991173283 955483767 977970021 164695171 884917887 378649344 810569856 193174067 311748805 731333259 817830939 605065031 779608614 985741979 997783885 637637919 842489939 963305990 971813779 678489721 729450191 187786669 389257196 831635978 950842927 275438492 814676905 469360120 823896354 430675657 611130610 166183594 261429495 896789801 920970914 988282226 996890442 452416312 625642957 86235103 954729834 541432320 808695467 976525269 981710664 709815842 960770121 413073005 894941825 415257754 893005513 888540381 989767699 578409737 713757580 407276474 786516419 274162675 765988850 548170894 817961642 187949826 420738045 835331327 909913809 988195394 989705933 463080465 784217312 306046090 312872340 495357170 546364776 972113944 993939553 145864782 357102877 891622561 908521400 539016392 820924211 751440189 873257001 311192169 326531049 622229884 921313139 74838811 409057045 32028781 538028621 250919141 903377591 796696000 867590720 61209675 519627359 485108027 717843535 478366973 924616989 364332146 978148934 55313906 162980061 856748695 986979942 889422436 985408390 643710724 921095796 642362636 885033340 323783583 687201930 187010842 931653102 211358009 744118368 842513746 933960315 11920210 185897819 284732074 789458493 883594108 934892609 763839602 955591486 230243554 516137728 941332051 998872350 803422121 979084687 874066431 888141980 776139107 858364167 158668975 767951620 954681783 955815106 702867182 832733838 914566228 984300423 540797381 753496539 445143331 593545092 616966587 872615942 94980605 922386750 399872870 686299578 958830246 985786118 770742339 869748843 945158257 957986332 259957482 640675941 347087658 706192828 986397197 986901723 258477893 776979643 787195522 917239837 17705301 120073881 981781665 998107431 811317639 997134256 703827740 735747258 106647500 582837331 432197586 668344043 17411824 899376021 398798035 716257443 504746881 692807122 902600313 903691002 124402587 460312484 940499071 984661329 612322283 726331769 475450672 842276996 673701678 786637958 603823455 681316025 21271976 583347582 256083993 921015410 595637651 748510243 917086034 927987308 247838446 301502032 79306219 354657209 156059241 345823218 387106832 626206781 985669749 987222614 142508040 924828243 411365896 837377665 686290260 983984364 952841236 998818944 256248234 488749258 24514839 280463680 292049175 720606698 995007048 995400872 427300920 547326961 533481552 678470605 393315932 840037219 100476812 295031787 29874782 503524127 199949668 435236811 731648154 795006484 692552299 903380818 647759399 815158804 779285577 888973313 194157517 885691750 106731331 693339540 91220427 371794495 829933605 841979098 684940681 933831670 212907103 332313586 748550488 798821188 45115645 439715983 884187100 917457016 802125673 983293298 386562296 886999047 451298485 618524762 792412589 954344210 116286772 412613218 80086171 368867033 503572168 764683650 115759843 488154360 953281363 971230328 398896900 508798676 935345619 972339026 10548979 191911121 115553828 810109549 872548236 898728692 870873063 891063926 640658701 794170088 206892682 234456672 364616477 497787565 132736059 583390900 839734134 890779444 941353866 951987865 950015406 984367810 721081525 729760529 669735587 843698173 152863656 670295686 598749477 872944179 394970890 568833993 306969784 526851094 875181736 965310400 651204142 834672710 721585935 859763465 145074671 177160583 777835833 847156666 505884352 657759861 184001342 796388702 612477843 862652350 810274148 887985830 805482229 991638491 94227996 740629580 308187202 714788548 861676644 894397365 300457760 770064228 697659695 824639220 359534531 552890486 113962966 244025605 162723244 575804769 312300798 764871664 119185000 769206640 116355657 693892343 672501898 798278630 32812984 414948230 513000438 634456208 337028200 862424519 154837283 817317768 741223972 988136356 845401049 977424225 930954761 996113700 273240344 507851117 622883617 788378087 955960683 999339441 620531205 901495596 590582479 760421035 720941066 868011961 302184495 375960369 978535415 995353585 880031576 986285414 684036861 753831177 655266909 815179585 363976025 759652398 976991011 983846666 34747644 187691622 181632664 677564204 252712674 282243802 222065154 608861018 253013075 531448938 713042866 904927297 205608166 587021502 454708974 813698897 901060823 915780470 828845147 962704331 118773466 218899486 60961292 447891356 338661033 920152996 707219484 753635097 665777289 775366879 649368082 682197605 624413281 995906066 623653637 929463121 449103147 688309881 912813883 969365430 556923437 735205106 229379281 324431959 426863377 908870801 813980099 981579807 650346770 782417750 966500574 985856026 90505059 575056301 909324605 917609172 847766560 985302389 429280405 832407349 658286202 958359107 629131899 856346962 665141239 747625579 369414176 425498119 511726337 981503603 976726476 992912658 95685660 561447941 595361150 816921225 983848723 997703611 813323525 940551251 12733373 527869876 341423532 896759009 181819193 799711261 185196431 216958819 154170541 574303669 801720630 908809844 445254227 854526617 129689580 763575125 404985245 999647097 220438013 666657908 809124603 991009902 731792772 962233883 932953658 936183623 238757221 558318963 930557862 963495349 654938630 920075526 32849759 184953354 685954243 778970623 312344461 963997623 834016310 973717283 754979747 836648862 122967223 759098947 716376161 916329385 238812855 758398712 730316730 757029162 760965476 868770060 880819985 948524537 76902877 641791287 700955237 887869125 520132598 530951962 667606218 761334552 161557082 309729267 52469975 810713850 309035949 369653286 109522999 418845279 967168907 994258948 10064048 310271229 972049985 995506207 58334111 444989247 609198746 821006610 999352853 999874340 290272424 818606200 703365150 800793268 939076709 999431091 840835425 871069008 692517556 720387084 790806054 823002672 328040033 742234894 700311414 853592445 305347996 964963671 348840822 970203898 129053361 780396604 789842978 981442620 105838382 217084166 777973582 901537801 319044781 949495728 615697789 895078687 920198932 941663124 318222631 910080645 852519864 872992041 942194940 966389164 921118679 949771835 964513514 994439013 632078918 771587756 33239228 328079145 170423067 978543543 132799496 689973938 715283417 850424388 36594210 65059170 227064388 486658414 316638666 944801127 628858676 757570503 774243971 869057619 85522997 413935784 451541479 757045803 130789376 431190665 953738996 988544916 631731523 769877656 363675077 754902359 215964620 580451697 430752721 578855855 474221649 719709523 395018369 709638936 182498642 693957450 755155963 826774661 901384767 929530364 82718207 403250549 490470185 562590124 838370840 870133368 54434762 626201750 586709866 826107681 571880574 850499400 782193915 872051830 166788473 693910725 85932226 600933376 314427261 355308989 303596863 472070578 375613173 609838701 194891181 205248091 347226721 631992641 908668611 965495697 67168895 494263831 255690752 417895711 565796788 760698733 210498867 675798833 119616654 971758903 448954687 853622081 957761754 999462195 28070208 704842361 599832377 920414930 544417520 961022275 670124938 932375156 12630515 166657842 237413781 624770441 399187579 614980004 375700435 858552984 533208713 821515444 663777475 860464745 643817104 741154555 806146731 851604494 11969787 713141110 444734076 591313631 490355692 903294317 964823119 989251470 692772249 906727520 270059970 359679063 144188729 453711552 671135334 852908796 586518628 724429517 256738535 779746142 471538574 550042846 243304031 858953418 922671571 948354182 875172215 895353209 235745304 353182965 131771260 381541326 383007937 407957307 230825046 379345593 271692942 978535905 750308946 845472942 177172917 977733897 601202743 819324697 551764748 757797801 523633788 880232046 591189381 860604213 394756822 483325727 605180791 935148904 970409850 979530556 773829210 818975089 38123817 642720339 138276014 183743034 233883267 457172302 935081441 986384712 807909785 958178111 628209563 710992927 698261043 788865598 732083532 941895009 828125477 960594803 492321998 629845073 908094606 960014683 309195647 466790315 137662007 955632079 819922951 932551421 643881966 825138766 878845487 916941745 990803451 993469602 976497678 999076196 198050806 329947073 158127629 718068947 379407678 521918536 718241002 740314228 917946574 935318430 534253107 857603387 254526950 747806612 701077155 991425729 148804951 150959268 690680475 949234609 719982918 820089799 801446921 829316031 252058950 599651240 225716108 530672002 965465546 967005858 242755319 537327315 173427956 758353893 457965475 770571264 631430130 968074341 893842293 986266369 872163481 978438882 283962695 364621621 625091832 937451134 160953434 631159185 936390195 965620355 72728566 539620028 471873499 640232659 817043395 824400990 386839334 581340407 101251303 269898549 586314027 924870795 643828708 741692458 493882214 789465585 392651142 649622737 498020821 526328894 800910838 986902491 122021982 339572721 228002029 449971463 839659183 963471060 805607950 877286515 867270348 957207184 719719417 922127698 292465233 475381809 372356817 664364160 692529069 849768811 970091354 989152277 55435558 745537678 547145856 955103309 463808292 838658040 381528467 497896303 933543751 935091188 724709414 786711827 903535622 970940008 524850683 767522428 872971219 895656993 114679367 913861264 253049022 883185101 626219338 959714528 121028011 692513642 459146229 694248671 34352704 97064805 500713248 616849078 87169212 394156080 390408484 669835496 98983782 956055163 290441538 917448368 492605199 556500833 286476040 522172213 412621379 565658450 259838176 793952076 548423817 852619709 699282692 933524087 810921406 905644519 18554499 721134146 633121083 944299474 879512178 920875631 346783542 926357087 589289150 843293997 31692546 853404292 112670490 521383283 169957110 872418938 494884111 516311799 561171999 628610712 934856649 947149597 142355616 242152870 19557727 435394091 734448704 740883392 480959772 997346893 691206312 999467311 545638044 731196773 117839362 727083400 692395526 891369413 729772487 862351009 372211769 754389795 659399342 973972059 647039645 667353023 573455752 994112404 328886143 598140221 967630595 973737231 782177455 859814215 437126713 967903650 362647002 446721478 622414695 776731260 902628940 937238998 396493741 436770853 67386361 673105865 946033280 982445138 811854363 901692590 835668162 888353900 843971039 877366704 85235012 447357706 675543946 909521083 842396396 944835143 932019896 964220029 463945161 475171915 141422704 861682536 272966219 436756937 642682810 896128028 543142104 924016458 556537075 972877495 812022538 841821729 348250160 378828987 290505678 803751977 481106845 849117705 847881422 868744788 365203967 734739640 977241585 992119974 355692549 855911782 339714272 564861046 774920915 815963907 369656001 575755472 841945861 878509591 622398265 638360475 801223854 981365435 81283179 359336271 884332750 939084433 586683580 766094511 213833083 693076575 824982754 979593848 596929525 666760987 984078056 999009901 231301753 376788069 241211438 340644384 246663166 440327816 294624101 613469066 60450493 201446363 653088909 791622507 730115114 810915150 378990776 823967269 182588066 357025066 712082011 918979879 950793002 977604543 594082315 707480037 373139428 458505028 156109862 717397873 122577123 797791778 328006898 920942581 634707293 985900898 164662350 672422171 562018361 994041575 805563499 957009398 398558481 433160309 171907650 776975019 800515563 953354930 267553900 946091942 597399074 911972446 969283252 970516014 112970621 125464629 399437179 958537747 779453028 872145063 686312691 702540992 760863058 832181821 281007928 706360003 14373407 775697981 690036043 981956040 558815591 710763832 148107548 968403075 908881293 922527336 353678809 609427704 883762845 989145210 393761163 516394924 552513154 773402471 622790039 843334994 511733906 611891166 221109495 834883420 232742797 323834394 727705312 800737611 876202196 948636521 316798456 486326049 771341160 894670351 693154216 830387467 745912561 817946914 68888898 283843841 372838428 636713301 428629073 763463368 306718358 394338473 605309940 979812229 955462268 980534511 895887305 959606197 411874293 924081885 693526847 938218113 46873085 566089660 153388292 670573833 345105818 557800750 917259692 976837594 682633895 945270547 25010011 789174150 566620071 706059196 392008313 920048744 554506306 802635306 771750982 901598636 336911389 858203862 483113482 834474655 182655306 679469702 651129640 675368916 580897943 728377391 655994572 975465107 150293921 898975009 960479931 996455247 442087204 707434485 378656120 503384903 246028995 443468460 43990412 504256924 634553063 962352718 383807296 648895909 411242566 900611795 125571698 804011892 331232729 923514273 658119466 665830999 598046944 848117421 982142053 996280012 770837502 958310471 626533669 629277052 902734548 983375556 165488283 763157812 19190204 478552155 219156343 229902913 474777799 959497267 787227024 915712500 264046769 615616718 651257318 798252067 855603690 882311216 899888898 911593455 706182635 963838241 205010125 828539845 190820093 413752942 295159187 561496641 136545890 798537561 949699093 979537086 68570552 574731517 666175500 815889680 447612278 901358102 955032890 971343216 950043529 969673634 502954277 537630301 65206560 159195656 47815734 105748359 957843422 968860522 441491331 621075523 140942213 269791574 976590463 996733701 618925774 815269885 587763649 746525863 483119183 563200007 617633722 758539252 383092266 792625248 792884909 887404398 19878671 805383289 945365958 952954239 987228847 990792123 557054290 793324994 125387651 371142336 432696875 948042399 424789408 559332903 970024951 975754418 520569749 930767873 853503997 943328037 841932348 973492010 168690744 882786425 385093961 711913016 93698389 618420527 330379761 726974515 323115836 604670177 186748878 728687984 90498851 433287102 799921990 829635640 906039899 918170168 397932807 618699684 53098728 344389657 488281338 528386290 949829112 955154618 862371059 996669581 61722604 185273301 463798160 980394689 30786713 963780779 436331295 526015483 572573829 660570829 889613496 902141423 718165197 958999200 947027608 993967192 610589761 899429877 590054039 754983229 619781201 888542794 756583342 896231760 815054633 859084169 94343642 972590375 315802569 949657014 700374323 863457387 190412691 504390668 468258657 920385802 116557757 974459378 331257238 856687423 796786878 858835185 689898957 988398487 426800983 665916407 905557031 948178099 413354146 617777099 754769845 975388082 549566370 624428344 975827617 984484210 274906838 409151180 251785413 628376066 99678487 168101386 487842841 982859052 159085828 894968221 788970177 823021620 158054552 209489460 364769262 879863305 192876804 402153183 301793308 749611459 643877791 713850903 179154396 337906047 340296248 707542687 501389717 800136999 462882408 935885574 655614882 983881692 337056614 405571612 675180706 810411482 604258345 963531042 206600795 218645249 468786523 975536808 206796426 931079764 621106505 717317725 234124073 635666202 216998790 579403068 620357298 793283164 930619202 992675295 420348792 722131539 151406611 383272161 959598022 978816796 991082524 993616232 520240543 591613890 511365445 793065071 211033702 478966442 369520749 697042072 841348469 877895154 552251905 949149202 29133407 660213057 613060935 799528879 359307630 683250806 600582940 973340890 490682361 518886084 662263729 906664120 21094227 215227601 681015432 978677816 473171453 797438281 412159647 565541258 447903323 896110338 802803064 949123983 247840198 381270388 449255876 831600270 917047346 921733900 183510830 372689974 815091794 824056120 212548512 582634463 145234675 686723010 635025285 933056283 651956577 720482809 284928900 502757506 215876164 740875915 574675695 912024048 160302431 560992329 35023071 934515127 400266959 979477038 325465710 898121206 146165772 170300897 755333802 880476706 16156658 294081783 482014746 989536960 33334838 210770898 575295841 724082972 392999738 813772413 364867109 479229677 64483725 367138186 859870133 944278314 578975978 741219612 194124952 953524451 47216737 214899813 704140197 944349613 269929288 381028363 810275852 869460314 799721062 919742802 851770197 890650078 156977878 718308787 353791841 565042679 809816019 815296594 749201392 996863013 192956252 734387482 437899403 792658822 148647498 211392706 109893225 757783321 241470646 585517328 480601321 865193230 360163767 814681831 177046337 589241151 645496931 645701427 205088260 233876973 36459162 613913047 675110835 727609399 893093114 919365057 921543832 997182192 863715401 995218909 281080596 704959336 469120683 746583739 326328101 814623026 271419441 738720372 261503129 577785436 687130521 878577662 25641574 268143812 597246848 622879319 75132483 423005004 647168535 980595139 129754311 739418496 512047602 849355792 63638066 791913854 760860027 972467584 194544215 776345212 838506119 853941422 257520759 817975315 186499089 631900465 409423361 465883460 318043642 319819505 82334510 751900774 518740542 731129714 714054332 892365415 523278117 956778860 153154922 326874783 675937607 857985415 992591222 996914785 31390351 388825729 414429701 626218377 835570867 944650660 582422560 938455551 152048793 778491706 107810381 248852310 913563486 956598486 828706836 880928729 895555728 946048986 55607648 510366080 277840793 912183313 30636710 428340531 35009991 531108537 23567139 432485573 96206520 879763666 377427732 559231895 582694234 764973847 360552086 861743909 876672847 985952982 676370330 976587954 363096017 746525556 775226273 988140258 83225674 90967448 985364651 999224490 887884603 952562254 137277873 768316733 728039555 787684484 275249137 856497901 461701805 701175148 653697258 862411162 838481256 861521671 833144054 985137348 605672619 972923370 14415413 387858187 681985963 757414870 571424979 650867223 747645075 759651916 793788940 925417290 31161856 568449741 226490896 374937105 752939975 801795340 792210380 853861967 631393319 977756034 270345859 502923259 335792868 782542669 922631129 980040972 135392126 382626235 545939892 556057269 291150953 488221219 238845676 830058767 340795641 711571039 207669986 775054969 388781762 700737294 848019960 850855629 89532981 243896739 86450480 417586270 705735349 951045875 420120298 834163596 294782803 994025129 801525081 806570052 621184214 802528373 203917857 597245328 47455080 764864019 671954041 781002220 36995556 524319698 57964302 350767285 871229947 924093791 892937448 969703927 104396552 697827258 315570199 955568483 497173422 504351198 79116250 484866997 891608989 990997614 764042463 895735465 979769246 981425884 531015750 638994596 894645953 945302765 327046400 382027565 900438313 996011756 447237170 644502520 352285621 626026185 594691555 614301368 743467104 855633309 696920941 873746582 502753031 658481361 570624712 837570956 830238656 897028104 150815839 963965206 195215372 439774297 843239034 889820845 821021415 825853425 486541592 539009585 796722315 819752309 508949553 775650855 502023861 990892162 819199943 927667624 116555563 667685184 128772472 878217067 864803166 921961242 261019316 552011404 972782729 974712004 766481096 768289336 623297060 940995938 668785919 826002676 211035818 635603611 759465499 850100857 854186403 974543554 693814157 875417266 879342804 879705366 762339866 875292318 185687180 343190808 707371085 733791382 494867390 539357400 525767072 895100616 36896529 77184981 10977925 721713146 445740186 902494063 776635571 935022260 375573836 722798848 323485379 640947321 101888176 139789921 974344279 978338020 860420186 928437196 877205186 976764113 820621822 995285156 851353523 852046027 763449205 851875363 29469969 54041937 365712163 672841632 465956956 489200162 946660203 965927117 825581333 972972821 192637208 211335929 273639699 538896736 345711320 796614696 902794124 992539602 271086721 470811809 39716632 707710753 332782664 823177565 867108426 939850749 276352732 473293847 879150579 926514889 703388584 736921470 434705541 468632617 950270597 951971637 410056795 832025727 436310051 502724160 356708947 874221744 687945014 741349834 341627351 444878321 791830507 940486360 333477752 595728688 671934706 769377262 600725370 714313039