19142
749186008 418033862 968694191 923833649 392108869 746721695 452814096 908831179 25650199 635845774 276690893 386471465 496267235 951484735 851037282 987711471 314019747 450847624 802102300 77119863 987534283 141929316 729143368 522626864 554393967 282724730 86009163 118680325 214231982 441982790 458875307 300365610 215833816 934902378 136783918 674585535 413547517 283127907 852333678 669295388 403920497 215796275 771225860 813761224 456853892 376517818 833581114 390516011 95602929 923627378 706815031 137428199 390679791 345942707 365832966 432263369 793296668 51092784 150294070 672970630 962637664 798411442 158102736 967286557 140347219 374610479 378130411 984201608 640854670 657258422 931026775 235731088 80619575 418910156 606668155 619755460 75960487 908741646 218003600 289370703 93660990 456343512 332181776 964585752 9375713 309645866 177885734 213584016 817546804 966578921 600493056 157700148 542766801 185013353 997807220 853224134 294438227 354710884 50716232 963593394 16166560 348134944 302569701 944889005 858554038 749204689 369532494 85098954 113609237 168798605 93972028 681905661 700512201 347772184 242740142 484501220 357125207 323077354 361503816 70174405 596354731 388943129 631476060 249606263 29512349 762367735 590476403 372708128 460878279 185198334 16795668 729341960 40341506 548914905 95001795 492960805 493731523 460401859 809269348 819242269 287556226 222403108 914341426 471342057 12733736 645657307 361164040 969928581 225106091 249924879 728270074 31023717 578210167 744157913 633970991 566085116 39515909 884588470 820019568 605693476 172278328 312325925 290783563 725321676 324773798 858208016 551994746 96034404 651661603 721269402 49361902 744129102 127136905 598808836 639727339 110739745 483024596 637637103 665221918 579873651 771836844 934478465 114773676 360526216 40351881 144887189 378962044 78088007 949638156 203953609 732437268 169477221 85960498 982073796 722651760 947563865 588956505 561626699 368623373 304806577 432597342 793194074 584083632 192633121 695716556 721496816 651582569 553972794 561028487 464103568 822206384 891451427 429939307 430835540 959643125 535228959 100417090 465379528 767187708 933598653 912990750 368848543 495812967 818242768 264687511 896904222 723723596 449330196 506965187 773888251 870831502 19625396 633915487 558428255 70727736 158147243 352063962 865940778 533040954 602104301 859950292 237183446 967853477 589714058 818663114 930649787 929000088 67758733 670058431 108453583 971827778 178192926 556717101 864895260 561744099 165310804 789068379 600306093 966698657 515643510 63541528 506180590 475074083 991347404 451718082 693463923 480294117 175619423 489486622 695288609 228249980 274866033 406660608 306685875 609804677 50613731 409248149 604831441 268312139 298716405 917045085 842223518 915698230 420992474 741644686 906452971 76019256 30946224 650965054 223792246 174674775 124678049 720497912 631371021 314296892 452466265 570799430 290708039 218952442 428577754 536263841 398476080 872650238 543423210 918007884 948900516 128651644 7991785 563649468 994904760 446977352 734617637 96629664 36422616 806163391 534648146 475699244 382927089 474776679 405684658 999656520 915537810 992162210 712457033 504775122 176687794 979403147 859548146 628092947 652373343 560550077 461710534 329189046 843604585 985795619 61425933 344662233 355947921 380535276 90963216 159354223 41884404 803385532 369297228 401166939 89079310 496199652 449031959 93659959 659608436 733051178 947495440 792229202 808701114 488569776 847109869 192637495 533915832 275539204 514229271 510915281 575982107 809443642 25213930 968416529 589482839 475240290 500332751 55855995 656612446 449309683 575546396 4526839 203440785 428105248 752432897 103050289 972991434 621390995 886539169 153587228 724342389 725230983 792300052 720113434 923211278 770477646 883104797 461848237 887917891 850167883 240608354 701162819 522003954 622299151 3953160 688151170 26714463 596978123 313454198 226731668 128760901 635454152 859268990 707614896 204615173 154436871 466325068 440309820 248026905 761820432 773618775 739132319 924611467 67073455 734573933 754461814 766749355 585576761 705493764 983260959 713084866 816806376 446718993 423483216 999611550 828852963 990982655 595986917 784410976 426183761 125396864 944132897 501634882 371082371 574439968 783320094 202932246 429718259 997209118 826250221 862808512 426501112 409747249 433659617 354131452 529410930 120959716 671515663 749850656 323831915 408893169 477057921 687673956 683391321 103348735 982517415 812184516 667681862 669743464 673912695 200094390 565635726 486752384 277171108 273604822 212070667 867929854 543361635 114106755 757019632 502731482 451505779 551774904 806895677 416111811 624739911 97374211 71982387 794441439 822582328 216100833 24090095 448679624 188570046 649601318 637713842 611532371 153414090 362662369 534972204 779266734 97031830 872767021 893413690 911208952 727659038 323469379 559786419 110853106 635855779 973875431 400482165 966937971 676876337 833606219 189778095 887022285 115711544 867239750 742418424 354739867 655898442 188474536 453768968 380694181 188212751 808479120 361572495 52274304 186466951 695682796 448800498 75073429 320913505 277002454 978741899 348618444 208568610 103109877 522108628 513265604 278160657 755305703 68475263 919891478 315525433 252020608 534672924 287680499 85105913 321142321 332032581 754293979 939464619 717168079 892918798 857249925 73900822 892720940 352507064 410248687 741055327 12509823 304420661 986351683 495969020 958455852 806707673 225111904 144750753 840967378 390671705 326134457 632886957 197097066 118275628 742347183 219040708 866358737 501700938 923917056 102168606 250759113 792412522 406801609 260064370 166727662 919702545 911074812 591494477 336697281 404430905 722138888 489191726 357356231 76876590 345758471 571946956 774951812 184631422 503065780 660909042 733063676 341690457 105552949 642181399 341755620 573850320 570531598 99048439 448410687 328812550 147654752 428827515 189139005 170604008 275149510 158737908 771208663 353292427 722486807 741651406 56191604 645042368 945603269 726662917 463117802 707333910 310506998 555584716 678339009 543727261 280222719 233156545 480151733 52078870 51786096 120628277 418503680 611197968 624515453 603507813 382519637 793221814 414579618 315058756 843421181 575412114 466772367 832585639 920377064 791762488 723643766 255396302 767707933 890221152 683688130 38870983 188863708 761784097 435326885 821314546 393827327 677233052 744934845 175285219 844899594 889557489 577971530 559113164 842719636 317332946 164623388 672858483 371822545 493810094 69707346 78588959 271984638 812144918 398837008 351484887 751535472 21335114 436701800 237896670 861506045 610435582 136216049 838417516 821057871 665530374 900092540 673751181 509785092 68831347 179325880 908479110 867411950 431682514 511418578 126658302 429245270 881834969 439694006 516027225 82243390 573269493 332923026 923142823 748417024 801375618 920370996 369570088 551644833 460461977 740253736 431835016 947422108 87443670 958074032 567196777 219569077 890575527 65591629 503886570 176357590 307294910 618890057 646721929 863244804 148719834 613714206 789076464 540702215 164451870 928967238 673899731 858449433 478732933 994742496 399057509 854098691 393772190 87107500 791697809 983088252 622597087 73308813 403218081 310064212 435134208 390362359 183388997 345958301 16996601 896779275 679578318 561420296 309543924 97506010 909320123 80366035 819875707 880582294 112341675 477854361 885216043 299716041 116193238 648427841 270599021 146145271 541990323 477512044 91714553 62063379 890545996 349912365 157613400 954997617 647602317 546698537 396218890 281309905 438481085 454705690 694008563 112517995 276317154 27297678 136544722 228959382 371024198 155831616 771176740 321543591 714307601 957819385 788903685 46538756 821497397 882746786 115927029 935625074 947431849 669663136 158955937 354320153 497867672 766834505 314151131 328794426 775173369 963656684 438124279 280848055 742168683 537215809 463718512 276128175 232414982 156613883 756156174 869597310 744293399 480146064 395052880 791545072 218815704 292266597 669008635 251661300 199485185 122925931 120567318 86641802 255796842 721593094 983342300 311791287 228673814 564381101 817115317 6962192 16401504 82126927 197895806 811912287 761229827 723886778 997746250 71156504 16284521 515482387 22754337 47949005 19677233 608257156 383435727 962563135 847618364 514196608 800846290 673686692 484081037 910871570 653483566 695013424 110790411 176413336 233160271 671957410 142588766 246629715 726314924 365839393 456422146 903019687 703893217 517392515 860816620 940690157 13918281 754582220 35093215 304294175 979968723 745098919 720992906 211745129 272714201 377207434 533229106 773842094 265392289 655507002 652760167 327063840 172690554 382528830 491501311 541532816 285791842 780398346 967965557 416559585 553476663 979789810 662068379 542677265 822272072 312140754 872398457 940274497 61272870 610885646 692013744 769031879 939580990 983503571 799597799 118010117 121109450 314619132 933540816 485898774 837080022 216894839 602683435 665523494 965164972 793970705 282774888 17974693 916312161 452696949 370229945 897767862 702852402 206442442 56334333 831555451 310869143 879686157 17242654 825137199 100971814 391819662 143974012 718642383 45843032 762409904 459412188 676419100 177239566 651219421 330777869 74177504 298998371 134053092 602907314 76311623 299114749 515191417 869686047 408062711 699457307 175871028 570379867 532583872 119033735 781868457 264801915 981313127 709895160 515815684 242725246 136342406 780974844 315922083 661455918 341367959 920561163 684206068 825895336 632856605 162092001 173916037 205176254 425059549 520353845 807496105 605606970 162214995 963570048 617711024 580374135 12417761 206454257 106958339 709717805 709925768 976341599 419394522 587079979 588977926 116221009 801525237 263780596 271327699 195290548 170660058 458117247 548070067 561666743 366746678 654972222 681279716 984300450 288446195 237529094 793162154 210988842 94102074 801160656 975287057 334080028 880520762 826652148 142667925 846689181 825674330 564516194 229008524 158946299 457210734 281599929 543333789 916508216 127918799 539444355 633934811 697609214 602068915 622595398 98371513 839720834 18018954 845525138 744019127 202673532 433779725 172604723 965121680 785143895 431273608 300204104 556052056 900186865 977685797 625093412 354953808 211402479 273790773 936326183 667104045 699354182 550563490 458437020 473130815 634919372 438547001 834489681 619995213 899001829 19863903 307339930 882210606 463562873 488733107 575927163 871818657 792415310 350627113 432906996 130563814 981537590 748739234 544201826 30121604 976406639 297741812 269575311 526343823 743380458 416046097 748145856 934306990 190177148 305061794 601725210 915479314 594187966 134855260 748953519 35123935 352689556 567169186 739597962 77860003 217008578 259144163 981246404 50412247 163067980 1821214 776679458 571006334 473178587 21177193 413290688 115034871 662785200 919458279 431403503 374954700 997604017 407901462 962483516 168692303 725688095 963827350 903595940 868019894 495202708 47432370 411844869 456960235 474583692 50571252 88019616 326038516 743411826 728128486 579068454 652263013 916130007 96402760 71569931 162323281 962871444 814657974 958639998 482423436 845891697 713437596 67991329 49497476 429646879 403609089 318546933 347973367 315003213 280846730 246146892 881213098 341543393 499736928 563870165 809920113 230115557 173196965 722360845 705322790 734914608 112635744 758073075 852385374 993337707 987860122 282082462 550978179 793625918 997345174 503072739 180310844 429680197 978558105 829498336 538419598 552616284 512984881 285185831 254142772 219833088 126213298 333163760 623145730 736489131 576669110 292124010 934718915 471108243 57737937 74935685 778549268 329955793 227415267 947932681 78838638 5069978 261718049 597655786 254263455 612864528 280299589 308921673 134076134 716555924 809700650 464775460 789132010 672252784 118385867 144836624 800353595 174250702 863693139 896330187 644822446 908982653 553590753 452043640 240718867 706634481 64226626 772971727 543299021 496438331 224520668 299133846 445616850 227323559 475633267 795449678 581254328 179942808 523380329 689389825 990468742 222474027 725248759 611022438 472996622 388711552 210781416 352217740 740893057 924225219 21989365 720024707 615380612 579228054 227024111 270377049 725422333 440235522 642035936 390395767 650616171 235953443 303961934 569634520 184924796 159312484 506503501 327899404 316470967 875589245 758452318 864639528 879219951 37066945 270761452 864464248 528631184 469646920 160629611 10371682 357529998 865544084 506335074 929262369 108305523 774447818 875603552 248048482 863956970 751909810 471740495 932606507 700923653 91820790 332752117 813912148 514585514 959406040 429963691 934995003 566851213 817132418 640827017 345959614 464622943 441500299 514708996 877354979 457288344 573442072 110198143 544731306 482115847 230986336 383679367 339766347 144046015 330268924 603772112 558627145 68308463 779193799 316033064 249844981 948442816 686991467 390899751 567142890 682956388 246301246 541440545 864021826 967797297 78100706 987594340 179939500 653342002 811341406 855121811 154053984 236475952 42544259 762374213 709500141 385316821 567472825 983935644 131875061 452060637 543444971 562153889 859100271 897776776 211687763 200793347 676614587 19684566 125129030 568172218 608839771 858740001 784232363 511658649 411589321 77174268 982910789 236538768 480532127 8082457 402941757 237721472 567201361 459477058 703962333 746901923 662911761 168739200 731744434 710212127 73339853 556309208 66158517 913242219 281924528 215251423 887720143 870253486 197273053 806934973 555980727 520505445 438621405 626637417 400156933 208244951 268544782 37294805 100208782 479185350 152631227 820982891 238011648 629364688 549218468 66261686 619804375 78689709 775224229 981113666 760809589 33081655 873964747 577765330 796803222 294217591 95783694 364397616 528320449 981444088 947527847 372758250 702893629 616935063 879333461 61403260 934987341 54856904 136477195 566206688 508664631 873873425 942505558 879732690 173282686 864379459 650907564 653967493 487136660 909391838 262617818 761341588 149501721 386811481 996426865 269317760 11017040 820304831 436813132 207228080 801410022 751325353 144716507 71122846 92470385 665180984 938977767 668462018 784232903 971882599 401268888 192205618 64422377 82072310 116074356 756253947 369628638 946780182 652588837 378897387 977478185 392315746 235255835 711835322 617342637 115065938 508265075 389330867 535577379 257494423 199325602 54679136 614810928 661071136 521765322 655717718 172940563 434952011 561510484 843329544 557596324 313156318 260746974 46398096 83145311 940432674 17469791 543590514 234643819 877270496 399843088 603627381 733414637 326272255 103022064 667349844 286271640 48659417 978758750 958050807 275970584 700297173 134636675 829797008 266372786 244344203 333369866 475508832 300062428 499287188 324978842 400484280 443518237 181581413 231354783 631725074 288655501 747072183 884023255 161978684 176301230 561353532 84547597 989098065 599422031 804971485 931572659 372766938 637190194 2151963 33558490 859319980 574008893 684163039 109624906 531385948 808705152 149406670 578054008 660273757 496492471 796779807 164481150 899063092 763778205 800425470 612701673 976463977 724130333 8886805 54905193 141001417 486766482 368939136 89777125 131532899 519590150 824500576 84365913 514767172 53559118 874350795 411473501 822119251 433631927 522694084 942730654 191960222 943602116 312190867 759943049 881613061 224554559 153810387 536210472 684065341 178391344 146898635 420329701 914321779 920560321 159073377 153202833 460182590 800241293 676237290 361918146 277786024 440696879 85471098 554096664 816384156 645689474 171459687 208276597 400819259 88817816 676285698 379793744 812175021 803038217 105835968 795427582 439092504 831343396 306812613 674090881 325695560 837364956 555162921 107623116 18620875 108173908 601228998 229181141 339786088 696053864 626379950 799994939 108738846 64028256 221325315 269311468 774420658 107767031 138534217 712092677 676488954 932136651 610888739 92270999 930606261 876541591 462345224 196559738 213004046 968266294 825856659 344875042 832386898 863334122 538159690 773511485 227196711 909043644 668531961 491410939 514874351 386014372 342368383 104493184 947822685 527725184 882962802 416702078 78732030 583555815 176322797 80580900 189012104 286604185 761128288 311698715 72663987 816268688 808983751 827549505 931210925 149061595 132107874 638673994 437034249 101261254 771776970 203814116 347693304 715323968 211358523 201873557 735509006 73569775 162666544 751616391 989524785 389274777 657915672 633829110 584475033 455389983 683323865 403532582 92797401 830632256 567961415 845000939 83813848 337047155 635319103 169485050 751616240 200215981 627250107 863511365 541139485 617345761 851649130 514510873 187666223 541359116 143220513 770553630 825155961 559697829 337055627 498317950 269723261 405080471 180424665 294236174 767194349 231391144 825362841 405325141 737256161 166243189 368604262 980727575 128189337 655056585 374981555 511640331 144286584 969069852 574777743 365559436 217258380 527705725 228096237 172462554 202128256 657336842 524321093 337016846 492208728 919942904 226137794 731691993 885468614 424794082 668884010 216115749 103585501 55153449 833031154 438048295 563458225 166570111 501214039 294311946 167714324 205145952 419964310 956754388 535284334 87168514 477300605 338671745 531930370 278687883 819896357 480604260 156104287 552997053 531721151 581469089 885816569 851461941 107065069 980139743 502379731 195819159 725846977 726638092 202180132 928854131 820234742 480259404 668842512 923084625 895907881 680909072 848992629 370577789 897225382 848469468 461019056 931014 721568586 490965727 160993929 586148121 324580450 956909109 825717553 892381201 429460144 755058507 260151480 983629300 877094964 979021613 437951981 185008133 307507657 682635760 447999235 635106228 121822144 956444540 642792586 276357117 457593778 792919040 634107203 985166610 11081427 661782500 519833859 34936971 878490991 451343356 67037505 470249789 476907008 270063897 120111821 665593328 2131699 737647537 412029567 562678197 53282484 414121791 987475327 565500441 476585365 86494166 31527548 180314708 422126071 460798774 698533269 933371343 766438864 611536113 566142409 841305649 456652023 901205402 535613455 709796820 745634422 777025409 700879016 49839844 867527897 967718644 336495514 676637899 203663447 34363768 713227346 93084077 545467566 467596561 461027833 37465164 6505103 836063689 424703269 711196821 198231632 691564277 721932324 139158950 974356922 346832263 351906518 891301120 132320013 56170158 760856038 494252373 152576091 981411755 849725361 678667546 550707898 326915082 481251374 192519481 348065567 515778381 914177531 643437613 24157278 510387547 135804706 208521851 121071474 935382116 761612676 792644982 525534605 660827440 21191022 610400595 153874236 381740971 644374135 600907918 972271413 794750344 769234944 688170069 893551716 288136776 798582575 545701526 321428527 865476755 452546561 280821727 393592325 229344012 75552360 500964314 747179000 170088006 993545947 677780510 288384059 786217089 707185254 195095048 31422312 854345822 74930035 826444017 289259829 160203362 684318611 334791120 630958187 427672888 753427572 639193935 66449136 496065741 408471709 400754600 403257123 353190779 616611039 33654395 7380540 317998276 684285014 168697053 134656144 745783405 65556065 153528237 745654949 351286808 525317173 834569119 929773713 478659633 237960529 461157447 463547016 770738859 655068572 860174400 855918097 219897185 435382984 358518781 177475035 108447119 621755105 671709269 754603809 859310189 494395801 437273601 352539884 919056639 252194 528045048 580321172 329010591 301085368 841554548 729308997 518844676 866731470 491367697 825470515 380247663 508556284 214680572 884724360 738252840 929440174 809461037 549159042 175309643 841158735 562724663 961382904 523547960 105292264 795575378 777384411 266382717 582355236 413115006 401944250 334729232 520051757 989023743 775191381 798658532 401166364 953074768 4421788 953339736 596991871 782629605 219461353 935312192 448290247 716445784 403715648 828940883 180601737 600481174 509955286 70553838 710504660 274780289 850560661 294399686 371801534 918879220 523554853 268151893 150985613 415863667 298869968 885679509 127100639 644541071 957419576 567408060 943375269 913198664 814964595 733334154 989579148 740507695 48175900 786159002 298217838 584527912 617376804 334277900 96895948 380867613 856414298 689265100 114695601 951038480 611500524 142202020 817370343 416826213 823578523 714650121 723081319 618796507 128171794 906107321 246942894 394816285 774868530 757377397 906585735 133099999 626952929 718219023 328098971 14488820 460900351 650969254 75163189 157903910 392002377 965658004 515628500 262970047 618291083 534695414 54047272 818257491 990756605 37570198 458306022 499495067 900213195 57438100 973484524 515475153 912732467 46022293 609432419 900661963 161160863 912366774 920337499 23745692 413681675 86847519 482957865 315102040 314256526 857272897 814710364 590841135 767138474 94305598 936533572 652970112 963496773 675064542 254905690 150150114 585138587 150847503 947750478 935109866 788966679 795990008 787997282 90432306 455806432 940402646 945371943 387150725 121450906 78154112 939782179 269904853 182509496 457311290 10226891 337142272 421138022 868292111 313692970 359702200 583465690 11827062 386847317 977604725 957706514 109442730 929593437 696651468 707334376 827152319 194407777 629499559 96362858 899022690 641457040 898620309 408797418 151732805 363859448 120265557 975953085 706914029 797107604 66858995 377582274 505573490 91102763 111806204 213602126 518175553 317742325 519253648 76687145 521765779 500052568 264062889 229631681 575485292 823730526 343249509 689053101 344900861 438228029 449222271 348058387 400866439 827584506 981697512 136714689 703918622 604003467 667029708 46206975 992779797 178455016 924973882 594117736 973241386 457842788 816206812 697927015 704948434 239413950 940336091 329706088 367786206 626821469 540704789 665013526 353994370 536141858 137143700 227502866 533118127 282777572 793635437 799992920 533540780 121002683 921299208 642585556 463787871 931274893 743657801 510369826 124529597 909762334 330190509 67046925 782979501 453430510 403620508 721221712 311959941 892639099 977661864 460635231 730336874 419423328 441443289 367631272 742782911 292542281 515117848 603585235 22098485 898256537 96436298 563808937 146149039 529706573 9155584 963141847 451650960 300608990 211521483 655521360 680539255 341916170 276554469 82993244 575872635 73792315 717312160 710056710 745495373 334550283 15268376 803254033 86505002 511840326 254662615 553988377 999111921 793666975 252412390 290344643 481577889 838708507 988161144 495245641 663688734 486065414 122597107 695648753 320718238 831362088 297456958 614930862 934045808 167641516 658771148 16445224 975811349 407943412 659412064 704067805 539244704 735889953 895593134 582752522 439767393 905140847 910268725 480856220 565876141 781941660 618757095 861103185 482156924 741753889 627140028 869669292 303706638 107469500 432738649 556786800 652376471 950583212 183146791 349445342 718663256 47503740 899512286 705813741 736695360 148585917 402023930 344717587 550713618 387306964 106198371 172048791 692686533 374849157 97813390 774298309 967220868 547490909 107771696 267457802 138308142 363783411 280684754 354677866 642886395 96492846 359908006 407094429 368793555 304803443 756239537 887268491 554304213 471074392 884461610 987643790 959335563 916478717 455699544 449519045 921156993 231257885 230342019 842576205 552111298 337641969 680663479 910366750 29838424 856710232 323131229 753146165 150368818 524838320 671638876 290437764 993783360 213388903 549771270 702796483 513673888 42084987 255325068 667873343 721600615 723859469 62695915 636075140 700649286 947153864 923015099 284776948 794759569 520220282 653869754 684857765 937878705 857601911 571345428 665633219 942301969 443921011 726362702 153038878 272297383 299395547 152903558 294430691 903204579 871097426 300057708 659580641 89101389 52146975 358966923 399698132 447064692 507831989 190802930 206155713 31772035 971341170 817131957 448639776 260108045 989037811 467141622 94615169 285607217 339385966 806412015 361517472 757678355 299594882 312494955 822979194 274155114 266955954 7943709 652554091 897246923 962481563 201471113 972464669 746215860 234364356 126134888 426911011 891125238 896579426 403507284 58541017 672428050 117467775 167337263 919343356 800092478 524923030 942436130 904896310 58454801 844404470 908944744 292919496 902148506 653711482 181818373 891748846 525894788 716859061 997356383 744909466 395525004 863635479 605637130 757716188 187214804 458193778 685284431 111890304 937603814 602356517 582124755 708820139 446650027 580767037 236715574 231760501 387102255 287799858 984441500 3144272 687193916 206287646 726625069 370234863 503076025 504555428 613097908 341403357 421607742 545753530 235069673 463408265 913480798 957593518 4033988 126722434 737695510 768610937 760054875 336873899 521435321 847855484 174967234 963885973 57359461 134222335 385947521 206846001 498305769 793128493 167976827 328528681 106004050 472230663 103468961 968143798 875535987 555589681 240573375 694085392 257415603 310633958 244307767 795827995 61273307 632954560 277978091 164113845 658841222 549832001 198302783 398379686 338204789 54815575 543597746 868394529 780571409 594812063 587447482 894399666 642021690 404257039 898713456 360889597 282635288 249834530 171349473 462592246 715878709 233080308 649165123 467801224 31038013 378417331 484021280 408205741 115528580 661278423 995809360 525462183 993707734 528188850 181498118 470596918 935190999 829973875 711046142 842516531 862364576 359225218 831210445 454052254 451226584 546030709 681319617 744108336 622891839 730900784 194996431 889969067 306239695 18709487 978538506 904136050 272319411 288541240 40159458 351544303 424421334 861342687 39344464 608001447 944745168 930685817 141134463 148858585 828819811 680105003 940392359 550595418 714581034 857068231 607570423 222191205 971792285 472389888 817513755 120105888 335902458 645771734 754779424 812397823 489345255 613181618 935329635 9472887 54856191 197955513 461549919 570663782 993307650 507950696 559580687 267258598 473392164 409680655 130624927 326828806 759120261 880466505 598242884 345846599 157792333 597015887 424343698 364379858 409664062 915191637 382974342 861100364 509545870 854767413 910758307 832812411 65984348 522327170 37321988 819605562 365583277 710334830 217579821 967028730 997491624 542512440 840185404 848273554 1370371 531716794 43839569 534139462 969005227 189588086 267431801 832503873 30377948 534189752 422697136 403328692 803781842 938163042 431199998 629305107 332232129 99899813 726285436 806561873 680140225 584556821 762319862 774033197 245503047 561106634 263917592 700419974 412519214 677629636 359045258 618873727 451715530 419421958 229180023 818921665 854845378 498349505 433808578 133758902 841370134 62029424 527283162 284866494 527351201 790227148 169976788 618524225 631421794 370351034 169333768 844835221 383945810 592304775 193526149 26406345 16199507 37127180 847788230 700327647 89315802 949787073 293879356 459311659 295397471 398191892 167882175 570938158 846701642 812436963 19332413 494505675 513516777 653170236 368865511 735336914 578854221 745993446 915927309 920142056 24682067 640987090 983432980 319347201 620548181 822006928 639980316 774111157 852974254 578731269 239787931 985775792 540261876 501598529 676388282 263390787 883323864 222977569 175703567 424609038 1546335 271991154 459146641 245300507 827689885 95828069 821655174 490825781 240180037 546281221 176372242 501019508 586720293 447707424 275285994 771750627 157691672 399596738 290285783 33119556 224159021 184511252 112588442 178630739 945328319 780500888 769233989 307395284 760286952 424041136 176684188 888227137 213600055 79225709 2874412 578139265 76233391 19776181 801660510 929847898 79131218 58855460 39182202 590786064 942675307 696150536 71415724 896822731 613867446 964727124 174335344 993318701 119830468 301379570 151424218 480500173 910408481 865130536 927338447 803565890 874893453 619529804 720810327 304724708 672444587 469531909 798163855 774728274 301848780 630332645 461119521 621597733 946703884 698217724 947764712 572476481 90472496 820148066 389112261 848239422 712082309 149230910 794434355 789102119 978004960 257320131 751645229 724618056 833265279 949548717 588973054 550211727 536813826 186443036 596634220 254279633 179865256 645517445 196546680 752644991 131526418 270822616 285726651 775900814 166112217 110012975 392146675 1137975 306395141 650985832 327677574 866695523 363647484 253572039 458042591 311029349 958314498 37304207 413505826 674375158 934218582 81175510 995242859 910228741 237377375 665486380 324354506 347867797 361834107 229688701 184438278 78563265 753423848 994521517 132382728 623641435 816668302 209930381 752784778 733904918 30392184 44558760 472226891 384006083 340144802 160715257 133001682 381427319 652853854 513813347 41003324 991842746 526258216 466551692 179514253 75758287 470307514 849344838 659200619 728496398 912510839 849176974 824333730 201076817 624934094 812416686 379731253 803945050 792924639 535884801 756555928 710083254 626581056 422734629 116910344 537923689 208410515 374682172 641989541 948104146 382735936 46538363 718264733 91660384 752421393 238937538 754902906 463099017 381950769 312144076 70093029 573437028 562888571 918550523 72631453 47169575 552246050 783872097 254034089 873637127 74375092 157895690 231857970 126750097 631181963 619482356 451112557 372531873 66936576 997294577 469399597 494071221 393353750 367235685 757469464 964800149 970832905 823133464 711213871 224685451 680966271 420656676 974942949 494469515 822201714 64436824 107146007 641543713 713831584 931763153 916607757 831996784 76842607 306039243 322820773 284781657 907523897 304854442 723890816 676065854 97915282 206812036 364558116 913955861 302911059 587644285 950171708 489426907 817714648 624196524 754530195 97052932 743272631 320348631 851837142 380609495 553042442 430411025 682307376 742464823 393658813 654652905 283224771 659000626 813336498 481813193 228025004 706542736 905985806 387199158 889773858 311725991 265583193 242563458 180138728 647613551 733030258 96781746 37899942 221464437 949685660 222400941 681555769 484218018 937578329 246872290 796581978 116055631 985219088 10245221 669868950 529382523 224895237 39678082 755310564 217472648 73107970 354197727 427287982 572654044 293733232 691922652 435868054 973721165 331671245 498608992 318594578 854234971 948230744 665557560 12630164 471630380 603872657 511140364 370775968 651796345 39330405 351821723 140693019 503980610 281550521 342292270 427600243 458159655 691032453 54096712 386213209 347808543 385731735 17822304 693842012 979868578 796366284 60785016 880618793 578443871 858027884 729019094 721443087 748390078 345268749 206107334 27706645 609433252 498455253 40420806 159762194 240370134 919212346 560805846 348949467 208051600 778653744 798304703 863528490 946574431 202773932 59828614 161859377 43441667 195556396 860908851 584431956 691829450 841324176 625554918 270371011 261208930 543270123 440048265 385652244 920465585 383588484 8790746 638718587 397734087 37712826 46136166 535949092 333863385 812016854 971721359 989334210 540977133 962206316 27019709 563549576 624177352 431230511 32410625 391077913 92432129 391271069 587296623 706968580 397547888 441449568 446223730 422555698 685522355 698151066 572946196 476070002 960086770 54806728 478273957 25450578 906757349 530374670 868658132 181681590 915983707 388150431 10422882 823110671 60768297 490047825 502963319 895762110 854205461 938370331 220691175 760314261 729335085 583090346 68288804 619877802 584501227 459537872 792171 299444512 700135717 719265079 781886665 375937519 368508011 909507647 499816821 756118243 38142482 989547277 280732194 959827685 516475435 100839745 271731234 357434862 426092862 441814381 752255436 458748126 859149861 94650477 676140090 238182870 489045196 823514070 343430902 31508029 57053132 924116016 827108712 139285243 584281121 663921072 727323738 351346761 722376952 363058812 786505710 345261353 720131290 770712144 725041522 362646510 578213159 469671154 685054122 745771930 835643962 572049543 358394324 134254968 585484187 119062023 808763832 742956750 771062891 919245939 917560622 812070384 533182200 150805321 554070730 101826629 846550553 714228975 522342927 333205170 409833850 512883628 151286271 444485340 955629672 57085237 453267271 722879902 648379917 567158274 390363197 976948464 10660418 779630033 983584782 736506241 544286149 214370060 625735792 966969213 183331910 638001457 753292077 720524498 237586320 410903122 557080547 396067963 770252595 233594270 189959152 495362850 33143019 867042015 843600485 702563015 433344032 963154345 927926079 608031282 480258379 741300103 131366435 659975555 943578419 715161992 587006405 923863872 430693228 875885598 267186290 840505785 829691191 707212743 473249451 329920474 878702555 926485560 801284860 479835972 89852530 847603 793165057 745134323 172837299 619104514 742232787 21257226 231251734 615857384 381521454 344485730 571867696 802230097 282494550 445716377 447908594 465616967 305769590 754660161 552772789 363761460 235771476 680014793 743830873 292268224 197124209 409094022 758183566 158279716 434715134 111113836 946161269 718858013 637250441 318808017 866453312 6988650 513871322 855359697 223845270 918996039 894793559 69990403 851638881 787442663 425403595 761567251 884768010 977431335 192581689 924421087 244825951 4588062 197022420 928421566 862061060 55630014 924969960 759534081 910350636 130545412 805469674 942178402 805053841 190397583 620224259 999037269 757053292 635198497 443387172 934440137 303177347 503544700 730538377 401910091 314156827 700945476 936233674 792799190 211606394 47518765 920970496 93049580 721018271 368187109 399375030 97474602 686913479 851954948 491913516 133347582 7695535 385301221 92069270 581169569 768575256 323463762 91158319 706510349 529527533 304167507 208095839 215024350 607207820 850353453 555371821 607951883 699690804 586952649 827893519 262724310 690563030 411972509 584610232 790107056 814593165 68108921 212618238 167234595 459241090 134707879 111864135 983742093 961886696 433175344 422036045 345957951 132435627 661723023 178737814 6174316 358040435 964995202 721217823 140614387 345607293 603090591 628976407 765385394 31950223 478832032 743208287 407263580 406005498 738536383 459702932 708696705 657108596 963386416 244608046 415524437 679217516 556053897 129793599 286335509 560458815 682668142 528099083 532041032 965516393 916291181 754075040 667208884 38793045 519098208 949012210 121921102 648961632 68996655 432039122 882129893 40824085 42133836 794794964 14212038 722177705 590308222 331896040 827964886 568873320 765139226 134332230 234349500 424111924 245045297 448923179 428387246 141093363 635189843 149881552 684106408 89225748 42551699 967294764 50465865 465402694 233203110 987214017 306982922 701809536 871923537 21353307 876246072 551160688 594641542 982275891 965025944 526099511 513144147 301688669 835782610 305580326 31483107 145394375 712612080 785133995 990904953 104972800 282934362 442785626 607705738 944001681 185131267 296442799 641948723 279976559 165740965 520182839 673540783 806994214 982544326 705843632 541483505 441866543 39523796 270725480 747828475 687650294 788375258 680913056 481506298 74339525 300935781 617857308 354470714 449503027 585207028 110796721 770469629 381794682 827620038 889494355 2845722 301103307 895586289 697889219 265456914 274103817 979752518 541971788 111661713 10081514 798108065 565760387 156534694 344595676 411250550 412155204 320437034 763359589 28243083 499396662 733986549 814285676 820807261 631238779 285775187 715332919 279743446 166441321 935060739 11447165 292289889 460478977 282309294 240116244 962369012 694806941 604067686 934262880 412747176 201374521 2471757 129202554 691655966 972183659 963361159 651574703 155791675 43278843 527223948 859495754 409130157 537281555 184127181 73082360 399364988 474116977 495719347 714714327 95688900 464925330 980631588 585949370 999048589 622518112 983980107 765752903 527008454 43315497 27635616 977916146 564746678 579353753 715632754 274985224 16800659 777262388 284536401 356792865 422433429 514190983 74555524 133477675 507105233 492551457 662662166 577321092 488406340 394185703 776064317 173426532 346958147 324315717 70716833 791393313 341958374 695155878 997614493 726677431 180344153 589945308 713030378 724387342 360904995 204376795 35875715 655667373 207448249 870661838 304482320 509776349 448413833 378910558 661959922 111545423 162623565 77276928 280756138 656173973 398952766 453556805 971528363 419424026 715101417 390401265 408753649 421457704 514587194 28812223 333403982 290217618 101511362 599828226 62592417 327034581 514723242 259964942 841166371 630880392 715599328 66903126 850004777 132498120 296142703 200773632 106777382 506197787 226004708 557990295 501792659 98489213 763092033 492492984 418881963 730462648 830109510 17687588 639234838 413857574 136297017 96651662 209210114 601083239 958313794 374363472 482625934 867135139 596029368 329670402 774485186 784235097 224074677 355415091 16225367 397298732 113858922 97685493 197767764 468036475 197089340 287565799 129863968 584291877 149351361 633719750 310404835 646224682 733131660 681334439 235120139 954911663 998235448 440694160 500129011 159642503 83568420 260574238 519988156 308716414 462979111 171922048 35772281 732857531 557581626 748830951 190817286 679411351 168202328 946511687 291433551 726496123 1203343 317913832 317865479 766462612 707579478 384291908 399753469 289073558 535751321 571836375 254005529 465726023 892302805 778267855 314664575 954645861 949764951 585658859 764855102 681195222 86991886 935840298 841898959 795843266 971410916 31580541 668313623 869007950 983486395 923031651 816127204 308255415 854015040 415493285 126561417 941154921 380801505 250146412 522699841 297315902 321623553 956190545 283753444 119184098 612299778 822645985 281759124 519379632 270756015 613016682 725600941 653505439 685368404 37220285 641596836 348833763 756430562 885859296 870356528 167061005 820844993 655468810 780282627 736044265 584981747 255587337 31290380 457979911 497013716 699496898 640957026 328452068 258130160 928001343 370001162 620885387 402167550 743712711 476546167 698137293 261299141 438405620 218867741 10634723 486078091 618136570 621086280 611359161 3792763 185852729 413908934 898068581 280351717 141051893 404421082 379815500 332239593 451105430 960287773 933423897 552983636 143867603 614254880 386829923 415095611 226668960 473850640 62388302 51160287 97074445 104876213 667580530 667125806 388098350 352314372 525458783 690238022 89905245 951546436 218466998 896621403 155453025 481983961 414307312 299763700 645865722 243514751 499193962 499769309 960993313 347700050 598484152 707340713 74448957 705197479 909117117 346578595 201621208 314284513 986049312 933640369 250160490 850170782 99911422 703316524 915399507 47002133 224963585 873991820 63745342 372652575 962843712 146912739 106456534 215218754 823191378 974302392 827797381 415965339 585957753 49187927 560595947 408216642 231854935 240222753 90021083 540695975 753457359 888928595 707986960 819106972 526006357 349692178 520692607 392936536 197223390 567099084 992875539 238540930 397172652 442341016 6861808 621118255 624747194 470519474 959090852 84160638 721057879 158615957 133622604 987699211 807534671 566699842 892027096 966030101 711002128 479533645 459036021 625044346 19691959 900826215 64570445 718260331 812789688 831242725 244304360 921198383 890741210 721971162 662537622 148827166 268511868 727682809 917518307 484637534 34602531 74198861 425050362 924472123 243429822 387309762 579394316 379169572 210364108 333818431 278597935 504891663 445658112 467509249 457916087 587869586 408759502 482134070 885078375 872852127 319439691 150917924 750160286 284993378 412312982 884583525 85846877 824853984 699352134 695791 911373938 830577489 637992999 989270189 606031712 509674944 180789284 419401824 437851193 786900 518169780 360251489 380950583 249932624 460095259 85184424 485578391 545700146 666537409 73977489 778464315 481929912 274789739 543155000 86380671 451764706 578452387 193207891 881977156 78624145 310795765 112541874 548002227 317375360 504043575 561796144 422686215 16315073 533822811 911023746 427600832 573872565 857338924 625245134 227583822 584633304 637312702 15164946 9171616 567875956 185123574 583010965 438702019 576560533 184103455 740962837 960375416 480505741 323217525 705331362 112488865 615124948 664983109 436077423 9999520 377415974 781173665 999251105 946173159 576495812 957439216 219061011 20346626 89549888 472405039 425500219 461676170 230241872 187180801 235124187 737161341 355144537 408868420 421475341 348911284 703897082 736994922 906893654 358168934 690733695 357730036 334288999 764803009 354619488 163865892 773577513 400703829 674154221 896570783 470707433 7153084 460294615 576757154 38448508 379465659 482413369 937468197 908875176 656871077 943239625 646878184 474907939 356276944 808555584 430783270 551149305 507164413 869181427 755433114 191422945 309326566 204004165 69003329 58515405 903462365 632948610 488279432 847281333 263377603 252358084 418556799 548732496 172605896 767752471 165679207 162899873 745040671 856403745 152758919 684691912 920684917 318275733 236182329 309775310 73608382 225365087 570549514 343931791 167833660 903253858 933350277 562483946 427650947 673311272 215657600 671001971 48301059 810981431 29939239 601536774 219876851 217456726 809383326 978302282 716069718 236673586 452788546 410347425 774446473 722718015 437594078 992439265 93661159 220281176 748876475 450887951 550334600 893779910 458609029 603882307 870281878 169832897 302997210 656772724 157968443 907607953 162102383 946447779 664076702 606003299 408830812 570964408 207302417 899399663 974512255 624892343 972446641 19158477 580564952 448249270 679783089 932711193 132032962 886007685 98531723 573855084 555857120 362111249 310718181 923168980 728967214 821942608 720101243 619644139 905826426 558782602 75940468 311075085 105967887 133270656 818196923 979554167 475040046 994006641 973118516 249843065 144164333 290089686 226250816 95255081 807363037 811612411 775129141 52251562 570508096 484782362 317469852 761765825 319180126 980277561 968030739 176009348 656595158 966829444 164172167 983017050 241999375 954591973 662877385 159481613 289021524 196422925 395477604 106710553 772334832 99116179 637369788 903574516 809823612 364377356 380670248 209468101 677169134 500894084 314347820 164264767 340032140 67004444 270518451 138422803 873830701 55166127 382208336 31178486 959083268 467350358 579179366 168991969 732645821 6160108 68080785 411437192 723635157 966572757 20431719 517782470 755872468 243269549 485703533 102453186 197471593 222913454 437562238 200443591 200927705 208787570 337049096 879238248 578216652 400099055 357616428 868613656 615854911 198585930 155141260 504731538 417616359 313758554 174531027 786272153 680051778 216953333 803434819 203765632 762944519 181538672 962922111 454562628 585360966 382919585 788218932 556264867 597094520 601257221 482687855 424582170 763847353 943244550 807917876 226492460 561786539 757031775 636354369 150627434 104079375 910904421 221198295 802502868 984470111 922786080 360555262 248835932 364658390 542616693 407682728 997469537 466412392 20505058 549547895 545758856 40016820 620154727 928203062 466221475 657127225 58323179 429634315 600676910 660628831 296290314 445856403 883080612 111818341 434832204 708666143 447027786 476591530 673526436 217188583 220728875 859135906 798834354 201572798 974078205 575037494 170944189 984254883 720228966 218443269 462121784 777899506 1462493 677584527 779968862 580703769 501842196 718358276 405080573 835232712 890961014 714176691 193760509 839336202 378913962 833167271 454259154 694192439 943589994 435688318 71802389 461218400 341319712 339234508 980492574 834715336 323469607 190434891 876514686 386314213 77636428 566787523 382889071 168566924 433197484 65906364 631865131 865510033 685347740 622551305 148688791 137405063 406190217 983167111 41852140 469248627 45019776 341608981 253328044 419864725 451907892 974695975 160269557 190772608 489828318 858287641 453323705 72291405 224846643 754119674 151941950 445203504 812241463 721557972 910497844 697699228 446483161 578635955 222606226 903827022 77482121 937887195 661453139 480982167 347799151 96643549 118206146 208012490 100315120 406031492 482843120 575675999 421258755 458625601 455436177 708412872 34360562 290434419 685880440 353850621 151182091 588543532 262018109 750559653 523523583 343688393 853689111 134834908 681387870 987893733 326869247 264119599 833393813 722978273 91505947 319690764 253130637 458507740 440119226 783153809 685166667 900228538 70301540 444615245 997875147 564205418 45553831 287470631 417237910 234293582 779886276 339020891 147426447 105639349 194893349 219502709 244149988 104720475 96740202 986275083 292665879 586927270 641018729 160046204 68682164 467020676 946889083 73333509 453599652 364378724 350546447 245030995 587292601 312123755 886109032 943724301 311171979 360941639 592401490 300840881 621995692 549169324 525285232 758086786 38688663 153892906 794837833 65223643 724252431 254504560 301777490 723208494 966063080 720394861 70474206 3977955 622889861 885555157 291368370 651136098 385375360 518679521 745393895 30322035 292659170 729789808 698539537 170227674 797702740 356553126 563145185 411685055 805108116 509486927 283065272 270881307 504059430 484510008 833038500 707657400 677362264 191564774 904777237 84987585 471146085 120168082 778283334 647879674 237675034 410400544 433133285 652766349 979231015 897304298 447689697 973097618 161443943 687673345 699855984 388645609 31046835 445605335 621674120 725223343 890786692 893053332 394314660 623876068 529747136 417600842 353022447 812995099 472604067 557566189 740312392 692271889 615909926 221993766 357723398 837763413 260709928 532738385 984863038 842158076 348346319 186970930 650261201 533829009 217286179 579490882 464536987 34486882 147748776 489596915 385833968 373486722 190678807 747273622 223600820 474070321 109169634 570694444 143820892 95257673 839976443 361594539 382922667 463487647 593936567 312019537 155758557 115197701 884059207 557743920 820487529 336328992 650373438 835376523 853959298 263617876 533121981 192150891 679482512 886607022 900593815 653834859 314556260 896110072 377946558 300297585 340624037 921125777 982088024 243585054 625152244 70730858 738903848 794100491 424688181 296363997 357354778 93035773 938005353 609109747 999316474 211853946 193045229 268222750 674680755 572717814 403020498 938173822 572629321 936545522 389372780 542233683 823942835 603643160 1893203 316795277 211075695 667454743 245848444 405533507 47005990 322846042 721387995 385996762 74104659 650963285 66849182 740569049 810770732 976028983 348161719 683748975 492509433 78921876 921531741 984932588 46953456 780600154 539625475 571015789 390793092 505835284 67296020 40204315 961022822 24278317 363795655 898180135 579047209 572980873 160946186 864162259 783082248 62762573 77375138 736851726 25627013 314660965 900350658 541701388 105604759 981278415 577612560 835280583 37241837 880708114 721417178 341086315 215823215 926893429 458785852 288959940 324291556 219643719 948072749 223968424 809749303 785751324 349370917 174294479 572689166 369574230 164474954 232332473 7571822 802184761 769479098 440398059 354009047 689544873 207136473 992090893 683608566 743398477 496597754 30766495 614497262 819889729 275826684 268677064 12950708 873937644 208593519 215586541 81973134 125236374 461173666 853783979 234765041 617150401 416982817 690333808 890794910 22751995 490256638 678361965 428994040 385189444 362328800 866769567 177815245 731544246 245880145 742258269 769193461 48506063 817855110 457836054 545037632 264663250 131148262 452903387 424716398 161717557 393195752 393572259 585053104 725225065 353364528 793168396 413130496 554221589 221828495 158322817 759959453 190301987 923039683 834688566 297431150 181529910 170225844 545348235 243745 614466700 437871244 161504959 821015399 554291903 451025074 842301498 400144473 521425429 628675796 983741037 305227584 839664526 275685237 627880176 990092191 396684303 200071477 298474716 670114364 699934356 558781713 831062747 741967914 756237221 843074165 436365274 958680368 446219138 208967167 259490432 397805066 857388745 781036970 390970631 750542173 226243516 136566897 571031292 416162249 650372491 754554381 532790161 930626877 958895973 48263385 451270060 206812866 438209941 668563455 935542149 943610970 585417899 383809261 884729831 273872460 497920983 432444344 42285249 845212204 502471772 665424728 414406778 327105611 649201926 266318157 350069297 258786700 987058350 987581544 498617379 98549362 461007082 925346396 92017585 636923272 168784570 177318233 858471633 300985294 173302673 87891446 224193297 160501812 554738152 614799746 240933855 690811432 888031701 599009892 334190562 27940547 480500581 74105040 627791796 651143575 254891118 451036245 397614740 268503360 882084707 852023162 822235848 241224114 409599776 268947474 425656501 345913460 222034747 49791811 797145931 858882818 907807897 873796809 421436340 50088223 608042976 629810699 258484963 69372081 446759713 129318251 72311808 934835860 956975125 624121033 149133614 376522115 539874783 942750547 650772984 490219052 564606266 307799991 905324617 474147566 561258676 543703265 524935800 92127208 338840150 353777456 515557578 496345935 471691061 331502323 383371623 988231299 346134379 317592487 651346683 724465432 866766725 656095252 225824229 806634807 219594085 864032828 181729538 582925329 123070672 981123888 428522254 335447364 841141998 753081513 676642389 191256711 213833922 333120348 460233142 408857568 510832531 56016806 344285891 773308949 565456928 564338410 407482741 775486217 318640049 824213295 359821706 453080388 17214762 516226602 728522261 323895689 770349447 563957675 60234228 761022321 435094760 206428810 396854603 583828721 907316365 318308617 773175810 587808098 829906803 978841455 429984089 47040958 347849004 217967185 683448666 575022549 7053557 334988567 13464623 864095798 406792043 989009744 192994454 250132897 282717532 552450886 543887941 787833238 547988939 368127497 97947102 945459742 868612168 193634438 992220544 991042472 131036802 894275916 598686185 400820325 637300661 105394555 557449012 515056029 664279835 54059934 363392814 527096006 250666025 953171664 84533104 174715464 63512183 35473666 460554360 592700211 644617508 335969186 771257867 214728805 32712271 531899435 551553883 145316621 159344751 202174481 636244082 632895172 738448123 91795507 107559663 268621398 206074725 379087855 751204219 316570745 758233670 332484579 212714599 544399710 483427727 797739553 108703755 892636793 210277802 924810405 360099486 139150918 6463402 857083191 63376843 813912072 447812614 820849200 4609673 83149956 530693283 508652479 334196047 138307493 818489389 483278282 413616544 942858735 991782061 227877433 312143122 628665768 969839838 633090965 315172489 683152337 236728761 984386394 259382408 363660393 24776516 840374913 620806054 201696109 461053947 165438725 188210324 837736920 140023864 547178923 95703029 462305526 946751205 268247404 207118682 593289194 211272347 768342425 146988014 137518104 48663117 219492865 560054771 523827751 73884735 680459512 808432578 236161188 190540059 957428009 245732581 612213155 750218137 32773454 397498107 473598826 488336461 659737478 792556594 148858470 397823011 50171793 809813774 27375281 877279468 431554278 448721345 154058415 639872534 692973842 135056917 371114117 198633810 181850848 673473565 730961274 550191353 346847537 623003988 676442708 993876156 166057580 606574643 789885351 786064254 305669643 995321583 975126409 67153945 455476968 42058735 973915863 698830206 297324887 838053394 381458843 824437583 726627077 950928128 18313084 914784491 593688039 76775015 621669750 409682412 870763490 442929548 472710700 314130660 231996161 610627464 872404954 546341478 811009453 497985586 341060721 848760275 834785481 290732405 278092109 825427271 759118998 582112960 605372786 339572698 88507851 76174944 660040563 19073725 995184387 201476393 767248998 654620267 574363790 522134586 500445110 861301525 182696395 79180740 227335095 847443675 969609618 357582843 800901105 640231689 483824731 169069364 329456709 41047255 804982479 883133860 832520338 942103778 350191707 600368744 544790974 938454681 62668044 744698826 633845727 690700995 684456968 48633406 409841710 294316538 565650878 27626517 181408060 691655218 676170936 867036622 496962818 547265472 403683551 593837951 326105521 681325232 442859345 979778099 75960995 519986198 32361692 558587316 667529567 486480144 422331393 713331603 882305057 30596663 62558404 422585200 244478444 766555158 895053919 421607789 125467693 229654948 791041599 414791653 190382162 250067077 200412142 783714856 380090497 141586060 200727365 553523516 422342399 53175936 578056788 92966628 55806378 529402141 905925511 981497686 256879644 219050424 195905938 749474598 514267095 855828498 537384669 672054677 837251648 670033254 47931825 997878463 202134730 963289327 918263247 136734303 420592773 628606155 448560064 555605352 901288426 934671593 216872459 303901188 76560891 88096372 781129760 517519269 692888672 599165127 167639588 445426318 352377530 187702268 26551891 416460158 175978780 8957757 942762239 579645934 367926219 927489656 62740009 222141999 532810488 685958654 950293936 92077870 247333845 753785913 37611666 256090277 435578614 98335883 694146061 345934032 145236293 133110260 714474416 845908212 505292629 255346276 100019445 543162970 815606508 125689681 244769651 526826278 904205698 286102721 923650401 91585381 290754098 372567278 86632614 612182141 587623817 932300279 31259176 34152238 727441966 627752792 149483286 814414748 222562156 973534853 754666709 672640324 995125710 226242991 300217941 655547845 66789507 928031008 639492115 907980924 21071394 222978337 459357554 585898568 792596412 823112161 517999308 162491818 732507214 325504907 193547340 872823286 328908035 306384570 896620095 691495575 487613391 700325617 612896261 109165045 251687013 131861267 730967761 644584283 546740880 585613557 794133540 184305895 315083389 258118772 663585083 493641342 879338548 44456525 978663662 728827648 876223883 914787501 670405860 710916924 537617053 307243203 581275102 250471532 341995653 355827072 35631810 982215783 20685626 360032398 950248042 28629937 256154007 961285874 898394700 442786354 243792439 501652719 209018166 368553429 622132670 564168349 952086616 285274608 585459242 544931091 417538486 5373316 488694405 935255061 608915379 421499946 680175670 98247850 725664638 141611489 938037273 860697235 952430986 357088464 79135370 43988694 574642689 7456016 752208175 474636978 257188561 139849294 760101531 805727602 45156648 610215108 810771809 33230191 282882837 160391284 127439508 910547429 132351358 589391501 374596825 463813413 414432649 356972223 970197246 563028912 845401568 322846599 284830862 955857430 191099737 961128590 602284019 431753329 379354506 72524353 583081009 263076428 988540113 448818160 528935195 926843494 544239496 373281355 976687099 229986717 77270180 511744219 988827109 254928926 635633012 645300779 411564784 394030274 209994463 401979194 197781997 50338067 218387644 892251291 53049356 576016054 519767424 774107766 489596547 31550782 822038553 987978468 71481157 472661803 581082247 779538604 178491956 685548817 957387950 982881929 193512183 291622084 592053709 58872152 307421380 220754218 541249197 230243734 865463245 229404942 395958052 963041048 348648652 43099188 770703285 897492927 608188933 400129115 867371327 721372480 535540044 700919896 833125193 900382886 736777013 487478808 140981053 242640321 102797014 654456831 14824034 159605437 5102696 443498509 802832051 291938235 253287063 519634897 759837286 746419016 910157721 480388054 838711840 702161263 327933798 780247009 403017318 885002298 868940004 167143276 580374991 655036012 806606335 184839056 142479441 658986332 597205689 792258727 909026204 526983114 353128391 566831568 282618058 623835368 353338926 212638058 532419804 66865533 62365024 666587564 554643498 787518290 863403170 917504711 264375541 641244458 744626438 180675104 644976746 705104337 149864529 963332670 818596736 813536674 406677767 672186732 853232920 812603627 996613381 135783445 567565361 53772655 607317783 645306555 562488088 244073966 553460657 861261153 486681229 915304090 655818093 304782442 703561888 338661541 265543290 389084326 846830961 444084737 690169450 321329746 936565286 210470246 796643647 794827129 798828218 541758600 962920083 529690150 948625679 363531424 436026510 282794497 147583898 543116867 751556786 153013410 66037959 129478799 613744794 186080920 293997870 382475799 570331586 45687325 126828935 763464745 992366782 693760510 100049836 805491665 610805696 100589323 831889291 146476147 119170004 579522628 898659090 973149927 235437228 291894075 345857247 648788038 313750196 714342859 111536493 472838362 792781854 799550752 509409767 556203878 757191009 371403100 784619173 709304955 40820145 319307789 613602505 726944993 57978239 790824582 679386219 580569220 220067538 806789094 460400400 521216617 434625655 414199830 553348345 660833537 340909827 941254047 603011474 349039099 254673421 487668375 127894885 403633171 750006980 74878420 658305435 227436831 722021660 928247614 321033424 498899023 808924084 441801433 929822465 622580249 341072155 649689908 11778078 465260756 725073860 88228803 722106184 464572049 980004495 131876728 953478516 596688745 792673521 765990848 248679505 678494712 400879985 103527505 647050060 671943729 223432046 672773217 703576856 856804033 457938619 66143396 697925695 57484994 150154561 444811941 717305576 470499645 965402414 442603653 795836207 77105602 475877999 87637103 644389658 192479459 999041160 584943414 432982460 473287919 735959510 271043615 445212397 901311459 299597049 112372673 602527594 207540267 845297179 142053359 351267967 893448790 278351844 333772573 641090000 856230849 592223427 344079463 103710101 579334067 331704002 571489370 481344099 731765140 541351243 760719066 349515350 688737543 656362195 241863137 699326671 611903380 191472974 865157734 220494930 645274917 189397039 471674278 611278240 906118324 473356417 77701800 397926880 885290803 333863045 11783039 755625588 782552609 687509824 605566978 343762933 471032005 823830449 209504788 941404563 884077751 44789592 898012270 73517390 463730273 208769214 412857817 709825507 12729846 462050011 878956393 115550843 69975927 849062661 518778105 468260141 565250592 972882919 191816256 46774133 216471601 916668470 912479738 552643367 684641598 874464016 500868417 576291251 961587581 935595872 889014004 992200653 657116484 708945626 407946100 901181644 606992110 130090274 481002844 732788909 636394223 766581343 405494208 168438688 439976163 990128993 515830297 153312233 176207829 770379469 348549143 192751284 694972648 471136293 20093399 959154249 606893411 2587642 25613938 660102511 838389711 126803935 139320202 889350046 902570978 7196568 7590074 394342667 833712384 616943447 398950820 670143843 274964184 867137618 233868157 910457640 278402804 300612257 909881952 756455956 739281416 313144790 214551121 412994727 735789125 387941176 497706878 247378489 23303344 826622635 881116271 494342519 731878150 574145915 336130836 797945891 73890075 407932404 741179280 306158429 547616744 352116335 107009972 739523458 92605433 620218078 7534240 939237943 333928844 421529054 791014902 21832152 672024956 139589767 21734276 319518235 689676331 5320511 63513124 738387028 73469743 111315468 201719279 132195078 417376006 768305574 613965445 945870792 982162407 504258828 331900219 680193624 167250668 526930345 182427030 305933983 527812728 317952145 45543187 839166617 245693162 623310603 275948195 980395248 926049752 209241706 342525026 740758610 878589863 816658481 783116236 7355577 29362888 595044105 94545426 423737088 748271009 799152471 49771808 523738771 122036851 129945877 3930900 639281890 183929385 187382483 235950914 395443483 404724176 248736591 526560808 437948378 16632162 132107959 674983126 451347935 713765261 590504247 875146152 951737109 624429142 635725552 260868481 449839465 78253036 121322286 234189765 158481622 27093503 796110633 200325378 675010702 636256116 265456803 75294241 865695927 715940234 80368159 454947355 459276851 568291359 153400822 482187252 473563656 608682480 144343296 978032942 622911140 162454785 857236528 433845659 89234404 926247000 910586129 646220234 738168095 278801134 854777954 46973901 596840640 123004628 22376191 740871439 564848725 463439520 887203289 538273034 625821032 306568984 831996786 329360397 5737673 780474610 853215892 562504175 296348813 280916314 421155874 481100241 316897214 242641919 12234979 575133852 580196044 905850279 487776077 59876771 154535706 784791122 847643787 110478562 14145824 987630765 506837625 627621301 658910665 950060017 295018200 956999669 653565941 726067598 420903200 442767228 297416424 271391061 944688842 381912545 921865963 578963186 291081359 948546337 936452286 291514725 909760827 844251821 29350383 545519949 360392463 455402540 403714202 458464260 752406900 588535374 853012227 810004579 296805653 5293030 505831820 18946426 188130743 695019 168843613 916537333 159260062 818698278 475801064 716070099 844459796 354760602 585374452 513985 667999225 304002993 478174948 305453554 86222067 77221890 381225696 629719770 988507290 471132543 270278143 201612207 537570786 766978839 751422742 916792691 235775671 629837314 904570286 378579693 252409167 945126580 680498593 312941782 363665836 476598160 519766666 470508313 967428520 867334720 8243491 753331979 361655767 562130142 80898642 673388455 68933110 974806851 404772003 884412574 126763867 672222858 255499270 20133282 205341158 262474847 16390705 290670581 295492068 953690509 248779274 187152652 982778871 902730096 138140907 949429818 921166832 588042655 3158840 793325365 559244158 322697862 718931433 719023616 910655390 512858280 739012285 476575843 628460397 691530939 730012543 568479816 827568537 299255456 695147797 403951733 499048444 351531032 144809829 637045106 127335110 752246354 52848518 58906536 938109268 166827811 456627138 770133440 748800070 308708735 384464248 169388931 631748603 262106774 325606408 794971434 672468546 574734450 30491625 522637230 549605244 537327211 989170847 577932738 20798966 595916730 126400020 279486204 984119252 584776450 705622597 251626694 187973141 272731922 511527207 968327317 364890949 265919334 988081752 23679387 587986357 511950408 154525086 871459579 264934293 563775120 711399508 880610217 720546179 426120885 145177501 935563720 936001650 667229375 810207114 495443834 956129647 529231958 933302313 449188654 217848322 55660711 135422816 622624834 13812761 316819198 69849740 473706353 534332155 156197236 511609329 447835778 311136019 208168497 389330672 333788134 535440795 167052182 270888439 148530167 80009895 915901153 574156261 310676411 278779505 637066369 204407850 468705589 431779764 257018086 505031914 286201916 564747887 18708683 908738880 463279413 188609999 936673460 720983209 991331569 715311898 133942822 781790940 934232971 49435622 605740844 16557969 998871733 807059323 539477535 915827492 424403752 126770651 232491221 670042294 320210898 784437832 7912842 875587766 471157384 533809505 887788102 603165533 360167674 371134585 986222326 7308280 873785939 323236340 838159504 549746991 311125786 855150625 514717087 583803583 138573631 886081579 366506123 766972085 766570185 955953172 772413921 459261171 805701073 990974873 889198712 563059593 982127053 386620886 645325094 491497717 272003296 367132201 266331653 359571625 754193187 396473699 654099857 598702245 682265716 868556005 39437269 641778983 202033035 895940230 608274737 702296129 952913665 621767006 957391947 511139353 283170562 494952282 282677550 355807125 955768089 180502453 960869387 612513664 889522979 975888475 886131656 411238392 834196877 661044354 168989827 79997396 934335601 935990721 228575612 383957942 164181565 275640933 259159560 34548016 404038073 43803549 394870293 992246010 793769113 622732677 557275846 151523458 292081013 797546397 684021379 681258043 356222469 479315378 701710796 748036434 715697954 407111673 585164004 454478185 376319958 837289735 421060977 171825210 578801995 258816039 17630653 640786313 717627133 968587960 647577280 807027885 341329894 268722170 692957357 926465445 556161741 598645266 718586724 620235519 495068270 437058983 697715082 262824500 901138457 146143376 979219 912030363 987656938 41018717 532310266 618975807 125771239 823899397 474060986 505359869 714632580 343855743 634781583 258645673 480894644 591123386 640226886 66335696 585034009 491851572 219844327 718195609 927509149 725223646 612476065 548749730 303970215 761263270 22024912 634070686 472762429 18518348 812746259 570212439 784301810 622164400 867800151 515240953 891769979 711746100 310697814 107912198 537644158 607557799 651304898 33325078 717783892 731941871 332724799 260791307 917814544 921590999 121808761 415018915 128425518 737277197 775950399 774764245 598312412 281201077 506806083 487724523 269238530 607315181 583006061 936922282 825625482 358423843 869956457 397361704 155244420 698843738 105610764 869737363 717664317 813569123 437499969 88495099 531282803 882654539 966923384 268592966 62501342 699177384 708233194 953372603 777254219 993110773 943914325 624113966 892504936 938427271 605237304 286369133 542324076 304969876 903608990 63258224 24924143 314390413 218457250 53405882 481226390 918561408 128831102 480291511 697054034 10561955 193403565 995833793 979027949 666550632 881513451 780253576 588982374 535451541 202504715 409232975 183417132 529914124 120346184 547040084 96826526 189397185 319770211 328598144 59447758 42097135 417053587 894490562 601730800 456928435 623758738 664251980 423927249 175006232 631387585 242185524 631618182 129467242 193343535 594739013 809206422 337246405 853234427 934059879 849952619 315930477 637254066 347612753 612994659 42802188 782137095 801086982 841169748 61965150 636883305 623410680 649339915 940126890 100644539 312928258 235847686 44242308 883504621 927210382 985691660 551821715 880591611 645052453 751664401 554006026 786119177 908792882 542323169 584897852 664029122 442145434 791553310 197189995 419548068 332717097 561867764 159220591 806013035 547154836 706450312 412262132 813666386 473533180 481406249 406550048 838561056 664635538 710940517 164385529 316039646 336146511 433931468 908255456 491529509 240385312 841123369 875496234 790111081 262714197 60408892 247731790 514924146 712039123 499095074 997167521 972654867 802785743 978171590 392505017 555743640 248885053 374225776 535315898 422704332 985522947 675122504 395244701 296372195 858369511 273832255 27206168 107833234 374536980 561315050 24567684 823719890 403102990 568285667 169712068 21641524 694139179 368958307 518934355 580714508 282237522 394623669 636211721 635350226 283138258 978856500 243531268 774309497 138510191 661109624 499824042 275536695 711327923 302255421 337288121 897010795 67803288 789205058 485222774 384548844 960324976 212221816 209615870 251083173 98109042 14496847 484670684 285704140 688215668 143532269 614312837 485736465 795617867 587687825 155963614 762027570 127018505 62391842 517875493 810830814 821137106 886317590 153817461 640056478 374335075 797250175 372535516 412702587 179232547 415520733 872936533 510422042 94177124 147297383 698376546 981556050 170338212 899229876 507050777 877260746 536053401 285848069 657256156 135966691 373931854 674854679 942637282 871965682 936635402 124905333 715614384 312753642 901053008 554129058 600739773 403104482 84643693 505447470 901833748 950328727 179571772 20578451 432914263 235528014 61757498 440598687 990300586 626893361 652306177 597241134 525824277 155847019 915246728 443352856 937290047 964525566 424931827 722889936 499449126 78198092 378485833 874077984 771115866 286330914 884145889 374119742 726187565 432829539 722316727 626676650 24050536 422140202 694314715 207514963 584035385 509759729 126917703 675518581 330370396 303951141 927314148 707479148 252603987 37946625 999424453 80288046 892327104 45978661 473902379 908406502 408747967 695839235 59817052 641030793 539258766 790868718 580815646 342030767 764772163 779738935 259207366 203225990 240432156 412905731 284271470 967570923 757665483 57279336 386971711 886398120 336344761 558955802 631341563 23578412 234797238 349193771 549146408 560734936 732898448 802780873 700192952 210109719 95972781 504269290 302193310 171168573 936109491 726986588 787118722 881664821 523410231 703492472 211126104 770714400 470371636 21412437 87174062 828584041 537701225 627442281 374355130 748780510 173375802 856161072 546244275 600919014 383322450 916800269 50137962 510468344 115765659 745737830 262396296 771021769 937159184 956307265 263541338 629829899 111476535 180914386 478127398 975548778 826313455 282737742 706500428 456458903 509899988 536922387 200164021 111343208 967546701 345805884 35197672 259366528 903337682 374922614 456349973 346211400 504673718 485859943 132292151 880464600 279431670 707620824 930060286 904479541 425700297 142889014 691145313 858122900 269033501 987192552 79848760 491476438 801167630 71564006 862677769 729876945 441212303 888628810 871949704 583130810 626844484 258731362 18952499 476105839 846406396 599961184 994393940 900400383 446952028 905476458 165478260 417687030 791320136 310220032 88539943 985664396 641080488 919199308 493392423 249489641 234241035 288188645 611198982 182579378 724715142 594823342 886604718 515377346 718846131 266846930 395003675 313275345 866938736 678833491 777321729 590502252 32366974 373031215 225769660 903698962 521908196 246709933 509449036 171725895 817031502 891190770 63175356 592728654 698451863 652578309 640519867 131794416 395119615 927397100 467413950 69284011 103369568 912769660 209165333 923522533 547432219 681980466 777873589 913609789 743663636 994290251 493662124 320007563 183104518 743228673 973700380 705630181 649066863 702203804 890273727 39469430 502418177 274530867 796230500 299568794 998410912 649486631 640341329 551026432 448942181 567710698 339302153 991147656 866926591 437216514 398106326 612431681 318364070 780955139 102985105 319321071 281121210 154131950 28098966 900887979 353518560 475310467 645498254 626212942 743316267 578371092 350372790 351845681 7090589 113740993 713433423 492021056 662265262 357793064 957352770 550029001 998348738 792044367 980777566 485727796 114919968 756380776 13958234 749898399 840083579 483689287 1782879 111795390 450125639 574428517 311861549 694416829 86946263 184399879 225267039 772767629 715031543 710428639 60786990 68261323 763758974 640004410 293607651 325458882 646671898 368136150 290803432 629577034 569134459 75354819 285182008 131651092 117547014 353018390 251209460 918978705 174551417 46854778 940741118 732043153 408134053 549203990 808287196 362183505 2164640 492803689 320643773 111091539 686263568 901203993 386342176 766584637 957304028 753725032 67040487 793254084 263669539 900827710 558251076 89542723 965127391 630929969 773176030 560737768 296798671 337316747 117902115 193200437 327320639 538897439 815132286 214130918 288453448 364811941 808857631 277401802 682426733 7194542 931758096 324044659 276280969 540949154 718755526 168806532 356014002 534660164 276648295 244416891 952436575 643403612 456692457 886575705 660916890 349190913 761956519 600768309 545846818 318466149 166298426 1130077 987179697 138951605 456689859 365522266 667706615 993193873 743398539 199344920 879858703 171075832 636528574 214619746 385374739 793853776 919109253 77435865 918343415 781846071 648967588 533825308 793864542 793159002 901638981 775979602 434088771 487666364 523045694 61921744 251332784 177847278 592766660 484645524 407358144 600870834 192956142 415028291 750298279 138238236 590019380 483160913 789450832 238251608 514906507 773172109 116622332 429215211 814420051 103971021 937376065 505172371 8976231 693675442 200758834 900720723 825227257 611448551 866089234 452980079 845500049 993184622 217186282 500824120 263354000 85067116 442137153 575744257 102540907 875157332 983624597 2821942 552441144 119090129 277027308 911822250 562242951 126585280 597989779 872655802 343369514 419122191 433379158 554682861 372432588 678422934 189002040 314905096 535708983 435592687 881248303 584740223 164688183 246831114 481807226 258318747 66178878 604833103 686970443 395676062 870687095 977627577 979606201 477828325 211411240 109401352 13184758 815295035 6035238 209318230 887567379 634364653 435777584 828601328 479808064 634134834 131257372 309492890 703438934 279547491 245566829 362168314 974121003 94747083 614698989 162146238 817215383 608896519 756435457 259351017 642259621 277800212 812843597 265327378 667186863 557137740 723736170 177279010 775163901 645675761 663269559 210613681 563531808 380699498 282076069 151038522 279939203 566029130 630560557 978996811 152025272 510385779 815909271 630029050 709986857 861799054 941841899 828987806 338435738 874149654 1065277 604769796 586655661 145004314 740153843 649983812 489217405 646051115 198872002 229622189 995274802 320521746 987247072 64826957 584940599 220900670 303476834 926596989 639969481 24527815 349250694 523381216 299546867 317225949 518502534 434117949 979542303 774386955 279435944 721538008 629597626 804326428 45172564 176167378 558291077 366246861 780870147 245230951 898418133 887096347 781699707 818199413 276831005 247810748 620317433 703556393 883420116 507232270 582356966 439418265 965502467 839052263 982311935 439351661 915643337 36511056 269764417 881512266 114461062 901832684 729075563 312873271 679774909 856297511 864654559 853891888 351420254 642481610 979932090 836810961 945894858 552169235 281012616 637563524 901960779 39648782 233319627 360198191 746095073 377970762 626309440 624800635 233466740 773684628 710993303 471070176 340050190 552161069 720641441 869005001 137180605 518156778 321272538 277233194 206662995 56969683 691725296 584591766 441904488 852024486 870363624 323279195 324191817 639421713 278559463 807223161 895561374 427658906 775056086 470749971 308590652 119066763 601041851 520740677 775230510 338727237 263491074 928607993 943625023 238052028 190022888 953960134 608365227 597550889 347959762 360841741 956520033 269520015 589066516 118804468 29779054 511809336 65136639 473038672 867014588 460148928 521914376 738983944 504591863 288575301 318287269 87272637 27514717 342402348 837880483 625931291 404159842 174354893 999420839 906026132 48837901 782969432 751084005 972611280 997824958 919905528 598245578 779132248 979517251 437896731 979393671 751682277 908733543 31598200 922173642 730861712 888368696 728211702 315349137 810211553 374055894 145258355 54085675 767154279 538066260 961697803 548964706 229133100 259327585 569589531 657993584 232783799 952701321 655146691 786671467 552014780 312776598 929518616 824633497 474621560 884710481 282135155 489881370 238405246 713877697 488597764 302047134 227210826 198092563 416966754 601148250 634371527 505046543 776487277 220914592 889633585 906004098 639251004 942368038 358362137 593083758 749667940 142002678 517134081 323462727 770854525 228047173 737923166 659538662 248764174 393962967 703029059 677642790 997079544 858863065 303383409 159788289 431001233 41594996 66938507 735025835 78561999 454854499 137632548 371823436 755380476 450410808 622064913 203454976 188701899 347632063 923517646 564075302 67991288 964591606 438400960 628956501 788247878 200225627 53155847 979195740 424002622 519192280 529099288 611492637 85078756 368875004 450616210 43819656 154500384 98907618 269225874 797406146 647296347 198309286 602045341 444699741 23031153 28076546 792015239 877053257 92878035 879477077 232911569 339131372 188628788 554326845 847463429 59021188 15504664 286913999 228501371 433582272 518321944 493669143 800826661 974888329 819309339 52329299 719106305 919113369 462539804 138039371 19817825 229621838 870821899 331762453 613641704 95622280 487089060 747553784 960342399 463359084 338410042 161223398 267269077 40941260 779921338 842626853 451104897 194514822 874854339 677905420 585600277 936892958 789289027 718459030 279271645 263581376 823491237 723975842 201061807 151917510 287843100 12014668 20086432 423403432 936595975 283836444 5715870 889320880 795151193 116102956 46980999 168921140 161772447 860250542 756945986 305059252 264077758 723711022 569054780 981013352 429367714 612794801 688979836 991907609 528012435 537228307 316879727 929814910 475123137 408023114 68676881 25650304 586561049 960283742 350735567 15236347 949726381 402195709 474209648 829933369 45672826 152914779 159740141 684586138 372547508 928989575 896321228 670923419 308597081 13677037 861155126 706189489 508896035 794495099 36011248 826546209 458587848 28787876 688690335 41323763 390159069 376305187 442936818 258057296 488173057 110990599 789772668 452104371 55365266 618041320 493476420 21887119 901715732 105088049 240987865 959671308 274533519 830864021 2022612 225084335 491849108 351182588 714133361 355589271 280461644 446506906 184699280 632925027 301900532 718093645 614612601 258253892 191782016 507957254 767982049 915820881 544325070 593665035 598906611 689564387 642411485 721661068 964110984 609390004 437476936 730742892 14765181 185905061 197679897 818233463 538126026 206334932 92137999 376354232 92535808 263514367 21445655 972038792 389374511 264634739 164158919 448405002 407494909 560367262 152300209 272164100 42037300 664358608 161740187 367474988 395370876 25012295 393070663 338324119 460999215 655553761 378537294 140850262 716630312 382042330 802482043 443733391 291089994 646640501 354691520 557198902 885132967 369626995 442644127 380910665 111090080 744889106 868298044 316445438 448338148 610040038 820589387 689295672 943215249 249692192 400188677 254542693 721413094 501194862 250029540 976556914 242094504 445855532 274007495 95074893 198243631 95611269 397264672 913169417 210615607 383043040 881339431 936215295 728658153 643284136 684337817 898380056 592438742 279826490 345852544 420763493 250158327 899034213 922280445 96328048 818432097 688273805 280929355 677524576 816344989 719114116 23044106 810118558 795720693 548449628 47362525 495286654 842543863 422582746 226518421 735311534 461904651 551123226 637869955 855178025 992825545 529712396 632558053 636802673 472765405 632815383 391663088 930403907 345730668 695089219 593481274 840884254 468974204 36754453 832869259 668348481 906954548 664367588 179188470 300180384 915565393 144988730 11795368 366317369 633340986 287836322 408927343 88314723 266148073 311499431 227746064 577439946 151166798 39591961 684143256 161913954 678281542 334975187 263141112 977814338 546800743 24625076 339950413 820483645 445501025 49344967 486635937 23281866 323065366 475943355 871283466 885635610 225347928 240190892 229885031 414632808 844770634 385228065 580937571 61563382 624615771 544507031 296125911 269734801 558778873 945618293 678098674 415287259 7148868 307912372 824391752 569304712 608713550 855146592 365161193 524636747 949909775 52977285 609140404 985916097 795870499 655429621 913219818 131897131 174439938 493496432 919524384 795731093 673964869 621023444 817532167 615203255 223842905 623343405 215392537 858883245 833337801 182361490 679549675 779641254 178275720 877677248 381375679 78524729 86528189 272012568 264570094 319615927 470071780 592868720 168892898 534425560 592839755 573852850 153682432 118645273 236282088 119550602 499062387 718624922 221786880 277334506 948647967 38743548 790779530 807696567 683594007 464797179 701567313 215099762 807894532 675878322 484831048 328996810 775764174 732112862 913372611 539695825 799653023 741354716 400707959 35185175 319484691 425419806 772589356 521499698 238183260 86833404 901768798 14515117 10602063 465407915 437009521 903929576 184881631 437643109 973001173 318124959 258456754 188453001 793782351 100876285 335079059 924516765 314671492 204919144 46268849 805013072 929319414 520683629 890771900 33562533 889233350 603046777 180799098 296566929 99996161 561989097 796962017 395543830 482478643 785639973 371967622 999704965 131780216 323583340 156311587 863259433 193038203 814072583 438108195 192459810 820241283 228652973 40873444 506404874 33976675 722262055 367034199 229515471 758745050 211353633 117143104 562878541 652316082 417374559 751424490 43495108 977169467 903833644 703928697 179346654 741653266 43957209 800815913 396704163 469318467 150182890 953743591 446071612 878582553 59688992 158591547 983971524 672653416 134131062 559846876 896744942 434279740 413915301 812887992 723917743 710739667 813304989 647468063 203115171 631649488 765259328 859704284 600758932 62692951 258067835 536655992 13216253 720088643 315282950 27746218 677904334 89265925 805391638 807087892 10981887 413187587 68053124 729258870 685490409 732734804 247782968 718023370 964697836 50427619 467011752 398041042 656545977 356476385 907015559 323430248 284891799 726816199 326686096 504689065 237323393 48067102 816332821 854756404 301411563 507853851 925798283 288018641 230216276 270362335 729383104 502592518 345524993 561490989 342862365 635339910 97744604 516522722 404820838 642953854 834409946 212517605 524178294 737278966 159015619 86416748 534981952 784972726 205221890 734260844 710349238 582599715 994478086 677691814 432071145 733990718 931912724 136955132 765304846 28096272 175842894 284099175 19209556 691435296 686428577 237318994 109437953 735228361 320221166 769877809 399102483 647630931 814353207 503334011 807893626 326910151 379326072 263677848 715761580 783169845 134240449 729546996 542493772 956239975 937660193 439998739 543405382 624104631 918138353 823197528 552883805 781817383 967601319 948693260 222065563 759485387 875426053 922327210 226784953 311525102 819973161 169794531 163036403 760822100 532508542 373102255 196749855 609581628 520160100 744222410 962515946 134642012 142863500 299499672 877044041 195926956 2659457 833524047 537416496 30635656 324135839 881301776 86427755 840784380 483210541 170813174 792410229 681317124 876427919 888723999 657345475 363274661 109882373 39244502 443772244 418152355 520171240 812835698 728870392 103092626 131321915 450587046 486714084 858398339 860528827 422420155 555231081 336714297 881162 429620324 346939261 732480199 213320532 801237839 41459567 630467758 362353509 723081318 756270571 739851714 592708881 873255666 326209388 2311639 767496929 708880131 153702131 976365822 67873209 746940776 227935451 618266502 655457819 961475569 569377817 75706658 427235769 209495951 682152445 122509992 932646168 208819755 591527878 719291052 662396589 504808800 179658331 531707063 227708980 365972093 310718823 478504332 786655256 510956280 826753544 74325026 881270146 437212654 479600721 9249419 135823589 96951807 960169189 437166965 835178450 444479569 495070155 267433179 944297190 631858016 322124289 468640034 336195078 220195419 883671732 304807192 792786520 21842921 198283821 183499218 292285824 216044753 736638013 155242297 657380144 887112902 601754940 130297821 103743222 682943057 703385588 539342726 310069175 310696822 266633495 990030050 17631316 658146262 657938700 966473199 623175118 337082627 298967887 932635543 313834004 533102266 760542608 424666254 494094303 963721698 237412157 669185055 827474283 908840467 142207854 387681237 662942431 680580837 528232728 118548700 610389990 605752450 381011096 369021410 603014126 970868539 608453717 303017132 128294605 408486416 576507158 828270772 218249661 424467478 731408640 729710836 991088757 832462669 351584501 8950500 66729354 724411504 2794294 497783664 459946502 351489280 901940264 742448550 789767788 388626015 790554476 551769757 208868041 956300510 623760129 734914627 102149745 604870809 162461448 5015183 283891297 719263922 547859635 67376137 616929933 809200004 530362516 648719976 388439186 259510859 267988111 531829774 354760703 115447748 560014914 540415315 746671446 236822497 542565692 574925812 952337776 213859927 158578936 633113676 187847574 829791227 778216907 359653921 479687471 880949499 59811895 336288965 682008069 492468373 694228936 473866313 182270148 737646884 155768061 533679278 152698393 792319700 544674339 283749439 751130246 305561489 81933604 49772629 247386913 673205573 550487079 888270909 515038893 626692980 419808199 80795102 9578513 624132646 144911230 493218338 656002338 333495380 957947955 235345618 155733221 54177421 122468576 580413009 342977356 12631263 628775347 711671000 204040387 242306394 9620262 257074796 109189099 65024842 174562976 771524301 40075047 312301693 881408965 791828659 547968901 269570918 517704913 400309772 650026016 180691821 369853336 271534423 459553729 766892665 590340823 782339524 390885831 518443309 157934703 165965850 425498556 388746017 629472234 355386987 189654668 774689641 365287785 823202441 456687440 502934125 601146085 573512383 711012019 710160087 647099447 897419685 760356822 75670749 331713584 424463367 458082382 970519055 642775612 238116259 776112048 57827119 977356447 633054062 563179584 489146048 80313645 396832985 732524780 440107055 996535800 492480053 80352455 144171537 802421029 784626316 236805548 461085774 62009953 122528239 917047797 187223431 443612711 356712594 907504920 77948511 648498199 21142376 855802953 171953209 807387625 110311413 883814841 11717162 680577371 705718560 28747597 611283292 184371469 427571978 266241520 970410123 547534680 112058066 640550084 412852408 974217778 240956644 79265573 270769484 89532553 813694955 74766536 958228065 471971886 17006377 168263047 464057119 812549674 782326878 314097506 300363002 51761091 683339574 909044764 196440078 980657493 386873787 690204678 444780370 59501912 506485824 970856406 610089264 26081815 694972974 743737082 461180927 991548728 473212507 136510941 126611317 14553080 825605366 539042620 378346574 390423944 568347323 88686975 490479809 708103349 631122486 499807593 528442539 512700584 966767861 315402049 40204636 611534838 32678312 475911408 324493867 228996125 243385778 300527597 606446441 392109557 379550451 666788971 581561253 295763822 36495522 788920707 27470679 974853682 948480611 732147761 89540397 26373256 617279090 207973547 549840618 225852538 517759415 964286551 444660085 512548141 37722279 106773010 205814446 900543813 201368438 993448901 433401337 995612752 95873147 836786814 529288414 91047011 723281397 209844903 504715848 43123024 820047551 22976951 273592943 397675904 129920129 590729360 421432149 797452915 160140833 605497451 140353414 184846807 627312878 878214042 81086101 315482937 724242327 835733727 389820165 734153786 52959256 694419657 779763328 860097055 276418292 818104378 428786076 362360906 61829787 847684987 217419112 104062336 321603472 950884763 419055923 760434054 143626615 529684568 857970643 913855188 893650174 714287957 551552171 438322933 588630614 169476641 568270723 254263032 700386131 998414865 216531069 213205940 993955218 25829336 57357509 218298714 920525532 468942812 864789407 298492438 760677243 164656686 802998368 870173733 601946091 198575688 163850 92616657 46455197 657572632 59434713 11736789 46847865 63220791 417664969 719085744 256283432 57008933 383334267 144601901 953117996 43767202 431214241 195382886 928216939 154598157 811755355 873879458 927702464 904534341 337055694 494366880 72866442 766934150 287502670 881208057 549714647 163093448 49602742 176718298 929809791 762181903 40028414 621159197 511214750 751316588 972017666 320207428 783482132 110375101 616886628 765591 149808531 477042927 960115857 513194227 26121780 399322211 339978415 816734339 643672797 98792172 328127728 381886334 801783985 291645456 671795405 405797604 911044146 628123556 911711486 477964984 513676125 173546487 287780138 708884379 618585627 514185692 710155809 499137125 743239369 583489027 480669371 389282639 557183644 53258452 108995131 926991090 326333027 972066702 781469753 38873680 657778876 374830893 940037194 568897739 132973572 181835652 201312944 424531426 658427484 757479593 92138823 753902716 180300991 400960428 373884947 635986145 2558964 558509062 806802287 834183543 645968245 661635712 372365740 687332856 771741173 977477252 103609078 395230901 431380103 723627561 34622309 84844665 76374440 58789481 271961423 72152464 239382191 345566376 984286740 678223566 178370524 323694842 396780801 694116770 365078825 672631819 348182077 604097151 815889319 539450547 408003751 343574600 339434 349922690 9836709 599430821 506805851 18646064 776729618 841010371 124298611 453871304 832875785 677657297 287756548 434129786 179013611 940867442 606198313 744778032 564462660 109512669 271434898 924032224 26934918 664974054 799937747 89003977 441669934 755618152 687084621 173314737 732418349 463572120 125272128 467459779 695983560 525847477 426249403 374245635 277533074 873634864 797258472 560826681 936997422 739106815 896310978 440340999 404692125 88163255 716772957 789643732 313966904 768953209 225261224 333915500 507597134 501873040 726855312 519609438 743012922 261972110 330808152 373319781 706400366 192451277 587549182 429480315 481956346 857470215 522138220 729488741 79502541 209999987 981847340 26087702 155594734 160312947 93502346 461707672 763517389 131277891 301108180 687308587 708650487 242089597 386574022 133856640 301549826 901867014 367101306 57358703 49209922 296494010 94484344 427984773 977244229 285295864 931523398 955057692 438534211 876473837 488741929 175839018 350458382 16873083 343955882 348668642 748173504 692378043 24162488 938647572 522863421 684170651 440030603 434779340 378774615 396873189 687976842 573375684 768691678 516002260 783139736 164883071 811290519 950936385 135884840 606764893 215113892 388917630 248276304 139095556 35602759 780004594 206302210 945684425 869295004 393731610 442700596 115109055 89383308 291131286 150355413 865349281 79111306 337233474 553112631 771636273 438518446 103880049 948588498 971050593 109180374 408339365 32435310 491007944 802259448 7388626 709281135 427218720 414879952 280414594 574852265 943185912 207404541 129734728 257660107 867850775 149191633 658043930 951935593 177000361 249220275 208756746 668912196 215362266 749678342 666937064 666858309 945226852 39626237 162420987 469701658 619116074 528029303 48293713 642697747 399658687 352365243 747957289 278752049 8968954 563821666 412859160 943698145 530073825 812607115 865801856 738194345 549487627 556524930 339149934 96265135 494953061 945947473 389229944 716931505 432265424 573126817 813248259 251245322 356097022 988556175 50999629 905897019 630519328 103956111 235771989 565468382 704169064 212536945 849367296 818145929 913164402 43851643 888607751 730115894 16299369 888543891 638517846 123904490 930733970 282189292 798400745 219278651 427762841 135830421 660819477 890934461 949629590 109077068 432400331 176119664 784162160 589992728 692391941 47093556 941892216 936164719 192961008 699241861 423589481 676376059 937512532 497254262 868818441 226842440 265279022 94874124 673030970 984965826 407133122 595324539 981014914 379849220 287585919 763287731 277257694 936463856 217331941 384756506 842033161 175576482 98460921 173640631 167682774 434220012 572437488 697420664 864815588 310571873 368635358 68404764 684949802 769021888 735124832 965477715 153387501 134105541 930968388 176036729 633689083 961726333 548307774 140991700 539626336 323073955 826805646 334693062 869223315 200840440 483425764 285243832 553111779 267741814 424557367 698581965 392888113 163618149 983838714 176074215 564228472 751760918 152569758 64709831 145122804 34475012 463616066 28823170 347733165 328009508 81030377 502462803 682877674 985081580 936771135 903554799 297871388 697921163 742127971 62721578 741854304 938601414 455859124 194988502 677112777 965874242 5031874 5693757 968895442 670775835 899140475 922486130 273233143 429905515 556756402 855698440 870511267 816560743 313275634 654146927 948612938 127085988 675104400 607135922 715292632 647123932 868145698 329614913 519228456 261798430 9866460 748921077 394224006 519240695 206376312 406564824 656095455 359432692 547309610 249330330 385341009 374212059 801544194 269492315 532085450 940190436 442968264 45125719 917540970 913723310 950033571 916862563 799392521 449498324 796986198 228803177 920580300 509903068 61586789 628161055 7078685 760912096 796108521 80815668 853399132 172164413 342309733 681545915 846234487 650218438 280258968 192973111 17398591 918172944 115464400 991369256 913698119 686752889 289019537 41955942 242348020 801636962 178818835 464329506 46463572 76151853 149337131 115397815 933334526 630186215 107605337 802764814 819372020 420062345 346982816 98128244 773018346 639549465 364021100 606757301 138980279 87273323 747551225 913444490 282186329 465910300 424652196 44044220 779370769 841506563 795814576 300998632 801437637 553465030 967238338 818583008 906340932 662477971 320028501 665500298 113290822 135331806 2783349 243170165 373157032 143514281 4135092 32532619 545684604 369324561 959866527 378453661 999347027 464908292 454697834 873166897 936511563 628406505 253443343 711166913 697015011 639864937 219476505 881044231 404514774 505573897 711516243 647684778 482811133 501204622 963371699 927644277 329804106 770518707 983912298 181407507 79874828 239213899 430874454 256769243 907951265 779436134 379576206 183122935 660437378 637859481 536372717 637430121 214226595 177075978 968150777 142548174 322351651 388166930 624336695 563444090 473995442 744952085 460067765 614501298 814946273 861654876 672921995 63217429 857053429 352167959 122787848 660203084 754100336 481836383 9382673 609657631 726323801 972794026 728491905 639857038 236836520 766157211 499553097 16875983 156689919 203597167 727279497 906604841 498973779 251377509 660360476 95859311 990787841 651734219 970032552 299977022 314020803 544705579 994674421 606013858 518414570 310972184 96057357 147761695 96774738 852801454 737061854 65019418 546438961 7869198 396735991 918508278 407871914 423646072 370535731 828911957 13748277 598878636 468829751 625834340 757983483 14748173 130361382 463407213 955403760 915560826 578064782 285112093 386359805 239263791 719790270 354679238 139499508 264574615 962031528 370585551 545589298 756014244 635047280 481174524 287841395 851933916 586002417 955456703 96965370 313410338 376460929 235565646 91442267 437999462 756360211 586033731 557372829 165199476 699140365 541332644 247862975 952470508 45300741 367707099 209655975 385358416 65433306 4725310 557402524 602113633 311447330 514362670 428618272 811526319 240716336 785556263 882864301 475788864 884132922 753089321 547193994 307535336 111745278 703027168 515914416 553939049 285196337 438242278 85615144 684634710 492534955 445863760 276060956 7941012 570747884 767803410 465437448 230526003 581339540 608599074 167750436 34765383 76003193 897056053 448763839 430860637 761498697 19394934 518594600 558874412 77836683 471870493 765713551 622606599 83920446 977308375 397784002 581160846 295455892 857845009 259781408 409887802 877202570 948732180 630217923 881752620 981831407 269949636 284658073 249029054 312798267 645802859 443730230 418217773 791755293 726848359 825955574 444551714 226413227 889928884 430875271 412523227 13920030 502417346 657362696 124261709 945146485 399697380 792081761 122035693 146112419 389114331 455176051 976211957 37851280 197912287 760871695 923561613 334057807 6279513 76613517 382633337 390401256 982013857 213997047 474991451 687582662 122031308 913943949 606148729 626597193 185275674 742044344 942730586 561233231 601888117 839237373 881796610 419166356 827798137 608433795 918805480 860269894 176295438 997681324 612859000 204030517 950569588 300386150 469443229 971660705 931314269 894441518 229670624 906059840 251130866 640421986 825235171 573735634 989555957 383345528 11586754 403192748 459407021 273677748 725669752 32183331 614023946 24432086 114780182 859405604 527895107 450849404 603452085 972710590 205258406 967935903 562473146 979417539 40149987 576104298 372598011 590670672 201999588 56493902 245917808 201069988 625290942 737366391 39900358 962044324 997165376 217663375 552159825 367742788 753567340 331857538 881208065 136640501 305429433 506939181 939134953 36258761 788310671 61992307 979877561 346362441 372045878 576633116 608511188 48447222 711879746 166251348 929706907 323605461 59361895 753296081 815177328 349497204 129133904 240175316 29751183 181167766 972342420 425512357 603058026 142806459 966564839 832343449 277064815 766103146 128383222 319787167 342903997 942471792 923084847 379342899 827493252 225902580 136979894 786938073 37227073 507387772 848435732 218320166 68392283 460651462 110820631 745319933 713129281 248213728 723756341 563807138 145833919 865256511 996535340 322132475 884757671 912472799 114285966 711426501 708418438 65583231 833562968 890883696 588991512 289703769 133214941 74996143 615647866 892807703 100672579 945221872 841514815 188924223 624397566 605953004 164816059 517388285 830978520 104560700 982183391 939531843 248660735 500425932 662940113 520692099 324103576 362332403 54312472 931744193 80225520 804330295 549387367 401797906 19064423 430746143 828137793 108787352 963153945 805503529 314254551 843540613 1135128 467517613 193420069 24546035 358966328 464102472 126306315 629663598 68453512 509244812 381290729 379758680 252583892 83923680 872586287 873506413 520599398 156416312 365199112 751767082 33277046 295156463 962406918 483351757 708723424 744769775 136619248 742996215 219465249 769777286 822655680 673244895 440313872 317787972 907932990 628125764 615435798 174286793 650396572 465389724 317874533 605027368 986439794 352365672 436982280 973914688 535534348 905339459 939860538 851334493 291193130 566783130 51433872 493154812 73852433 64109221 144300865 122102002 181294991 695786747 429760814 422825095 353980137 473679961 636980768 141548441 348963298 129657403 633019371 146693768 72383263 528422288 892143479 796907136 295749846 551370209 217524196 441950527 515115729 196945110 526078916 620541110 556097635 480984053 713789218 717490925 23469929 767237497 791284854 649462842 857427877 640746155 959803519 89393877 612954821 157581238 85549218 667819581 849701061 206578260 157321300 265608850 879884230 727290234 878156112 409377918 343754108 622572160 517025518 141150893 981493365 987433782 60296357 28659485 820264842 577693249 948373947 352884393 778906055 294785436 754439529 720113171 15516787 67442740 415113348 41358361 102218726 13024823 79385492 429730480 898131270 615814769 796807819 509192542 859959313 626075677 794939774 736707926 672305072 486051818 379672512 337612141 696428185 465068312 638463501 74151395 361809946 706160913 816003282 261825162 49798052 251069757 583505491 396857663 235340212 310431178 125665102 545869607 36305740 693181449 597887059 580531893 18974691 722078073 999352378 950993913 957824272 271762677 897202082 194976659 75291391 955110453 111962828 283184339 117280602 801709793 221704842 881515703 2444110 707421416 645480435 904068443 429516011 691894183 36366819 401674383 693957472 541094852 342020769 295266052 368415496 601038098 616392032 574562457 621280336 550830458 386496489 804663990 388695967 296843351 240491620 480432584 90866781 345151981 764726465 524940136 10294827 549625520 65015300 100941608 444244784 805051265 629277323 655661181 243715362 850913352 415276056 379864970 208292562 416479179 254103348 588609173 102354696 488302175 169552360 310559683 204492360 290080951 762413768 107709360 672273650 742575548 959612922 18722662 610215878 910865385 683199750 108627787 537727851 15222736 406547700 3841354 485782898 467991914 269060721 81144837 822978748 758588648 117769845 931399479 646771613 878542481 786294109 505350557 936818343 189099138 990052583 34358709 423388796 709901406 291399054 15227954 574530942 950211327 487672561 509861514 274387455 21162617 803744691 726920801 448371337 580865546 959905353 800194656 486689488 163065995 327596136 563921754 936124004 802563385 449584663 515007918 134486469 609301555 840966678 413353909 787966472 905085486 79661906 114353882 854913621 515201522 400093628 969297910 992126563 621832088 687292909 919914797 884824396 201704170 956300850 861669066 654908165 29004653 334039546 855968335 11680437 825575008 675139316 504095961 910763626 798882329 376237819 221713279 540254829 976859561 211338718 225983896 644560795 155390015 969980317 764796754 170121790 641784736 476578960 356194783 918644903 784862941 819476094 22776649 872562580 666568173 807341169 696308770 146902119 118947889 387540700 294867976 873164171 863434858 723903640 45236518 383907546 77819572 288281747 150124611 533735087 645285968 138198970 881031653 899029709 754754663 864393362 539212658 435483739 571458748 530026739 212947472 832374812 894907740 820072963 125485419 724939175 594257876 719184257 405289444 581422765 16748642 224688370 88817824 354294367 719310569 141925183 471940649 225053827 258373688 629925542 634088352 318238626 79810180 521108015 414768963 436468774 888300320 265183335 527873069 686554809 113878606 2734948 204251283 10599019 970816325 903926212 225162966 32154353 245673905 887000281 826275619 107702274 485306321 617790967 896514029 721363197 617310120 296882437 639386765 468233930 886064362 176787442 713053810 875982268 582379630 723067722 131493930 601320512 531237474 939058968 790111427 977063426 735035056 90717911 436553063 799808868 279465944 275520695 396758996 535015433 318118716 585181918 712855087 809525000 829571718 50599454 298959461 687011600 789862732 449799688 910143532 794002881 707658448 342139228 140939047 570025341 421816057 230194620 533542566 39934528 942006748 941764797 888184639 864375054 480769248 468242491 897172498 39528787 948359242 443530856 204465217 784091954 34687820 98655991 675769864 51986422 312996606 751827541 772835605 929394607 821460569 512359470 812357773 711042245 15380918 110821700 663211622 542338536 241103060 760245355 250744774 46809835 105095485 319197702 25496212 782186112 34444227 672919230 12191009 829068344 496215827 962707855 678311291 936185681 858620328 859303927 537050150 860817730 8821537 456380123 707371896 968526139 499190020 516196275 311685539 767736338 636602339 646826829 107926755 272781981 554829676 768444969 642798592 82502339 38137346 798554016 582464525 354432515 17899076 854532862 603126594 779260416 760633741 488599495 625651489 826709911 327580585 129223862 330845012 472517594 61435233 739761542 787582886 909196234 986273270 390298390 870224104 15152091 249023268 580910944 839294714 431663711 477609475 70681433 348262724 989479293 309994459 189666535 254994807 682429510 327148317 965957193 284120765 349982896 197906010 810448552 109172824 18154271 175809889 689408534 83406591 707231279 654488813 574299144 41237438 601042522 814801473 603088180 727188965 263997484 857261412 745719033 918017974 409510830 897841 372103632 125732813 187457738 914838058 180118033 609022246 550190341 609099199 266704369 645184013 403994700 821322896 808628755 66713404 712684495 270990313 474660160 318468643 836381691 417564939 406976259 854812734 237223056 90722376 646277242 156375831 99997553 841426102 279243802 274322455 664701160 171692523 17924381 772550152 237283257 253858842 438041633 98451124 963970450 714517955 721285558 38579864 351438988 669428395 931228587 459900904 540620244 174380685 540629434 654844714 565942492 199129660 619434130 280960601 904868784 797986633 622467922 820289441 852705503 255690074 123219610 510567445 262435521 106604352 256215127 435044438 571912002 798405173 849043013 45029023 319618608 577342801 8373683 257079864 939499340 3972031 39374096 605311684 681715988 449806564 822091795 424983236 861852767 230406272 617727516 80927906 669450523 910363525 31238037 768508560 111768929 462851926 536640286 919615962 849237785 431152807 439192564 253413540 429958285 60313147 655311451 251280509 774319045 412600384 317913208 135006015 65454180 953059194 102781535 797343814 406317523 20485873 689921820 118346115 305125375 538329092 467604726 917971809 150372658 723205901 80186002 819434583 264183875 879033073 64846208 614760869 464464013 808839273 94615664 635986878 376165502 271468707 56388335 84400243 570645317 842820480 511069298 210267624 962862500 482081613 107265192 212684157 870602896 90585466 813680790 166550692 392627205 647678298 616720402 509414041 367449908 553029226 861564671 275709990 352016384 727102220 733728154 29770369 386268874 516901970 10357982 612053306 959960519 179004718 706273803 441050436 553435249 280706319 3401667 790149483 505162469 451645118 30428195 495197166 587438570 683602507 839254557 477964088 847857161 690374454 985543134 467067628 2907534 667038862 559516477 12204529 88349997 875137147 452384308 783580986 964334088 957816791 243698710 293046672 711668181 125757152 782911517 898396611 77757512 691824360 444747751 688769115 783778638 405864473 761164530 758471795 74633224 472885294 858885082 894991220 86304033 501196126 496016578 683199025 777758079 968880366 519754737 412525206 722549573 219272472 241702035 338627531 237521766 68160849 661025320 10773274 66773042 265370305 146087576 70128077 64096793 426078443 812623372 715251687 908736545 981900293 914209902 683643519 386104283 726925464 26083998 79075242 449806649 149136940 649684896 385773703 494721682 122787590 711128461 374933555 187238348 819684144 792058590 199882724 755972862 450987102 721725553 238632235 683609309 511761588 950086685 458617862 811629655 768055239 108896728 612783077 502968803 649984459 494536738 443810539 338864305 167318717 652373834 227720358 280924575 623166153 633919891 341041262 821516651 64569468 234588271 146550574 368750632 104249913 143757973 164862942 330928960 77376876 584576158 987342978 50454691 10780789 900873792 89025630 875901464 642779912 32780763 118077335 189612826 245121701 225206331 660007641 723007355 221227838 762788873 582807446 676070775 314941362 750015459 416889767 773315450 112695951 780112214 527340820 72128011 448434764 516769092 2043283 27937544 420361278 195790294 177066875 527589738 451250702 575873451 399255097 403228691 180876250 769402237 198105131 490561265 283865131 320198492 169538358 13579218 225077433 657837635 675387851 394224136 724692336 506853809 31395963 855360527 176824320 182570090 170254108 555302321 524445236 643837128 206332037 115481615 903167639 422096955 901912376 90935992 281074635 781598359 707820611 425120406 991586085 559880788 332771007 645941586 751861639 753277502 690505266 628542258 5966518 129471160 344592998 472214333 24147532 850561803 888946978 700694218 293919851 448409261 122321895 934839583 40596573 415559524 261663487 351014995 469870713 176365353 212815545 260544680 704330896 392241926 768658777 695400264 697769668 661783404 612842991 944459939 884306160 273279647 130121591 264917051 696542387 219566287 563595280 215023671 596497399 664964423 213935060 669608068 534606339 861237499 547191298 424977477 96908319 833856899 411770793 704101793 771248757 338436584 925652624 901710997 766031082 160950890 262456042 127593378 242877396 555446008 276728964 40518510 83961271 830387818 146173181 343462861 209258696 284460916 108304489 304967282 834771024 308656427 414222130 538326665 99885063 350056913 350420915 884839586 952345082 264195237 332899030 515938709 255148404 561631615 678013903 887027899 165116989 774912411 151593617 847531094 604207077 381041990 683257843 128936112 410884397 866558447 436799747 19884485 623537143 852942411 883312001 877590041 428247049 612435512 988412785 954588286 169394094 990140752 834558005 915938259 847722998 924149958 913681922 871025871 939082136 49925967 707132393 688694874 535591625 976062008 299082612 680817015 135818684 543529553 658572783 174929695 722509954 562813358 500799337 789741074 24273196 431056350 454924899 572021912 964208360 195418011 21501656 473383046 543104766 697546830 624257460 157489388 547113318 631151030 689168810 45129790 480602155 996145165 92092320 539162792 800280837 634968891 529247335 922221574 946216773 663867551 397501017 680168107 391830088 373968814 440272555 42659437 304598503 5234267 853696675 715623677 84055663 774352602 360351017 107506756 781854443 634461047 612066779 219696679 988174584 278939061 718051109 678491996 169341208 722252586 855357441 623483878 77008848 42079187 215689363 804451792 185176067 295845561 260353550 774537699 684791500 734975100 275337036 303101560 245665381 642874769 627334638 376638009 169367864 661874228 807793841 524806160 211418952 845875599 276625810 32670963 872514614 909053285 92519293 126653772 802734161 844606902 670778166 465684609 342396095 859694466 525419138 648452329 130305658 55719935 781843408 323339590 446585667 44099418 811883220 323871692 64818060 699581620 144919148 532146308 170238583 775090578 440249614 458745165 877182634 401509666 709921879 306379900 297767716 224556500 813336478 992021520 154993188 660489934 36070474 991941496 575980160 759923149 766305305 547893775 527726563 5398133 787190113 933899100 76326490 456580279 129218741 955040555 831676367 605632509 637698919 462328065 882632124 109971661 5226748 708958293 456420151 6213418 261299640 284229603 344235406 338619854 339756752 30720771 248964846 121421088 704219333 566589310 5118861 730769491 748889125 367407886 624706619 685770067 747630749 278595497 898038502 889593972 438235080 100085416 640282846 810446718 895148632 612243637 515658028 246534843 318836110 419100920 531831837 563316407 459459618 756191133 576651625 641590634 255851476 189538315 803739104 734934892 994808251 329999961 952811963 324583796 581778985 37712066 622287616 245870035 286406626 331447288 694851703 778133459 327738458 281576469 599294525 917124436 300120116 207915626 736939186 890550846 854247260 6948533 965358544 335784107 425428264 617765142 597268315 481573986 737993418 404458339 85468727 186713900 618984492 695709773 678131874 631810346 797794108 392529103 686710308 408011272 392324401 305232582 168456979 76022427 726965017 214416317 896504991 124549545 490716174 388679153 114513164 82049053 684191732 483836936 180189014 194489638 117707539 910125634 184748191 290755256 743040123 276474687 771809015 316029117 135154846 484399947 83378365 95336554 624883636 843434247 662918129 731632363 960423638 842526348 345432870 432509730 342289149 448608184 26973134 673938661 8490638 206542107 420477748 64765088 487656050 119322298 136838918 215573297 249181350 229859449 96414660 9267543 479479736 761187698 797126334 651144537 397327643 323508987 944177311 525803031 207591094 291585664 68146227 958297317 652012539 395272192 544250987 11351115 90940329 231866539 525509407 101822221 213267860 77986495 307595864 324478935 820328390 78418180 833099039 354626666 858719665 717923483 806337972 158789544 975130283 830793491 383032221 228254524 782288719 485375274 497851725 703567682 677465757 556276018 149154228 837203044 51935946 545430042 799497048 353163240 786574627 102230595 971784956 559940709 920915133 246154825 87168842 400454637 852722766 777149351 334271106 769500248 637665707 961807807 590515749 979820874 564088342 755829890 933442876 445380306 804621598 860306927 37343622 527985991 231497681 309585175 887804626 445578239 862776608 995983396 478329397 657037712 894455124 470482803 215422964 932374411 904404551 185930185 185383413 773407267 854001947 741646730 195477980 485792739 1646438 484588836 3151419 700729300 418883971 179355027 312736322 931653383 511000002 151667704 631434076 398838050 632917712 24128085 21446762 587274335 579300211 245931893 628097373 17412400 286257936 171265365 954562377 258765455 656465655 470633293 993301821 867096909 368896986 126313277 411978272 653127382 916401248 288991931 677141634 632052070 907073699 329923473 918696282 335700231 644521659 495288584 867190624 758587059 555521396 419370722 113718149 943757726 81230200 289939592 522785922 100414990 786500357 12292211 232354586 777421627 115453318 370738853 74569535 9069855 50037603 653735783 62934373 461077528 974574646 562052885 536958169 327329426 242890315 260608227 212013929 316509100 595298155 722546094 650010419 829166213 983472892 618109139 533693864 291883796 405998862 77945877 42407782 229889114 743959181 976841322 853787654 192990520 760426594 662649588 402053256 468252799 564064513 921770560 504832845 391946680 4038013 436660336 113092646 551223112 86425328 376264184 168318463 543522830 528885180 736999569 573135659 866882711 621174008 786620039 278251175 488995630 148174157 672483719 172121848 555475886 983525847 762359624 180163943 900256380 825015205 50885178 757836867 326580141 974609717 601872429 931112819 881340729 327785967 738126608 327733398 585645034 69155288 961691292 217421088 928995639 966723799 913855767 851149097 208212429 242951614 875813294 57921382 692005332 635804114 853397758 99128393 821382835 563674603 668168355 997372083 724581169 36900477 407565073 875469110 440720474 963628810 173060130 343395355 868469983 43861649 1362597 191830984 254217459 9076913 408833423 22282859 975356446 321433591 265247811 567072511 248484868 714669485 853818657 301586975 497857741 790525494 704353637 297819059 792827728 680336222 260505129 147438094 464295495 547144793 139030711 392128664 961028871 620459070 953639412 979104255 929810358 26355628 954059935 100495200 621777275 847248975 299650624 774664759 56547530 138056574 643578493 885950092 833728619 769608791 879466894 480562707 500335184 230204748 554834285 704335989 389469580 449780548 6341882 941641012 854678640 178943318 100125049 291428019 465725766 733641524 547469838 359507172 589301259 254846346 842056356 817518451 355420105 385623926 744314735 774085700 644604655 403360585 285715808 407422946 861570781 742544072 152212135 507809509 850389187 983472807 187175225 144644053 357493188 672967253 437566709 884173883 433116506 801865119 444946388 533962970 499278351 537428743 828301089 642576402 233525700 822122108 147361300 839613000 573121906 343474162 824328610 893994883 846957113 310053508 699531019 657462903 922101411 126670295 397969622 663872196 490262550 824048283 600646507 567025851 732637737 357572514 429920715 107692966 538247284 733907484 233441397 758087980 352107367 840802667 992196063 225809497 196392205 20260528 872335400 174771358 988318916 111092197 928341323 423097292 685351641 79881278 75307654 485137140 18517622 321573638 659216180 620256772 622293404 809563173 541797956 923421697 446437670 873575261 847264912 191125501 567586684 454745211 79624684 894907445 91077912 441528008 359029229 637224358 605401548 628109877 455550923 835938240 412056182 671760159 368734725 643419449 320291392 322178806 668928911 262581167 848888793 889081590 976895118 860662906 47740628 510933827 806093118 50697839 592223943 686778934 143451628 69270619 206581372 234657027 184212390 754159576 541443765 461681492 461465984 985866795 583472426 907131220 82605191 477358670 279205807 504828501 287297302 226602977 83147951 828606832 833169231 491821778 279252144 541427034 643194251 137241554 220085801 176534523 286490862 639682927 582449051 148325949 287762846 948022790 471444952 811924068 718111692 498719357 56379435 843999787 464633974 568103253 259791558 551274347 42419884 872071977 401822461 151674550 43768334 431301954 27032736 753977514 691093493 223729313 383014667 745218691 585470440 152340126 488303139 375568482 862418362 455177173 465123893 331945860 79155550 369820602 942822622 602078931 715170285 794939336 406605465 139535321 406476789 326249444 971408282 969882117 661117137 7527958 394272222 554437753 285127938 689961555 86314401 762006317 873668231 904091538 454381803 480980206 429656261 665981894 186861869 754483469 514976599 23003354 548716839 534013765 352903192 626068725 389393124 191154952 201938939 399534442 515238795 941798081 128422348 839870232 568194294 835861673 551115781 622709134 151008694 135984266 218658897 139171389 804952942 685511819 90841644 922898575 435915171 375046444 249716979 904692966 915401909 828379853 448385801 791423275 883487017 565074999 782684413 837438768 311063802 831315788 570362958 883364840 213139417 677567002 919516721 524692749 66866994 723352996 78509612 279296565 626442900 125175681 504348987 812493864 210620060 426955851 70848003 160925308 690254735 907333364 92071221 707711305 24906332 498786729 875271191 499888650 987653038 792710592 608704769 876548311 271213771 251441188 50854950 111263489 173113177 992707051 456830576 922566470 760917594 738404309 903150026 188375931 133114397 255908010 825429491 862182385 231410643 211258531 554261881 114304868 325399795 557218957 546537048 563083098 870743992 104406576 960509470 506126125 13136669 604864505 331552922 73928870 730749914 594726237 783535610 372960440 812305505 799864064 214553912 411266454 527721055 413556165 534738587 138864972 652093616 106462402 148480811 112032341 829480704 599873996 765560870 113788961 710308220 836455512 555924122 449731414 942717994 172939418 287590556 374360647 503179299 606869687 212695628 431407265 820873914 355348342 89396378 814104286 22692651 804981211 9211262 926684279 270805987 831151826 546827978 942428862 256877240 97641639 995809026 315789773 118744639 973982509 964565496 594808048 387478141 610844239 95809437 886826209 539927308 728746648 198318047 154814197 389620563 357647949 852865918 288568658 44187293 422069630 943830165 822495033 444273643 187654075 812472254 465047384 960836698 16825281 862296650 8640785 524234077 714722534 539561157 120012206 864041381 16467458 149224820 332843119 513528867 305455237 67919991 343082849 128075106 697671259 70448116 632587831 72408936 593207432 575296109 227748103 389206819 973415166 554926392 619442627 656987126 777768462 920388845 619854197 306327934 585152512 388540600 348828638 295015221 421967670 837794492 623279508 764562277 565347214 323757479 85067808 787090633 70539585 415829745 984081092 622633220 409859504 801993366 236445938 349525645 340425573 187804208 793655097 878066836 660831888 688016294 176228391 810951797 370114685 234240579 882704815 307875983 653914012 974716549 993211344 973310381 29296928 651382417 266259693 735194359 44095657 60992446 12647636 81881222 925683527 425956752 577664375 647287688 988261169 186184413 454218657 686269630 825421004 74533454 136617221 927129637 683366269 547964797 71611435 275562508 993204686 342186088 110475205 654203732 651547318 719579617 464096439 376003850 917364631 725503397 605627157 647227809 179363182 768082641 928464469 294589936 480585508 185882594 921585522 694645069 992143585 360032451 848045337 229646918 790912751 250207936 603129778 63295883 121752034 964326754 185309382 622956325 584368550 986482104 254660840 227601581 223489382 565916414 707767298 529277281 36234018 600417717 955163263 178094133 862828915 811788217 117587430 788426245 773675887 889949143 890933713 892670614 4192804 778600850 70194764 186392538 835512695 743357301 348189644 576642553 712910549 739725742 438774096 125627096 456295929 502297899 654866209 938309021 146100812 738498458 860949451 319976901 534446771 151974449 96447933 154251708 415015707 895493507 669052300 948458495 444119605 938597824 577041621 229932415 839904299 933455192 854764087 828568394 571671587 446635970 267718318 748091844 10712114 609165709 461978309 113338290 591921225 24833552 339693937 809202092 679206714 143120634 503652278 601578970 137055277 45496081 989815545 215940034 451458292 403079026 841469863 140843282 121763885 780859032 470834899 462776264 319538586 911807533 876750108 727596057 989282711 63718597 515019055 869786854 940837330 697112750 287638625 689661226 277635396 808138397 619341352 549230819 387037009 626185602 257531187 468095899 79522542 377947424 186198258 114554082 172634775 718431345 666965431 590898848 698151717 473807291 679820432 156348526 986694013 353885659 231859053 190970605 712472281 655395284 865031371 413248676 471378156 31949628 586016657 824469952 592960718 519920217 223733072 223921567 648809953 658920698 169063334 283120731 684304669 782052329 887209944 332907286 819854019 8461067 368407330 199890952 895569230 530990137 823978175 959539113 932006320 859204234 784262978 190654051 245477091 891331620 463932707 909669375 319575075 579103630 988584307 624518541 236783198 447670203 730051491 71235215 586495988 342991728 672842477 616936353 818709663 949063003 875589441 877205736 690898839 427100077 375690370 655946918 579081409 994621725 154447349 263300085 565093719 914583049 639944402 994218267 54516715 554959019 231814389 466009160 359063468 666933723 747790872 894960418 140393021 501889087 116719858 181508371 656543408 821835862 434762188 995699321 180554230 560141709 310161262 912617407 151316161 42137831 250740884 104194428 464840855 517025592 341618473 380544344 144375431 256919557 513924042 562183158 34635974 460864251 718841852 680357262 625120024 521015003 783183471 355552028 680091195 482223390 652608194 76526721 276556046 181457721 746653507 482329097 878092866 61213193 294818912 863561370 413449919 712448718 845432633 26954928 806581729 661082435 659302362 209973043 473198327 360947945 510867365 421313784 188107695 569126052 57209255 803009616 325251298 368990362 646870759 839840188 351983715 506170051 379351699 181711822 349720412 896452737 111022370 128891576 841788145 868769197 574476764 611541529 687344732 803993014 850112817 2264576 926175664 668978730 989125695 752509731 165964516 66233295 545915214 308573821 979356226 629053192 926683720 774353522 992884959 611962686 25726730 454743504 301479995 752746612 281126907 328855361 499777684 594127176 130979938 551881364 518540425 752777837 783560294 862178250 921744095 913682701 569073285 463966942 856977002 106461800 877134807 400681351 673936424 119868792 539686995 282170746 234879058 264159068 203877027 687155787 395812945 868350945 447317345 699179755 872461458 549683106 242569237 180239745 186161652 578087535 82047980 513739435 987106145 82547061 741110489 247622597 334414836 857254595 188721657 670805543 417864365 512937150 890475 916953661 99221264 185299330 841244073 148661131 292500602 846826557 978861306 439360630 741763356 711242749 245892273 558854499 958926177 394714307 716243727 456068629 600776746 974885078 754299775 781066922 881500875 960342314 100287592 123148499 338610873 610800141 519189676 446516446 939761784 961029938 604155410 375291777 399540212 942270004 268119806 663177797 62437741 310317279 214942891 519743605 461072754 540111208 469822634 179331664 983035251 271060629 295194711 324126871 621296547 77870819 340272264 901089362 1702891 890983949 367057545 706660428 825655082 874131769 498601962 977306174 78782639 181982911 723689776 272924766 785009201 63768887 728786629 339422692 675655734 710284207 231844922 598642301 708158277 284575151 271788400 576866305 993869336 221694229 877951969 771738432 856992237 349050284 955421816 618271193 869765463 329982052 89691556 433725917 769669562 729322416 643791052 113939062 349151790 496838081 520412551 159949744 389375208 425861255 742349843 300858039 378316371 988583967 935184389 191982 501769821 103111494 961303271 953182832 548457459 679036784 866684556 892326457 363986385 483863968 621662140 439933010 545170666 989329494 282337335 551893303 409681463 640442561 267281318 405316460 758437225 832878285 648624277 229209821 403906263 651148747 483346556 437174069 857514166 238090987 45566169 63516972 311099636 292310769 754069590 430208787 734079944 436216789 57761940 112646060 706261812 521957800 715757126 81535186 587783577 770704533 739707589 237333368 139538350 685627400 398777763 766101812 977032255 841637904 224571298 591934193 8890551 20924883 374605926 768943834 85731731 874832691 758373320 878054893 586836259 598252593 955032008 997924610 97422485 873874054 566433459 918808982 304369079 835043957 85184409 598171289 31154960 939920911 637763696 357791393 951342361 372160500 399984201 221479865 868696353 760397475 283877069 120399803 860240847 638525537 327380603 75780071 201521302 26568289 317953446 331529029 424144492 445783997 778960382 252890262 839642531 979617808 639057028 581481313 251911571 131288194 733113501 739121470 866024405 157312773 189426545 29947509 76587375 716256200 853814425 92091811 936375262 524871517 346969229 217553559 70278209 394752801 988327613 802308261 196376350 590441585 279070043 33930788 605422490 869285449 728335218 321901535 903032604 589908520 534998503 779491475 643529937 844718883 780437813 332178593 197361805 279124970 921573491 455352773 387456754 936963175 553985174 314532873 732471142 238218267 345044324 880084541 139814376 202491430 232839652 157155681 721221901 798252831 140773957 250499640 900852565 819503028 611956253 15669363 928396001 121533886 584254653 80209444 435177927 970307140 813979975 271306642 967838467 196643919 373501713 89496857 339007643 138282102 454655756 672222653 855076505 310594134 140320489 257853237 425788061 285912276 960115200 970144412 205491302 860350580 801814589 63522363 672602339 163325833 529820431 567253312 948013295 928792004 497996554 736113001 440437103 887940713 80056169 229758758 181037462 996181983 407803651 401658876 344107200 451536104 841052663 634660482 503727779 783543771 236472801 875514592 45670758 941109447 946030094 911756886 710902411 765390081 818610894 788272063 923479528 585778002 756254212 722622332 412213484 933003793 111232805 814893717 216092867 298413820 900261580 751892807 971116324 956542399 58451008 397809337 784365250 310988804 484828612 759078269 525350549 665833138 574587093 565804369 810521749 361709238 662163965 415767293 739829937 826570842 822604762 826398552 887643515 48896307 404596473 384799391 235502292 242558867 147581602 483684367 570168992 696654608 843272858 559967858 315604072 901804179 303624244 836467754 934047352 127709912 711434969 124185317 308042408 621919585 964232200 383079714 871235102 370265590 801337967 378270830 804732894 966837482 439098019 276571678 162169627 523307419 637493869 62131986 384671998 721411051 752772748 849810626 458448744 818073015 60313174 240569744 554877317 951559388 271227253 483333106 151154842 61665591 383874357 710349343 206756543 754813698 91694772 348298641 582074237 400247008 620258766 267108419 712744636 937808669 658999055 908558217 662674340 869837414 619928342 830496211 739268694 666382520 374526662 674090118 451999358 146450897 604383465 865608198 48679139 885796791 808507785 428646884 137512823 539454729 267766307 195568735 879320376 796022595 779582554 606706862 135114663 619925238 220432635 114863058 318249731 770725831 308194484 604552730 682691516 971338838 500517955 542114608 408650468 633581479 486814633 373997393 598789009 526098595 961122726 872770187 240863136 953026329 681901656 319031541 516158531 229880614 372340601 226356399 239460864 456774543 606302090 375197898 325133517 619492772 69375298 84802828 339535508 891115130 296897702 443720174 891680218 251969106 665417187 493055610 225936456 368108947 247707824 256084554 671768703 258355345 502335282 269113611 610809006 322006992 8562722 743780324 874535969 868796697 313502974 572014920 84403421 842043178 126811610 882912233 685275796 263532947 867728614 139263299 648920240 440004384 437567795 244263573 248398135 195893700 926794320 421400539 684458774 326774578 638802554 804579617 485346382 59149444 237954253 949035359 652539800 527510966 7434014 321084362 331606696 759281601 592294327 824809097 414574551 397988021 490422090 771302916 36748047 919909711 571486482 613837916 922641211 440761803 972843699 901895831 640777149 51818895 731815846 714274612 62590988 679459054 551029894 530885260 783991892 739258716 442492519 599405867 352915297 120405906 346579402 741039202 646250513 711488082 325433520 816442971 584747540 806553523 699721407 671895987 33190125 459752690 14144691 669204185 574743219 763897940 623960825 500887810 288542247 271758900 778684730 241400023 780755699 949401151 408106594 482830132 638630338 499867294 386114293 339745585 548847478 149503931 636098678 305838826 619524585 903067499 360903052 680852883 540781674 571173788 521608366 615641409 782285428 975996233 604235035 861898658 29014740 3920474 273879415 204797507 535639955 268565671 771284124 837780167 429940067 395599168 862553053 324447402 53027999 144936391 693332030 923089952 156059152 469807780 43722460 947612961 944876930 845563490 71518877 268633237 67407860 227536825 385149649 659881264 424532217 891306551 777542093 700930274 652039299 65558875 935453093 211946915 533341743 762839083 996000347 497402956 934915822 137216497 47407112 783518544 677796555 208693356 997065120 335871526 202914706 219343073 420457142 375862917 172361635 620578292 827652542 836486767 339429524 768328011 515852002 38336870 830181005 594323088 671374301 870327260 988310509 400361319 267842865 981034013 301824686 925462819 251070028 871338986 261254828 216739553 125861339 248871377 989102346 543115162 452945394 484475458 294922245 364469393 21489371 267570686 880175619 180814027 573629662 995787711 143808146 515138687 473336303 17304615 689511215 433052030 375574412 226111742 905126557 79517867 423050724 831979547 36394505 836689833 804435180 62347447 686733765 845737819 848561167 725766334 896198684 360378258 163405824 936682851 883778097 287934760 660201244 592717387 178299392 981250421 933920402 702982545 475456823 635168715 686047587 419437736 456328161 687621704 236889266 111485417 323982313 846701455 95050392 980122435 669392357 255879066 220860293 390433217 576107229 49007685 388445879 12026838 575311526 728276200 238047599 669447437 715479522 957517026 886157166 936593555 105749919 122800129 188515313 170999781 572362834 162180844 626858692 883356196 873167828 723442748 84081692 948620977 251184704 447314219 947384352 121080469 445943250 181980237 634371818 247187319 409716863 10030069 693194233 563327103 434634658 543752456 16931764 965119261 865028241 531281874 550661061 472643328 773960139 794169497 750163087 426992843 23153832 53675762 402248946 870621050 88656821 616646329 735645588 516555631 825604739 455074988 907992783 802542752 352934773 126123374 124280222 221105702 920062507 575067002 104849690 214960398 275001918 923729218 868918620 969474280 83376772 935625404 262435275 224302873 446609614 513326369 808191688 409026544 410201465 557183660 931155429 683332386 88278054 2137146 109023146 539179688 880094239 296324659 457417433 521858498 797749952 429858235 217448331 901007435 164319498 922561778 295386966 844595940 599486236 807171921 332684505 161019659 12593182 788259349 783793427 569022974 567267077 715180457 532365360 457803773 668958758 433982455 202960642 845205566 987753312 659778529 81434473 283208617 686837482 270535929 41331740 436076862 970795000 27370300 338503847 465147724 881601665 946622909 789997290 935287912 532238943 987824642 510885329 150490675 847807290 462272008 976955692 464793181 693417391 256867409 58164818 250747235 487875862 324834322 938398587 829377652 987762283 306654163 177008532 206664308 628369477 375059155 253372035 462483545 607763203 597258795 699054553 735629270 792847831 137497339 940713002 421743986 921876234 51699367 359163569 403349994 97297287 268857632 407760265 473932551 976527623 69810163 412529379 104271171 705175966 239437476 494460759 80996056 1243943 465171453 295831352 947522395 29826646 576176252 729324110 889146551 201392050 665388695 86251511 576739434 331712571 599671759 21022311 268851861 26916561 412188386 104668933 122497248 329385543 502407980 687122703 216170409 445082183 290853871 475214161 770523053 774510274 998160592 178595249 991861471 494298510 557594145 397792638 415825752 352451385 951795118 390515660 734986617 58799400 778557553 829731937 36639067 131924575 60870791 342358574 971210379 849929979 367644142 664475025 933736844 878933425 197338368 883397673 360554918 904362182 760580025 542725978 472516178 980485514 546046960 444068176 834935166 717449653 550059070 132381878 38171377 343715132 257495383 540649430 785701789 690059842 674104446 265349411 334449285 222147193 131512407 419796421 967182557 776161899 388350532 796569797 577468757 839703683 140329934 959679371 116571344 949116386 944866696 88512661 138228386 282445277 214425257 233587647 735613077 472112934 715410886 327435870 365232024 434582087 743799849 533543690 165783047 564798564 795027891 921135174 183607488 800587440 663698623 34287396 967236877 982329723 471033548 712982918 126797973 354759831 725958293 489837380 185589351 909022243 673165513 871093222 534980809 230007463 995207657 261574700 379577274 173064272 564852 295521581 368903934 708200774 3719980 947570358 379786216 237059224 372072706 724693290 790621659 651714881 931578303 173237315 808521623 929601344 336826110 807676438 619622522 99239619 550850936 168514104 487424201 686328889 331451958 386928654 805842596 443966429 233434912 649941026 626073794 21553423 276948614 957800506 853897846 136062706 275934961 878430040 615391045 410906738 495241187 280576292 768798326 903757096 872345313 563696116 560667473 843203499 248421056 158466378 73889047 957848527 775520701 986544556 104964454 632410312 28106422 1789117 203963269 756553339 414490565 909635493 677979436 145078655 829380435 924823094 184967626 165245214 281997908 613340510 82522955 268865110 651927556 284037849 422479047 26963848 344506904 697724429 865564412 621816284 13854275 216385555 48980818 404569717 238307362 58696788 225466999 710794141 497023156 851239673 321531996 993148561 990393084 223568398 899928285 179552808 222409639 713393826 445147067 478187663 137863056 384312079 729807527 807098428 858968987 260691840 351902449 52113248 690262444 949862970 18145474 695323875 611327909 423087724 140792667 619286471 784650456 883036820 89440414 676309672 351183557 480767741 799291422 973185988 829720961 46561340 844631099 610500863 324244685 290630447 549748138 247488876 140384790 542996041 604403266 71145748 312574673 40795633 5433902 607129333 597121921 972579355 519969224 423459822 639050462 55799271 572979381 815810991 294798519 297432247 452611910 685504309 72792790 656784617 303141127 237039587 521461417 999352491 737424157 335491785 62676757 299318584 907951057 847472335 119203083 908969867 563047565 406662251 178223649 867856367 720332270 524617331 748210058 743278876 680863709 745945485 498719914 4787493 959107688 93061750 546034913 43107579 999092723 410476380 474448838 490710297 471309844 458644860 351872778 494121739 326594298 858839930 584147541 316316587 578751928 104644737 837750952 451388859 778199789 802425946 230846945 191452270 543833231 704257241 302518999 918256836 867496165 23849375 950878602 394063383 790580004 214274811 461387711 186636405 62035566 550731531 166919952 148194786 705093806 131854605 117272902 674757556 161173036 319016753 469908728 915921945 672051339 604505807 694542030 566428870 800857944 524160959 83915624 409246649 717225479 827802152 846901001 274107192 392177767 347268851 211879582 59304476 171564398 224804232 361185732 484598000 587486699 638580362 300092286 10471016 395345746 20951084 813477584 200577323 977768353 512977080 853431230 952185932 513196298 850177468 483185294 527283093 308976994 13731219 549247596 390623382 72913543 783492979 776985369 911774435 65214038 711530973 690578341 852811791 922212560 249813335 269672046 222078573 136103892 400532714 557530483 39858560 839526482 861364936 108100300 450353585 341840656 60222410 550012698 270867602 70856028 758814862 704292430 941199780 433187753 297110098 128741138 733567367 210178652 370096991 510575208 435265844 580502695 429016176 788301390 773917625 888267497 57517988 356628477 311661606 388021401 459237169 171277345 206667881 548317371 425793365 33422478 519986340 723986345 166402473 85814155 616463390 153225653 321378528 360333204 890648106 170257472 631146429 625691985 113878510 865242732 833722102 535260206 406469920 371977287 361663017 669289481 458831989 312730175 42669466 556158166 43303494 662732029 27607622 244247281 780231849 157175121 484491559 125568918 682997949 200640119 177297695 441281801 893693404 44649965 554923754 540061468 713029166 274863018 262446059 403727034 812598651 60613158 47882886 171068753 730621491 52711390 22516458 846987600 69772193 664655708 63172747 282360846 251618203 825725009 788696643 498017422 75843454 378441524 153231007 115000243 242406805 64033955 939999196 391637566 942012720 112653641 901834931 949151268 577186531 964159816 240156414 209537554 731107684 846315529 957806274 15226478 223628982 595547673 593882159 585857360 688856323 116208846 629001722 367279392 758847750 757390486 350247021 485207895 784194662 603445192 545606437 207771129 769951587 662429084 48999905 770459024 608232599 535627034 46265032 2871464 506037222 448887325 398020889 335200101 856177929 299352096 834546029 65245951 65392582 569780149 493557674 790147464 100803364 409913253 149066896 961696855 564946949 573541601 30134964 392802595 43320657 9396496 714028763 654134610 977583795 259292509 102204236 16904868 334172303 583597040 319756989 957932739 307226002 400488842 157072774 378320497 188637442 864962111 564907369 555475648 815140443 767430099 711836392 62797339 105024198 483026969 843284922 632588333 283190836 801931355 753058029 523347304 240908451 983823990 555199479 570468730 644905352 500962727 705346701 370601498 149691183 375077665 677511410 987289189 715959908 978122253 187621067 902001411 534243494 854436960 199781108 353633993 923031635 170496642 165253569 873896518 592349424 966536048 393330102 770689176 647460675 784668472 930332871 431957158 919441114 915930886 383417733 705154459 677427936 577036606 927449322 874681295 470252159 833314775 952875671 622715060 599689337 202366463 200902851 232301131 353422207 521206801 108445851 561431928 602969620 875622971 565668303 531821025 154734659 65040827 722539432 12814196 729912673 932566460 947479165 625082051 125305679 599675316 287007045 988388813 247710795 732823174 707980243 645019386 662528692 578249324 139184649 752410861 884509211 421518630 300196391 547987989 560446015 662937213 602689386 506295503 603225956 923476048 835600229 719799825 318461452 478917698 656666992 23376220 453300550 264161938 340124027 257708363 515190684 393521140 367335697 209514491 526288156 299192338 820701823 580709984 838490472 301695204 530715248 29405399 187363592 510295652 135736487 297941168 519197034 447575323 374215473 496123314 856636568 953091356 174588044 248568784 491056547 373035209 947416331 897968649 296648918 419394779 607824267 610707400 688429570 865029209 2412688 71259262 767198218 869455495 894110134 227261729 170874791 203525798 347862313 775344712 839848116 577901997 32413656 370809433 246189737 327367114 17692585 511586644 216238000 755092599 969393869 656320265 803213780 360884065 487965038 888997392 17326997 659396696 988037641 480378370 245488050 449618491 751494552 860955226 493961195 502253967 147090271 39045451 441370997 32683268 581411058 880210315 277590055 409543830 64679759 299416580 243589907 297010590 168508493 499419580 82049783 649501487 336843997 753106007 733162355 303848737 277731638 276530846 64369650 167593861 595183215 843041561 501458098 622705540 312140926 112464181 385850137 631129221 473668193 971770463 465235836 577919319 124388558 354219443 429702047 463476613 572241947 472694234 873537746 61222500 505372584 282701647 440050357 872611616 212579423 163776965 56102760 680800237 19993657 709588256 268555994 78146331 157291851 342812503 398360736 116417150 195826806 757108031 324108495 403626836 484735304 744470083 945231698 804617979 512775380 337626920 544891234 567466102 69696931 871997360 874256439 96830442 884604139 808579517 821768134 607418735 925529021 708880882 628839287 270968946 70675106 41235229 85247443 148703306 258156625 777315695 747394271 276013662 976870094 930640210 823948580 701137925 77970958 197936458 979022685 229196370 803897713 798708508 67486954 856114555 751937267 503648117 673262615 591159063 562521415 211705351 943096128 406312272 344853125 476206746 483274156 868819798 730719690 738698912 816693048 452525544 824280816 456865717 640793203 957258607 785812758 626109024 786015915 149675316 516841592 177014363 200573721 792643609 945648637 976532617 486792789 584252732 678335003 780946755 495870014 660324910 17083092 866134152 391590962 77373082 455656467 135582738 812134290 953335680 183952318 839628301 835633834 673726796 791530776 184667170 231086041 206320001 289790537 694570794 372978417 622359145 719832162 54491715 98093481 742298030 603673751 40071108 176355567 783260770 353461275 470443176 45402879 937285997 157019696 566939229 289245090 850229319 354832910 383990284 822603948 965870708 956018037 305687997 926566031 523015449 948031488 72401530 833165589 241996918 126422033 366062194 144310765 401733496 235769621 983699924 762206808 761399354 227460673 38980368 690682351 61610232 696066350 370323804 573337012 850190650 566424094 274665438 547267521 139820321 882518057 370445997 464748975 337249294 156808077 892705135 396255806 559058141 455140597 218598787 261261179 953573421 217123237 184597573 25961263 498252254 669230862 415773173 138277882 475346413 32265855 320513263 684865442 724538285 323574016 540407088 367062941 310786534 196557025 100233278 852612687 745411506 973635645 502098322 973237136 401855704 187129679 380264670 385653728 496327125 725715354 376200040 609327596 999342247 660323392 540358117 203315908 649285764 268582839 567534220 694144745 726773721 752897060 835776737 301688453 58990182 260911092 215891483 721723279 991116645 519053453 520615659 829727968 790890672 145652055 131678619 796068804 917332781 410349543 95399308 80545164 470458043 743593823 532042099 495909893 894109199 333997603 675024900 385442020 614327465 820665000 65359396 250730076 693801840 115204367 288265629 942591419 994773991 665607249 152643545 831584588 901966794 581574433 451370674 604585933 924175544 684790583 194828007 472536215 286080276 364162097 814187599 586257104 998200000 669035264 939646196 319949249 283453227 524101600 412946581 236724694 95785860 983616257 425802069 855586423 90516125 913711708 565027068 301053809 43260608 577495349 618612183 973327677 932268059 639735054 310196307 196159462 36432077 806289419 155516627 860875860 664976677 140451074 91885027 131366185 437637013 248376424 367720409 666941126 920442712 1464203 75926470 716402857 894206820 555269831 484755041 22205066 668379868 442950719 694157785 84351577 792567963 108020249 881884985 490600469 211476458 144835325 546812189 624010815 722277671 472823941 827347683 373574505 382991779 855411867 863523168 537670013 325748291 944348190 190847423 432727884 198777326 66148162 800664970 217900280 473383425 650530236 896418068 390168873 80514606 46443417 46747407 40745019 276984221 41389193 747913092 56734649 901625445 660381638 281659419 276534062 44560435 846580138 139301812 277139053 690286519 148960490 292816938 416506585 576025509 22326620 564953985 189136652 459311547 1255529 917238246 722285175 427935373 703105693 563912321 953761326 309429271 705870916 528060230 31985161 21448178 190776681 338987790 628987904 533206532 826495200 740315108 607413953 417327827 146952923 238281798 923706219 657757467 279841480 88214397 242629308 920480787 206446814 524163807 140571731 903539123 356461251 565784639 147911056 378545638 846369649 170241272 730798562 267120223 217700607 854368594 888526224 541870377 286454420 866674242 890596199 845259176 194339984 560562917 981194556 379891078 532302098 737910799 326176534 646335124 36166215 87751186 749071779 700860206 815790798 622109077 859269807 792900276 87315423 675095083 46010081 751929752 764661497 899702786 19645615 723833426 947109232 474366888 172460756 724270381 501354966 107793171 226690650 759329302 419940599 38312176 892588174 41998070 670927115 275733135 922525074 755379394 398725397 965879443 213442250 78466636 45216138 710505961 221654686 201336400 138808887 859381190 67204818 604970873 904008978 241471669 803481722 632516366 616474290 475335071 387816659 518962571 552330285 141183599 90340383 88764422 173998627 151142677 7194907 85181497 474056766 562341678 783405794 806326682 461220825 670137588 31023805 224997365 535419603 718174863 716252639 614690221 18202227 583203639 850560622 900151510 793874526 121205996 223678377 842292423 426166993 138188463 735858280 571312467 28116797 890641079 819134689 22240613 493593430 910005389 472169560 578446954 988761521 467596504 566592359 377749511 693319389 392444795 568203869 365706899 248571859 770912753 694102341 487669418 781493299 199025459 177644467 845887098 84646922 193055927 560535064 943829130 461205683 699021013 467859174 192947433 262181866 831429721 652273434 184789718 534808124 737668442 115497331 601401303 914549228 698164183 294492749 464459991 342079645 143899795 562136581 585406362 18699012 662849653 988240691 290329588 258719358 320487803 982357280 195819110 834623671 836436143 852578563 421303833 545300742 115000003 562956389 977619624 4306852 580859307 326458035 422441746 886102044 59755748 150148075 829636517 366511947 230614682 688294428 876838994 457171339 558844321 871714065 406603055 201616709 925045051 69384314 375836677 842947525 549411931 742689907 584307344 951945363 468591240 143774418 210554932 441306481 267300558 727769461 758363670 818106093 494081518 817796821 3189564 912047023 721004234 946888381 418654166 148241626 332382547 628475758 778967579 562180875 31135271 883006183 65773588 234358610 583206535 859962217 923912701 613732489 546683946 348704641 447834608 691078819 441935730 946686887 427683617 120528535 948251373 967520013 196788728 546217797 249166931 230991141 852615313 338726521 546526412 911594837 254144300 992460540 556996791 239736581 863993258 894617951 874444150 175357173 877821391 146358074 646926195 465993741 67300795 843138223 204134809 290725684 872308569 968940794 251952974 998917833 255317344 926426252 339430112 526367009 616227595 871271409 876198101 69169432 863580534 192204540 196449988 125938230 491022903 565026496 489036591 825284610 333247425 407914211 802443178 78892591 239249405 698226841 135653739 315727242 367906918 415014100 894191830 272535690 153477417 998406042 186158690 417302431 304904432 967930380 892149007 796022992 440246124 608838067 237773288 308878623 964550015 382334625 534467872 486499048 903946435 209905539 518534046 816301115 612374665 389280699 543936241 601515062 230411738 317823375 211967283 487998283 775321015 857721824 910841862 718752528 504086035 602790612 548739263 622780920 577684688 724485504 904330443 931671186 610310853 76571118 813197119 733361242 670833049 722258456 14349716 910780914 750377168 968899732 890180828 304311378 104060624 937061378 215315706 33376939 809920663 658616031 490605477 152137052 79412167 349464033 293738001 113199058 345234796 470095775 115652254 240045840 233302260 448372843 564845462 321042034 293235978 500003176 550377895 149831263 93165471 31143802 504424111 589671216 455065504 510712475 114316301 246291319 913528552 100654820 614340717 167172581 869560206 664442367 661317596 769030806 170334473 307715238 102325057 384140535 40607433 164023435 274757703 709062940 840550496 731187310 864546855 659311902 424525537 291436968 654058998 469591358 806297440 854738446 754190161 575815646 409137993 508995897 998323906 29557236 981495143 628963303 872881205 894014444 927433078 705922471 537541069 525175365 785410526 595303778 120499054 885722241 706865502 817500312 716540066 429308800 218306967 343897834 539854244 929965477 522553613 518721352 153485439 177907558 998598322 231923940 79422921 931746607 915308756 943348698 110577112 319782011 377261908 566565798 320120336 362439926 685355795 235236944 217236308 689694697 475900755 448077731 935253952 231268168 479617075 621766510 863769132 675665735 574874303 705763683 8566406 55562246 186254987 489250009 650251345 316567918 629053982 859102196 678804488 247091195 743870139 262963600 587660545 669950218 478843660 922090147 446259788 804158168 600317188 567684147 180814855 335957024 906686201 373169881 870771866 709103708 378352668 149380326 810235240 328422002 603680893 710945502 568060514 470668823 479228191 170591643 155771574 121904527 527997138 539319769 374694177 463149779 504946231 61762721 433458493 285872806 801192381 703668262 80609190 294644884 120145543 421440617 591058047 336609785 171593926 314448115 825163853 239286409 697934897 778735792 989300370 785678516 196160284 8324388 613605208 518981656 681791462 359073696 939034201 257219579 180599848 936460695 987936063 592906496 697848178 318183869 269094392 458219947 84112186 812198933 817771901 723282081 373891172 826918357 338001659 405418666 200797528 814273374 858446516 458437729 527676765 882922987 303741392 313645418 527341882 780877760 71840662 783264008 444947426 566092987 448205819 648030625 464086725 396213039 306891336 723344681 871499625 244586412 102702832 933641459 177547446 269527181 101644563 720109758 796078323 949568814 275979007 323104829 164033266 823109143 420201498 677362945 500980177 878831247 353031708 854130142 258465647 650423244 386639001 690073963 917156587 864202280 53830083 482535498 625642495 804234845 687994851 886832533 797083619 505862292 250518213 723265123 710721500 324537179 117180397 654615180 6454756 722239133 602913969 861358587 720935943 822523764 493413951 361361274 389817593 402085652 372738931 560849927 837940765 151113628 354367836 91092367 361399312 872129688 513401450 151958602 58998908 56797236 415448662 873177989 835525743 597526257 871500284 601596130 278897236 600749907 573744129 316479258 521027707 879475230 270584315 377973711 880453994 471049638 800664236 527593888 866809345 408088423 896339531 615665155 200732554 421019856 742918911 476059936 998112564 70773968 802315806 640820244 796413309 617094773 798023871 834076668 309176240 572086155 883067358 42737588 986538640 588838104 623003036 129617264 421084998 974129138 291090348 294383509 659000150 192239600 620608685 740488223 101212933 72847041 705599233 779632291 965121485 947230237 411183138 98757283 526299070 216000917 564238968 3599019 580727893 578848942 370624350 460025910 268454924 466524849 642002862 461125505 829153872 614120097 81188042 248554017 444351487 632334440 544815402 106813859 139031935 498530612 69349461 188930419 120508516 972555071 294286835 751732518 345159231 59275171 845563119 946179445 578165366 236289618 201891940 485715776 457181786 14603496 227469766 523413129 161176650 192176883 163785194 576727375 166288887 226469949 774634182 99745110 385707761 113173324 237414130 939378858 541214327 243596901 495299602 237816858 534782942 644274448 995551839 213670476 29876037 807986704 149999955 753761471 550338807 235724668 737683941 702754853 215275531 842022751 303566411 435475146 782946708 304042922 893160267 272124755 563069101 249078124 880549243 546332162 93543121 813958700 574748502 422087029 202845158 553207423 999005606 314651553 438983518 984840400 960943083 811670553 442163635 470123297 52428429 825509214 876922930 823433279 109578257 799100281 443511759 115715858 411063428 382507163 49597127 877675573 813669241 565326238 546171234 828788261 779442267 745911459 627565444 891250526 769832203 512814194 19252863 237635840 697131006 655810645 875957833 539733297 16744941 521486849 624062030 74289549 468591372 365510599 711276602 455837652 678139150 114544415 372802143 757074021 47176357 205723903 872884971 517655780 552952216 713402905 854025986 748282392 996191666 790547634 375617086 638053442 547220242 122510857 419389076 585127102 995775653 380534298 695823852 730865905 180670245 257493011 97854732 596512032 194981861 602878107 424970312 465777296 936378241 892326512 237154324 311150355 269880587 702623054 734427668 164741632 869372449 886449355 133571701 668478609 352798170 217351211 472394275 59825295 972665815 696334091 800059579 417303368 871606902 741494281 162531584 362766343 204887833 372557576 359767079 378470509 241969724 263949987 165190835 860307266 397539126 958969765 649978367 29506552 675957586 546904262 683510658 314233976 19548001 117763819 921032617 987684936 349395564 97806616 243932959 383115588 566973280 513981999 363290610 367163143 278887369 750869016 48271288 838833322 427149310 199045273 852710260 511295177 177063234 492765137 613931560 758657958 978114306 938525611 900471168 983754223 394827405 936999379 433977620 141086711 491148230 524291853 514858272 744757598 120292967 550738825 939672726 177938758 869183000 27127850 260748544 100130303 492557529 774492592 806785237 494320632 881513356 831429988 398871055 676112755 682683027 886729574 467822207 140423090 434784895 123706439 879426935 756725171 570883276 153806422 394135478 358777725 229526003 456637982 389468375 897287391 798254575 336941139 227383852 907644549 807930422 807713172 836014589 710392165 581437556 41046099 343404048 73696377 643230187 358285725 551647878 212883741 714509715 117579125 339994304 80597852 726865555 492165856 425786460 586555024 995726241 14623718 267159405 942658498 282518030 535738843 74234098 485246445 610317042 270372443 515864257 614624906 395375705 408645672 428770585 883567998 329092283 667086128 712918724 711074611 994459163 639274816 664855555 969977818 142132905 942691632 886290904 973751648 793150512 997397401 232415935 785927630 491491055 409869593 396329851 350841820 82874246 827154338 424452729 660006612 945775667 615494502 126894141 872211746 751317676 730479175 863248544 185267617 604437186 355668164 89976966 184751454 246175472 121795165 288228864 441173118 153505651 637110382 370230297 172531585 182208809 509205612 44260392 483796151 301928921 491248472 611553386 768028945 341174609 303699307 416754177 546783444 565797530 89802037 646027424 351715958 900901929 26417984 341273627 574863569 860152576 547486686 597909495 472349934 120123619 978283129 436847099 362470037 449313753 960436171 993608226 544935400 503416969 625267105 195543198 740662305 556921899 522891814 170715784 896353843 64485999 967678406 923078581 485456312 652738558 909022328 266093286 35162800 803663939 736251325 511097699 739946634 238173580 412025635 536581454 963844956 186067127 680434888 665119766 474765701 514715532 594173748 803456521 390154012 50613023 223035503 220581686 195514093 432164326 19212176 150510346 634789068 120526488 617584361 937738606 485300811 248703837 411969130 128795811 889349206 595481448 108470829 320346824 142301529 746519187 289581427 868896511 977257326 48181984 545546143 226506697 998701781 342635632 551484588 147058071 860221084 659492330 178663021 590912569 416897495 712800101 299776056 771292588 581974564 915821427 793829430 4482619 766506289 475557828 931073669 837283982 701988229 371025 873261192 910513456 565872246 255753688 436085230 647837993 664389127 173680220 705044351 77910194 381796696 43176722 347417086 279676425 920277151 509446307 739743041 930960577 341034977 931419685 529434435 803732888 456394805 729118442 635281738 713074730 518330082 346789789 161108079 298571483 856530407 957438464 497614227 732382317 388477681 505640882 476198191 679167127 6891298 254277783 840183998 118705943 234867240 872103947 850311420 160477060 424070318 236841160 857579736 803045856 579117667 31019740 132692134 327317651 160852450 419228284 462379349 105523005 603291972 432456000 14849664 667880361 328805057 853498165 122267849 609032399 614683638 357909338 128983266 998081623 202367502 641013227 13391561 366814030 386334201 311268989 175129257 544041540 666004401 124124249 388738072 705815955 299244563 903497674 582853542 87506078 895262873 362524319 378395366 432666473 559015778 218454161 243819711 464868364 712958404 498275214 74875553 469816070 124594650 105845208 539801646 1682963 569142986 25636773 81694205 586134605 438136499 488098298 229325281 731359314 516657757 399275705 964455715 240379596 290347537 688269141 926382277 35843357 166147132 115145952 982430336 184145464 371135667 506115616 133655326 222158563 53938885 597797274 993774272 751677428 961378499 580880386 844050868 403615380 16544997 14237147 656212546 216582650 945940162 404517014 414354293 97609000 218964856 211254450 276471026 829294958 156630533 28703464 133689930 592913712 642135052 483916446 826521323 973356881 150720719 764389290 694891019 65469792 675593659 926975149 864596403 481882851 932218813 287110050 892655531 786819485 763768224 936505158 781081189 969197238 25550475 319904987 453713015 497219437 292923147 497700673 697644897 432342412 360618963 260706296 628336421 736395261 134606968 782184432 807198246 369489668 290160312 947975568 909389318 17515362 828777238 798516733 162607479 453130999 648728740 349236941 36759812 818325230 244841137 961068734 771061968 517866301 352195196 189164270 304818314 839720894 206392148 743760502 540417693 413050029 89102571 884435496 249811895 722906058 433785607 353195370 901911208 419430847 3371796 56099454 199317505 899284354 963164632 82752223 819495301 446191820 452484012 654215069 98010963 416484870 17984555 569225494 359080253 25357954 69793530 868709460 212182646 387691673 352011379 618415897 369755824 81463515 540910785 405434609 895794608 737013255 27871482 149241207 150507859 899559154 257378944 144905927 741379436 637757705 895416194 167604392 675375545 183051591 16213108 914840659 827436760 755388904 569780017 493589891 911150661 735700475 621088847 258670435 136736139 870617195 2755412 729582469 878133102 198180615 155775620 947031452 850676668 348864971 54520410 420476661 345286133 788719454 865998704 509570582 285743102 768428248 483777903 97076426 161466052 784150436 954225430 372754942 87958201 377363310 386562443 186531998 9764760 122826381 568004570 505390980 200545996 549111627 634921219 374482836 412729354 393291657 655998056 671840179 600415526 689912668 623991331 478555321 938719774 406784077 135337308 878711119 635191871 331780401 68201036 469767523 675423348 253052753 591759908 526860022 879881601 662163548 703999984 443802617 656990777 772719332 487051003 610508242 62978618 62504111 281470768 207241420 546934358 7467589 829366128 583002031 435334320 641783959 544821734 177171466 956955212 760008340 971362103 655194818 459007307 517239222 21327391 987497337 57113503 979652455 250014198 554606664 671765949 564578807 562532474 279626000 316599366 439783320 370126338 22947768 533113439 390193051 754148077 290566813 776914775 406104180 272972762 655904578 236342694 536008952 396801065 94185737 24727206 260843872 59260771 17208793 794241038 905319407 711489114 105043925 193843754 296047196 480491770 28828621 941273376 88518338 17455053 275479736 314679499 151860301 543055351 824652234 516676176 953225671 39049770 338857901 731926749 765771331 513938036 881173583 833680710 731390060 464980651 641663774 885268035 404100580 595025637 732953489 80553645 874852447 949931048 906923709 13698335 966297006 463416375 811046296 672899722 515166257 334058932 77565129 538349474 476424127 114585691 671429291 352588680 845034471 784791944 283671736 99846366 913648268 747357769 796578254 197115246 823361806 729760413 930371519 549046122 978189567 144198843 800517852 984705284 543176823 417031269 165623941 410308403 972415075 32244458 529048207 598231285 196076152 630266939 28021112 445501151 422996391 488378965 320603848 718411458 145644938 865201716 164859453 244646023 125766365 546326960 542475675 806148663 170544772 901364585 226763392 208732416 349680705 817401331 414224411 734463329 750662378 353867973 120408484 549141601 800333072 871114996 868439752 546583960 449797933 408138888 111992039 659743683 196626625 773872347 162009473 428696602 301044660 240614951 767577773 926209400 704269603 549965287 497069788 54944216 647843523 908136198 882487023 279092472 571739662 189545053 503165470 213411238 903178403 879900527 225592014 60648230 337427032 466263565 606469063 409474110 445830284 497751633 660586540 786370623 535554405 957072221 172060143 250124619 311018781 748300586 665081725 536047029 917126742 620161115 225714759 341980213 351597029 753501091 431232486 336103667 126682653 652210556 960447180 889152138 330583354 735697452 170254078 664158692 153839993 298247874 783942869 867027032 614322582 893374874 13928190 491504734 823855389 213860171 328973229 949383195 960199166 334211791 657270122 579246711 550521388 767936830 788809396 771914736 59864922 207401104 440138957 390411474 968750422 673922059 198197394 454080658 369394534 854748362 136796033 20252121 466842421 915047299 365673569 617711032 948030066 147958709 693067218 423535483 961010400 389139269 436908880 319959582 186116245 308788129 897007545 445086232 775950951 62038911 661599926 924342312 963649479 96245708 369408809 280531487 926173120 309630771 308600876 58937129 775994774 328238373 161051408 919644513 754066971 655946116 528274438 93775530 974991038 579723770 326452941 885119071 735719614 564834283 408242662 303048437 57618807 568438713 436668520 404969515 802820896 679286177 851121364 887539852 638694293 197812335 41016128 253204850 272169386 170123081 573199084 439483700 384827338 189568080 896979051 218320742 470965535 806465915 534268057 705494953 869995975 237985806 891209582 396608618 731871564 352590336 146557528 265723818 596706549 911890562 802029628 437751134 692632250 115564427 789943659 72389607 94832285 29106737 396124493 960692981 756926662 181872260 430282308 171937566 769823332 760566046 545808963 403543043 292625653 91283162 684564030 991677696 405843008 452415947 521863230 365177129 20420325 692214949 758075537 626463799 111893593 172225709 415211423 910583015 687708845 547059933 772697772 189212105 800166978 471525694 77110433 942173966 517625294 394048130 651915630 337169377 393353141 949428942 486600545 874835483 23926224 330515722 643156800 975909597 525463061 127845070 941618732 695053577 956121999 298350389 970412291 442755686 445891811 557837540 286858620 492680665 999249824 695964946 52868656 230176176 428361032 331049890 229881734 693952864 997419661 340505390 181373072 919686631 852653665 51901200 644988195 119548566 682595336 656928735 258082096 541420984 273467566 305348835 32455926 895493856 535229228 550243080 255909146 246192350 140545842 634204644 765303025 74586787 718843137 426060357 871568884 100046492 593903735 590322532 78810332 341808753 27919755 500439007 724310193 491380274 826212704 315601093 105278109 902588591 178362072 439183947 420486651 185982123 889275481 745141440 23272536 884553077 289139058 226395082 807804939 755645662 561753975 625838964 400304931 132943333 86949246 617547100 483334811 512061842 782378848 800106670 566434411 488280462 114168304 977777712 374772307 981767998 14874973 864337818 848884627 26331868 148600544 496091743 700893110 119715111 188599149 131240100 799935110 906889777 30717559 985494953 237965070 58816297 499001644 456382163 696285038 910819653 113300754 997688999 955139672 628850571 339870422 10904805 194785564 808487143 650306901 909950149 173692893 474148759 91511685 47444171 601424560 346116981 416308392 374168155 853663790 726840943 400416399 54415343 613847053 736573710 837704803 879931092 666472874 757923046 326107873 110247907 414494211 964862744 600187882 217442401 992966008 101516425 106419879 1113396 84787064 750178089 675323077 153952351 796985206 98101254 598916464 553185326 574445288 49608854 226255530 983457003 417412154 490084317 66085202 208464389 200894361 975379959 889276979 343737105 462329874 333840096 375705346 441847715 447957924 521047676 608042983 666178608 16255128 283835624 1564521 365755401 771920911 869226334 226052266 133035784 226643773 574093459 800243832 330688994 794479668 968583079 993591798 131529757 656760916 322218104 422017580 618757815 757166186 295329800 916528161 569150960 561385461 229750562 532569210 333880162 371499389 58416556 854517263 996517682 142634020 792874652 588278542 768364581 510222575 701564181 10089246 530493470 552032986 869195935 436420467 319999937 887611486 814999252 217487729 665415643 371141080 229817399 355680576 764070035 167410430 433095049 373362629 905448520 356740705 247873079 456883207 122830667 491305441 608491848 416122671 647503061 83394079 881466572 226749885 175997960 292777875 572218485 264475883 754030518 928776065 662424013 714098983 631309198 808039631 737864479 673577469 897045555 489413148 264612136 456191820 145824775 907691725 838252309 781954677 522579962 330190228 912266669 199167637 864650404 2402257 157094809 945540791 394151949 304739159 326073464 183334191 480740779 96713852 353444875 645968687 345614807 343456251 361368579 26512374 710379382 705290824 80201758 416217917 934430252 6251966 547611258 248681470 404883461 493404680 105108061 492776965 557704326 711821614 16736279 586446468 322895259 369190142 406092618 148995860 686417400 654022189 638884766 978335931 75791664 944284510 152626430 367602423 413336942 875903732 384059316 925177832 922393943 212809021 420954628 245864922 488317730 271737019 113908505 157152298 204964298 317306073 531081805 177396623 40518940 1249158 953437424 77664159 446600448 424095046 461583055 764096237 605804545 384550535 34531895 361537760 575929407 987589511 833097100 876910892 347956723 817102130 585808069 646904490 654008562 473687147 840557719 936970576 389244021 488403641 943594437 518856396 181753242 755945410 513702631 585120759 292337929 73239058 431143 22811570 926104245 333071005 659519332 170276520 529872695 516613229 601855896 651874297 202134374 869336703 399691917 251599644 323036793 41934032 102035337 165174334 61659916 44211570 12016753 20285191 946196461 549007546 70400658 850343376 254011081 468069874 726901841 538980225 34202367 508706508 962053887 789896935 696928010 847689178 320352454 972427292 497629983 19341380 728609141 750315056 925226757 115584702 422216452 921883202 239562682 868396688 119449547 84698734 910220013 852273864 339170871 709296920 407415650 39262109 688703904 102257477 920770958 970021359 535184041 834697731 741182861 723503853 780861768 1315455 709571500 754944156 399973923 626203218 178825330 999014934 958211043 23341780 787846627 577086979 14738809 797320338 49829718 511940941 101186668 313049366 170813686 212855256 615847429 41675286 371154652 878757896 200817915 709723823 846042020 144495028 848669176 130673565 559838900 447244471 113157596 152635655 334126321 44713099 758549065 160734520 72624130 564285973 325979229 76519347 89117115 299755881 400985672 597815476 198111955 521905477 660178096 140514302 79313607 665578082 356993739 44931581 757681188 626692671 127514416 848855492 784438141 915615193 206596888 434293634 23962340 865596828 222018416 708396697 182591586 617756551 979114846 148247416 882374159 678898883 319978732 303424520 566442376 137176305 452728545 747770923 864735639 705267848 551332947 290105849 794939789 604261931 827801770 713179023 916342560 849091979 484008063 322766927 699591194 262100963 370707219 676334574 200574557 867906423 541231978 580285003 94594717 28354680 196685471 322232364 543053252 106310846 760513202 267925111 493316778 27496942 64152411 742674900 387580568 756406702 975826857 902117579 800398563 668901755 886459075 963974527 963771132 26861599 906193499 801246182 711327556 816100771 884030462 534393459 620878751 454705496 805255209 868854358 620961860 666836718 47358877 739015688 622936932 139791769 363854313 511781514 686517937 213333483 904114306 241313223 23397268 391374204 626118238 244985137 478373126 927122918 211923 933136480 357570113 510178805 222205383 451785193 430957096 201482472 178342392 526750807 740571156 814232536 153202361 29346902 131939518 254990393 276111961 133057904 753806819 617270266 846473680 745416825 614116075 343132884 224728897 625175797 663239675 188643607 879342706 77644646 37914314 260024202 486345020 662077928 515358296 538148232 674423592 183167087 496079798 928639297 786266762 62573319 187677786 524407536 87572087 814779353 486216569 668971235 879175672 234349939 705375966 725787464 901842968 393092730 822851636 558206073 606728468 313103592 565221343 735330140 620107264 194834172 166196612 915809917 663883601 333664290 593342434 143170496 964307919 997670109 803814700 823739203 722102961 496645267 908988108 698372758 144533932 191022075 838911961 179304242 391844056 448047309 343889742 109133865 378636904 628989381 90010795 831242359 349429437 211569372 488514292 1831194 422511892 75619366 779446517 44751342 705302356 310549273 200553764 457062824 420260397 964043807 830260048 240871485 569696730 809022793 386594452 801346387 310249182 431092254 676106140 28181443 102797372 389104147 663566601 211839315 591204520 627391087 969814313 345841597 726388598 23711235 68786030 376335966 62407442 407674483 364274571 137334210 93450162 427347393 339564180 678332697 847181409 308144913 673254973 117937690 177302747 905126471 155017349 966069874 253894661 720708571 398838699 335389859 817608290 106850775 959034517 871658691 303893486 128747361 350123005 722384522 978767786 268456459 114429432 759572337 272845021 421007206 597367519 655177919 569329471 150200880 502746848 662943551 246267587 983078952 419318400 802794593 481896059 536268290 542578531 181389029 550906829 438989655 710463201 423550475 867807838 967966785 53212735 209537079 537934907 301467672 311670760 263183680 539062312 917705105 559613000 774897539 986498252 617483578 289343159 812195267 922388273 143190199 37219398 123008882 354299519 933708680 417238530 900593210 543408146 806927691 810580057 170219695 48905182 175129796 787705988 238116152 500184362 806127711 272113818 499768017 557871770 881890200 797547812 546852783 681492690 599425311 296593228 729740792 955247083 159224750 947436303 893331192 156557943 851331358 193390335 89996774 904669364 100182863 43612037 946152591 872765413 902278160 119958611 857646361 158260798 733223898 797438100 160660354 901576312 38285206 410876425 123032336 634400073 310650410 971723284 180746140 482958740 26718125 253458201 427255160 107694853 236159569 919432543 785804271 789862147 178754512 20419658 382143988 594650364 153601215 153503898 248187780 952586675 991795296 718680133 973458451 419697119 257138455 340271456 636893111 517506778 691868192 719709599 695131033 295262177 651119000 879793232 950182947 121014314 594747165 219716180 946423301 362766664 673831831 489692045 364703386 702175659 929362767 802772962 474218385 7895955 7966591 959957514 504614023 808349581 758670185 75090888 363657776 661455874 675797150 406547841 244035560 900116844 557108730 647790659 327863226 859012076 275231873 471889338 974139418 185351999 395187987 386430589 832889717 387206536 260781851 611762221 393334977 472072378 567381161 108496935 952590687 953264869 547497271 990750208 496308128 624318118 378503674 517157557 402118881 51292895 89164578 281138196 473835349 123785108 3572727 263970861 288356889 338056496 838935106 186692635 950961071 418340451 597902292 516529854 661751926 478066150 184313135 613184056 22593215 148797883 84521209 35298921 80034245 827236027 253293701 209510162 3934182 927402067 532727225 17904141 736148978 700755661 891246306 666219660 22209104 983415648 706772800 308354599 223891151 401750469 26708834 920251105 901836850 721208139 179179897 729522313 674734786 669606283 270282911 201058394 697904096 684513461 935356906 657622387 419106625 560819303 592672415 892815751 494557381 820273799 546565414 290635287 565306144 266379610 491639180 706263363 114863197 324494504 344854927 773548601 425380114 112511482 645486883 324559207 383486674 625755654 103237632 921578642 972046310 877616841 83620932 104147008 146930925 531848904 251802396 266066336 449732881 444041528 274706034 6416452 233386627 682395736 193598046 527920220 38229754 141077573 511690432 847859211 441563599 465690593 76693290 339844516 674023641 523313226 621540627 709068613 561594903 658450657 614428579 935985867 305531158 215080490 469394759 736554034 664113624 279291616 936815031 791191238 534333159 386389909 987554900 381276133 122188703 20654631 299280965 533818258 862430095 801272161 778302233 620088779 447488439 485891944 636048100 335202294 870633726 371364304 575840003 474294400 56906091 635230481 968139585 548494145 139830320 2682146 657985350 521547819 839544702 491382836 144938343 176394711 395581897 646645113 621610049 370735574 934852181 121485466 366279276 201808875 153384697 464983511 735544968 483103176 697833922 970278295 43523688 828089791 730192466 43548399 712541187 959482463 930258270 319662580 440341811 992251675 76509861 279634666 226012649 353539135 576866474 575567921 451835018 534310681 830629624 54849667 891402210 735222988 720131769 366007951 198852350 228562887 589271201 669592268 641011376 98161876 902265086 449270261 305275545 314770570 501842957 429609074 949130860 6521231 268126295 817092067 245987154 428216975 454588117 813763014 434982451 479595361 538260180 425354599 118935459 918548026 366396357 95751779 807408061 710011097 332842117 918670622 500207644 235996181 844795819 913856759 518504131 695353017 889511165 618056573 390330122 723140845 529232433 7939479 220036234 273699846 133816452 335038217 17039786 422111397 663212514 578999376 338068104 304657982 650320880 761353491 692749151 364097133 177487606 552990227 134087648 452336497 829165597 614412883 945307775 534572018 876793242 662806261 415640765 696056975 623638195 534667194 478924846 720721964 72533367 630008618 990151537 892945036 891450888 125933472 1090296 692232690 877404270 761269128 13750579 994634723 126372423 952205239 58176828 873327349 530405387 76539680 650488729 514232639 483790013 222142562 758966588 430382121 973052940 639948216 652220004 509355312 736887422 816665540 650759092 1964846 453304951 652030501 439307123 693797023 925743330 205018896 833033933 228406946 198168242 448059518 500311932 790913703 409042985 816309204 48614991 796616205 778915026 615298960 658316637 179490835 25353720 695651247 809667036 505412547 32449857 640802987 302368934 879368916 298425014 610898948 714081300 930627541 429869608 596317589 159040291 794753695 744113843 876664555 552975827 179032580 844594181 635249311 932455218 938940725 200826209 781419035 179077725 242783021 336494730 510577231 32592347 331546702 702172249 537164879 113002717 103685782 297336733 277112958 236339263 96981158 373110754 934876068 946353131 945128809 766568070 983264061 793913159 782705368 249896826 737610358 644693052 660682544 73379583 219042884 674650167 93726337 997137086 429108135 583842021 780424182 395188447 317981092 140945857 37286235 763188354 945295667 44123235 617297373 57595388 588391943 151353936 11576074 266363308 757025395 129096869 610504788 81349911 413708691 925590616 117572009 328009358 803538982 950692286 60398720 862162795 378291352 570511014 377676639 938460566 889125407 406301083 924416490 323869828 711942291 26808796 474316482 146642610 385950208 252750101 271664137 940445440 939727862 159778156 34410977 511142201 630372884 339722573 608765468 657406333 443852960 840336615 186736229 485360592 282058604 610252502 734148803 532904582 748033173 737318093 657261507 177833742 223899398 516158167 304589176 722070097 733256163 888123737 716418992 887176279 47917930 772348456 852345470 656018168 140950379 240048666 7803835 390776250 892545738 712167304 580063782 71017410 299282840 792482165 427838213 67266254 343585897 180439180 875568466 480143155 827936030 62591393 388843039 271127195 479154168 924397772 242959985 753076271 939044248 538253684 883003478 960170715 469428361 535024570 232014637 850640032 972587820 648386405 565725313 981385468 254290026 219311979 162833117 665059275 397023267 386454174 32241108 115904980 261423489 186407877 689426377 609461541 695819975 750329274 615592279 347399776 753134077 186779855 675795852 728150142 599202289 129883765 392329865 241033171 154703642 427583674 179429565 368342741 414914760 436326812 704093478 307452428 237172263 820815849 465528882 92137593 826296359 39862840 596626475 267088170 431971323 382706765 589889965 906370223 392306061 248387554 970971101 759687150 825297697 165612799 825164752 623428789 676314870 82041006 638221174 493527377 231856749 71520506 284906432 702777481 819416904 858707508 311693229 781087177 311801744 271527695 598483250 718642022 882745162 555358301 273353621 23809654 868238920 855506555 540758931 247739202 876725219 540215761 81598068 762259592 841405498 252286306 121376577 486174261 873030210 626843966 264081519 632130331 455426896 855005137 495141610 208785797 234202154 301546926 137827766 617597225 7826246 599587627 978275915 886114936 62930297 193075959 248845725 505063375 125070861 592691949 962863543 656637718 197546694 949718422 361677678 754768178 127747289 786891059 223729543 22695979 477227746 999489356 694753879 46229374 977821982 154899700 279235215 915479312 418618376 692217100 498753307 725520417 728072784 369415490 98776584 883294103 594495640 991651246 251655546 455531751 662091371 353158484 749402432 39651945 575827838 315725823 723364102 121961661 396734485 864182263 186702539 382617833 72815218 214414111 129845178 853387200 61908675 694398783 749694160 737277502 289901479 370917178 787841920 193839610 935851924 757979473 705559157 419402996 53624169 362551567 377861193 525279417 23397350 348301957 961442973 579315463 950418667 649617471 488651394 766261806 493287892 58779506 552858749 126577272 558258250 432905173 861090600 666701333 692102470 133240171 559118965 985641637 878760563 412421683 324791425 111239772 672418125 927007669 82369014 556107755 33760078 466686126 613349379 342355592 654210449 990484382 730933921 470395991 463667157 734860172 322862779 357674677 857368540 644627288 876956362 486988125 79626418 814542895 128826728 865356725 501493806 283644797 955075212 517890254 324530710 301536319 816801055 821269623 289753546 263107063 172573687 417144470 487088975 306827065 614024252 791500525 146922666 25574761 649150470 776304459 309753972 406574659 953123483 502647558 711676714 218475532 863987899 810052593 80900637 154849776 700180088 675629899 83489075 114708258 171153343 748343507 745677379 916436306 186867659 179993588 892063920 317903780 601173473 934664330 363542072 242038507 989051166 492068235 591186104 941605158 446784129 911945655 862671115 213742572 331004700 932153214 484979008 995346405 154176000 810586357 874419663 577246396 710397609 109560817 973843196 410112314 52507263 470302943 709817314 954576287 783018610 504503260 129165895 431513640 124921506 916402740 455636792 56556719 144878830 130772241 477671845 16853544 357430737 977674368 37479679 768101060 459460391 536175939 81561903 211824719 718539843 266495879 554740296 396699055 47860554 464298937 631685577 905945282 385328632 841930761 22296015 703297992 523375384 120623331 110240018 399072028 890175743 907366259 194130820 348134422 682503673 500203698 218696926 12992436 310062422 23115178 824164542 316995494 175483309 198195385 601486998 550095032 265154413 371494307 138831569 321992749 712926388 543558356 222863439 642270641 658867807 463780679 159203258 428522001 628315070 186493498 581556940 991221226 580703351 222813241 638288051 648716036 799428470 492011611 510735408 662770180 553673310 908796370 951755574 291087257 941629295 678203796 489765083 587456753 186889012 644652431 968747261 412770264 10985807 815468308 240045092 918864127 456089023 403891087 7847287 896069723 729293174 189318001 266494524 256990110 570828695 259945251 963971645 996584923 33978826 545658690 461288365 801280233 163776614 741117497 222547780 399447428 829813861 715609649 685836653 692511790 478625670 836184316 215958092 251416528 580599933 682787609 877998205 706855123 377684050 477867513 989812252 188887570 642578680 308728843 789223585 49569929 756386932 362641482 806652407 966112832 143999178 701918708 145604922 581079152 945034932 624348235 370670112 371633936 681516059 851985613 71099481 149331617 872524311 990710751 730750310 371748820 975275708 897060125 621723326 730091314 10864928 605839736 867127564 596230722 779831056 517131109 328313395 854524662 695114133 73102395 406739380 66809731 99420762 848678482 67015666 20796699 339732236 203172806 347462067 378760930 521321111 955707536 699243644 238230764 399002063 20114345 406773249 778961389 437684057 469582244 555473158 965454817 785665898 768456626 490745472 506177774 222415203 305984299 429252988 749640274 843290524 642358405 420020335 887922297 855455745 262719772 576505567 630243098 56307847 828759412 208881434 876841277 421205371 231160419 78547525 63309573 485922420 511118499 656620138 465860767 792158903 184826762 177566049 330499751 736814104 296020976 374381402 541440050 16100225 481038720 872487753 214193130 531349485 658146259 165272698 808641500 429262444 945328841 653938175 586902874 352436117 487664113 349987640 640002348 533700517 231543229 823406325 159588697 65054969 315351725 590842870 59717808 289249198 436056014 571926772 528385000 761427574 974328720 65128831 519697359 647486826 916500081 176379402 648920908 655817478 13614607 888777161 461975332 214253047 519383905 521297744 582056040 330815519 75174957 230306841 900277979 113743468 29933915 811314179 55655358 219762912 438380479 94006494 983693654 646497288 205350016 556467011 3657995 827191282 982142730 869135644 301378361 121845907 9485361 727773931 125444256 822844555 588388258 937416945 444341466 13629651 215565828 455339539 17011660 904063340 783051068 806004125 343018142 710751494 986481473 92074528 889425696 900808205 733437568 427223950 552028128 728042751 315969269 735913788 858583315 526109133 835385740 863036079 765519193 922614831 805295081 909239395 388085111 665347263 39901349 951682244 147901480 321879263 641473067 703635768 937030051 353752517 364670946 686429285 636050675 759741552 854507472 629032946 26580498 725612424 594004173 755118883 336107667 574284855 25644053 42587143 379168480 520968998 261970210 49985783 773782244 48275187 822321455 852420985 222095819 891155143 134337866 286527744 220640485 343388877 344443373 811874278 920562845 885012737 652326438 921260002 785872039 98577397 427474409 602524434 42560921 199020868 422994148 454046573 440808034 616922342 133297050 276228424 842362131 616844278 281753040 217582521 858248156 661714367 943390288 56449308 736704838 894505299 448109895 32826913 727984774 831271666 401936885 559945606 382661300 967368527 330939072 110376719 361734552 294172174 984508351 306979954 438540097 334833788 97076739 633066522 500097132 84954756 992780943 238088143 634572019 98194569 152822037 508925038 725968134 558706915 163064039 471951187 713487866 99469093 49923340 795939288 61550560 72531206 897223494 365411098 460741871 698371892 116174571 370319621 510907741 326704505 358098078 866275753 85474236 986996433 480441636 530271912 515168386 155361175 113420634 859466359 90328778 9683392 739034089 420254942 28227650 571223102 659709535 394310780 22772440 673793312 989925893 962411097 456424131 555950200 358385000 531938608 659878131 491848288 677471439 634517689 155330687 781730861 38591141 31677015 842255203 65249174 73768934 75178055 78901363 834947560 306128003 555393930 432008575 366907182 952722242 344183608 514878115 153777957 929133737 718260419 110683222 88046923 62893197 272352934 343015998 933479015 619099968 96903228 755801474 658585259 760193475 880539740 675343102 178684309 506966056 939104781 741409342 514426349 806271921 966408058 221916965 18414003 412611004 420848979 289384796 971026788 571822718 321295437 568603196 920060573 599995966 821529367 353291747 515685236 523963935 295976424 947318903 112661865 748542843 661604361 713876417 206340594 124378413 791620601 575478313 687690464 177147476 73506822 419310330 805301713 139330669 735625650 766702762 986820582 235204370 757837344 978595413 498714979 201925183 535654989 485436365 386903611 166961817 444593344 219974863 959209247 866241432 829971551 112114954 880836400 961024832 296344668 256694088 543250848 96607936 890256343 558158624 24895341 165172612 462935309 302523526 293843245 31997214 358346873 884075849 924002663 808844628 922116829 387753246 293852402 356924033 185952917 202024050 203137728 366209936 412908009 909286159 522820538 766081419 578218798 614638287 765135010 856038236 868533133 352786523 705848691 576885320 887866025 572295096 775411926 860231308 895427085 543371909 942419613 54906189 710865011 368020238 139342618 692023272 963808723 542628533 221461136 714249778 712489504 116735918 784775853 494274031 27270061 642650248 598072266 709854134 451222036 108917207 922536271 414617521 576792486 714524036 348447915 764020087 47309076 517527856 166242365 258111356 650488255 803379175 275563736 152052529 691633117 730892025 357961994 484417219 149472779 220914247 35273416 213371987 216016390 348056927 197066128 304575815 50233919 295118705 223086451 786935170 161671236 690965911 953051212 634309161 150540905 452482031 20801551 775295300 511195441 182590256 918980062 292735820 941941651 63168017 349147861 546331681 733990348 484725168 983428923 87560184 189831539 453544506 529965432 455177794 127109244 512317731 808731722 631911903 113421150 420750495 804887480 64742957 159244836 39188073 718169679 251471497 793238921 830766422 563184748 644578937 700652028 947368105 825995404 316576291 489999110 880948475 996714050 648114260 935739115 176218168 703537359 962892827 905225927 676727694 121563035 410573127 690316333 411928668 474689880 274415115 873537501 544680590 420584342 706736086 402920398 543597676 350861926 997831062 616393932 869908316 53575817 552050118 678928517 434181235 394380093 115039282 483465477 289715297 998081409 698019772 992263373 205248935 16711610 671727296 585219905 35342219 243024031 103776175 217565299 711301196 11976095 882010036 22657457 168035622 771217497 960723960 169398355 638304138 870868817 389619603 409221872 168600443 365324442 421275261 756306032 185783883 976565771 677547818 951833148 89274169 461633536 871158972 231788193 246683852 47030203 126389174 816677345 507182244 989601627 634255141 208944852 889492313 471570781 4591510 946767402 907084769 587814730 356772808 81742989 602783334 220077823 741334911 695167752 452433020 934844533 733044226 741640550 700603875 841604723 6760719 792004642 957573581 319797443 509996813 871311142 913781005 147536547 669710588 207505235 754763489 134152051 327514988 455143515 858703816 826770917 618446958 994622374 920572688 796762223 112312248 998498803 689628013 113609686 426054638 434387087 617942683 862473549 488338923 838737449 459674960 449573493 612320133 664065924 904710283 200980286 633770526 893494011 536664726 86793458 532413518 501065377 816200841 813657338 287255995 59933175 103004623 855771777 489110903 2731062 450105297 677277422 480345814 37277837 144161900 279747922 245388421 917142816 386870512 476129616 404656019 881888277 565441360 540756743 494669116 33468485 923859603 147697550 59645243 58127161 325021979 394239801 408146667 241521165 21942110 988833400 470382317 71454452 770390593 360267865 95751603 131879208 187040183 495812733 332207575 498065391 74278984 942678164 900506631 567008400 353648642 197796578 693494863 236003920 471047172 613052296 348759398 656181929 652550204 448359364 323338402 152636701 666372784 345635420 218483142 818659008 239736411 784911800 653914322 66783113 853199572 305716023 863542456 601128298 681396174 713133875 98876280 235185430 329836858 211079431 54790403 422940562 991793293 211066239 229079127 748038956 578139035 438080251 673103307 20200367 41543515 793536715 804514530 18973073 684035607 166270572 129261258 796664500 928038020 725769978 182623699 435288049 353446863 427312523 925332070 568468120 119465887 688856709 440588867 947163129 453931684 565566818 500442599 42936546 242201690 141177978 971547480 115557265 931811532 31878883 854869486 585178338 515430698 196284969 966287205 337448045 396628934 266116600 795382764 472767384 93709799 213205222 683684924 488887728 397947858 218654314 420624626 589079517 401715916 702327204 57039099 55864119 853896267 748257353 268122458 476091361 287372635 848542694 40870029 529986075 691310409 706478843 171632198 825382176 39838201 739935094 164965272 217891816 153867110 621283905 542490230 25553756 999480820 726555967 566296510 390308554 707068329 154308087 797750078 99585634 127722424 783527226 18617309 219603790 125920604 449326203 220135991 978615258 58505678 476476013 302242841 750617822 599309172 926273262 498601463 345209438 657303074 715648784 649612102 53871450 503270645 998539938 436327376 867739101 339185629 665763129 217887248 213059030 687232799 692149863 79012428 552445745 423570671 166938728 631451384 377014192 825000607 926530166 663263255 995948232 629021045 510688394 894268194 37336933 64758817 112990611 855030568 200391222 559763821 355462926 199385561 635499814 803733679 916665698 913987695 366910306 543533954 407384214 509801175 278507525 653352010 200309901 352316225 921005658 955642716 363419329 312313501 199834631 916897999 736695265 756333268 815086767 637409904 365683792 615750841 423040799 889908801 283395776 529931015 548756284 842312324 421129123 23773155 794108456 424677075 682075420 248364566 749274222 847062373 593748447 377236623 380595842 670199284