19526
826041546 979383422 286062207 181630023 390715101 877236106 302829987 575911274 448353035 691430592 902866259 557367438 41712541 978501653 912811983 371521518 760546864 651045394 760747257 660721528 437970038 260763520 928991478 852245960 981383521 404146594 838472280 436314495 609403081 543810333 314781968 925479273 464563172 593663433 202334253 561094520 260954391 707867532 750889743 997541722 696462290 347260453 360321049 79680003 511004750 786528641 815162488 411951105 241699542 660450360 209053588 700009209 500050329 386469260 886508760 534346652 212053156 736707033 582944217 422830078 420889712 101231459 827722108 56298745 251069710 361978573 340118844 454635268 562638044 125909407 995175365 889014976 626932073 137091652 592348028 672380209 562216557 233361772 749260059 139573171 195694182 633457481 717608420 255131484 979568465 297409438 111352562 833100261 383822019 943076835 864224709 494408723 350396062 516934570 456611308 993722258 152966364 917551937 757253805 690862179 387731232 974536060 473387379 917410033 787503928 640121994 36352830 292922748 279934827 618414592 372715166 57785117 575483373 621225033 412372078 511915098 539947858 439243748 918025014 742472791 35304706 158693356 269196870 226322543 85687826 181817872 750573228 71094861 790024380 944872345 34189418 977725038 539120084 438752871 306009709 648810342 656730687 955799204 817005889 941339392 499615934 112660952 452522700 127386757 371530006 408476990 218655831 283517372 489886594 421911297 473027354 598854251 411027119 905736854 130114413 904930529 587633466 587827423 210875072 228247747 458804993 416160873 710890936 277780508 177915671 488541297 920010474 477402251 389852818 255681099 56816840 49565765 966516045 399484250 600559876 953284162 829343458 604661343 232910129 334361520 915244446 709419806 587035397 832661821 701008106 850135315 877971777 978529156 630917439 742084383 703117525 129232958 604127928 252110883 401448982 625509670 868564226 705629187 897914303 9466641 941713036 847202363 146812655 604523833 271122649 227050119 297440627 47440581 982998963 942702174 192984307 968417639 749123751 897869819 849641997 218336024 382130943 670032531 52933049 263417298 9967658 466163377 611635813 609567826 989687612 813601926 908329908 880250289 345421385 888262723 4635929 203714556 417853706 761025254 796717124 735263173 446206517 48679682 531324534 621552348 548659445 497922946 27868521 568454703 717447784 5127858 494245836 464746945 846174731 321607312 550309715 845771256 987246789 3931894 15781037 554226478 717469305 822866158 585632616 832501916 939085225 304373202 981726711 180652704 611702235 720795642 461378908 889259972 732611626 981063042 635537611 914957306 727777608 692854486 365097258 497487220 847507585 802423110 896496210 353240899 750964208 612051215 313404841 689919624 208755630 423051799 909335821 670141224 911809584 933834558 817947824 811581947 851384423 164468978 748054403 133331661 821520432 234732660 731204441 872496908 893635272 783293961 73825800 698667330 906014518 875058259 684485108 398080959 925389583 969900296 192730778 816780342 233878325 794462669 65712714 460603524 389585101 310314614 877760045 135537916 852201188 625211924 270772753 689796578 248722746 437933158 489126527 235413713 556942121 614774106 265024819 137289994 143766815 533608038 796867351 630770603 375505016 933918700 908760042 496032061 204535098 899728855 864302671 587216397 508023329 527093697 776921548 238630203 277430056 976768118 738232156 977563890 568813304 958871982 430393163 717094541 426866453 461636492 495551049 994324543 197639625 161929010 422017784 302394873 667094865 270355372 250219051 443508533 209841979 270233976 264137043 292431475 538857398 132597750 813148553 765356036 987156317 827294532 57359848 897830067 901979651 186764827 794043572 907190584 372501870 183609571 202647436 447825907 190414477 17846584 910448910 450939142 738185022 484784684 43121294 819723483 888435666 225436105 695892105 660952346 6422686 335905428 703899602 479900187 68015487 431960221 276519962 768368338 79948801 149141142 149142494 435677672 690466254 506651342 173171138 438456721 582635536 686704698 389241272 279433698 413305194 730385267 428165608 561434610 914623217 513721826 988649808 26523376 308618385 146136663 134518119 555604645 584972752 178349174 858046738 515416381 24097120 45598653 444903268 828616194 646540287 125782270 48188438 868696090 711733303 952249807 779609591 966900095 76290395 934027039 269478579 838751464 588343884 858297977 631961160 416606714 501523289 753985757 528063647 677120335 910011970 695510190 732176788 843445448 773383938 641697672 197856439 316103221 371850710 397831888 913849784 27678965 477485269 452501183 840877655 795955627 580816896 168631898 267258492 402892495 707254432 59881884 324299666 642551447 633733143 579344461 822649845 423730607 460664704 292663977 130289494 777767051 778106040 580065658 244590099 879656570 991065640 880946680 152489367 54410634 261741464 405388708 768347310 722861540 544221341 597524502 846726097 302049418 407657784 710278167 670816979 475326009 421583456 892962478 512349446 790539115 733455488 678923121 320347396 947829903 946111961 283927023 889792927 184652998 596686894 757453039 364471939 675610566 345912261 417667906 676001144 560397579 908737387 163632737 539953193 424830450 189668262 421685986 906953788 743676399 602834044 698715243 93605486 291737792 892151390 319019724 850439354 15648451 316756529 86697635 486360568 596047589 279715144 672499088 397383812 90714148 739844232 287813533 161278730 589020977 888731225 947081975 110357896 278788664 845598060 889123233 748995117 294306045 305313248 843660182 278208850 531493037 412613316 722885260 341524961 711364963 615139923 446716077 907079480 62172078 382220650 46969604 345174612 920340531 748022100 910658746 705962674 254880710 656566344 379008070 36825261 779610235 835584473 676739342 111211384 670057514 68253 664219195 111558634 131691008 595267157 928828316 50515198 326245809 682392535 945828424 186845517 935833843 742798132 216972981 253247012 92246852 619135468 20855877 64643187 946594834 463334642 589335579 517327540 197957656 554950956 250888186 347855811 97211637 757653161 334588195 312031258 920981534 968958682 121978479 569465076 355654026 297901922 757280082 904455993 510572320 7817212 2586518 249378079 783120348 327559915 445245240 327755039 225046940 529969478 325240080 985032632 427411122 689089720 141930961 851920328 937281952 611224133 106278875 623296073 672429568 936109604 721649769 708860610 179001187 527881132 554093672 129466449 617860704 239473492 987950516 770121439 131516271 108526959 527786211 342678694 812894991 52670825 73151587 924095493 521649728 5152800 583049779 692166656 31156445 166627031 174598035 761305615 543692304 958148994 641839239 703264360 19748901 967750730 917776621 175916050 702980001 171124340 831290562 647945479 727836572 910571774 918433544 165944796 426253156 58055090 294279951 74393032 699130389 198205932 414577914 467925069 170068982 614015433 124651007 67633482 336351862 274866616 703718027 6621801 999014701 271361218 837051663 305349683 603695429 80756377 43696461 462232885 671982373 822721663 936344247 63895261 352520837 802922440 359941960 569152922 917567978 965853930 804008202 795668196 750392534 246605475 531051885 745045769 601996577 382405304 685910666 414988170 982737767 920998088 830261059 777043637 97376396 134480365 247985125 962970461 858087797 645172956 669782190 188448392 641790611 126746170 314769540 186525781 988090094 560642329 322448475 755150857 395937016 75004807 631003278 425035808 253517292 987315363 913837494 11076758 874396534 617897018 892756045 77683634 862810301 650877725 512489409 533646939 459979394 15345060 974333036 534297439 626295862 798124667 177062272 855272446 108606880 765877265 559706595 575703091 727789476 312194452 58961921 211688255 47043277 425935611 921844369 575532635 486139497 947663202 392361740 37419468 538718289 529663663 379474846 590721371 161942483 736027867 75086904 355704527 51328934 389003067 820782628 708288974 720789907 182526421 586901125 274219383 813702743 288767451 903236721 711516121 857764608 594006529 249245936 696331009 160922750 945773982 355090141 250800145 303513460 179781358 517555330 492145549 383963202 948233297 191000743 572709160 794608410 820168193 650444001 570157264 874915649 367717675 40229516 973877417 847082012 997929358 521941138 127484897 533744934 817648597 735582048 804614573 712296556 207960481 837174390 803795743 66507952 692036806 457512260 242813848 487990050 378941395 686957985 718032043 861668498 881531650 446569594 143939399 8689657 133746981 757216791 53845140 574906427 291440292 205942915 554148631 831498609 648950786 124451198 475411867 363056645 683137002 613899181 16671884 240528689 901999694 272143283 410060253 936247488 809211255 666233972 406416079 517192015 111163542 53413022 444108425 396213591 745785025 812874977 609446350 824916482 69723442 565383626 860081844 584250465 314466200 887615624 339508392 818687048 343109259 795939139 162474018 107731263 201192537 92142755 882517847 524990794 394672305 937696827 181106602 810122895 642466349 998387610 448144277 945546481 820300067 630435498 806670990 791907248 471325941 702763375 198749565 942003689 646021641 305172254 624505262 821071782 848860685 30243471 901403194 658133307 67939644 700997392 951818549 191284388 788538669 708779887 761881335 596259328 397395128 991609030 516805751 988993494 114035003 49120460 573209195 700179955 918880170 190945224 23630393 610374470 937221758 667687066 808247989 504775404 956223937 497046239 258580667 170173071 164670170 158836291 674981659 385711205 889085365 264339069 664844054 488037836 261357282 839969612 958712339 270076281 991995422 105831652 989305284 897762044 967874011 900658517 633036166 984539069 291464722 89902488 334651468 614264905 958824307 600445467 579862293 425226125 310587682 41077066 696949874 283581108 204097808 625521951 209673289 297939122 803360625 317917183 680623658 816271695 299793522 151136086 504717136 774373822 240535688 879257195 516697719 571480733 183619614 81804159 681999458 264415245 274233595 570469311 363671937 133281722 775394186 844818049 991222329 18451687 828434826 179473083 90422349 814704983 787458589 277104334 518518184 340974954 988468564 171466116 805353701 304087055 889932167 169668425 208103098 258600379 967878230 419202379 421511854 845230276 688821922 446664138 963433425 730482438 399952639 824564855 988567252 900420099 289435430 122484914 680856529 902599987 674824140 243407520 577886421 717666966 344731145 695762436 998187559 641269831 293235391 344586037 916435799 757250618 654378695 583064226 318561270 815540474 34348809 551160284 951711060 72203398 934136744 968515788 454112334 314942454 360751111 993639186 916319338 810554480 372371517 660047941 246435160 111689291 933470503 963599997 636812809 442412424 556561336 634299103 638885252 848929209 9323674 404215941 580236395 55947426 690801796 104812175 671863086 493845331 719717598 170880697 570014209 927060296 100625629 156423277 506816046 815010546 885238242 259858022 496206287 411941874 89248213 69607315 564810846 567525076 568628283 556407071 259535027 778209395 382863122 661483783 342232771 649881637 199983423 233164258 99372664 251662808 822719792 197604684 632003050 419511859 244238354 811206427 330772083 772765385 615836306 461206848 871704245 277361513 310639183 478818911 297689133 107280034 307094970 26966458 622068965 84582669 724795876 128364360 600423394 12738885 992456759 157951195 704154373 423919700 578888850 986180234 317771048 560357984 561690829 928520478 806732828 790679181 762321246 40935034 664068797 778659375 223627688 206599183 359487900 383491105 352316891 64410744 748593127 842034965 898438387 355482176 866584187 185120468 965048531 104242130 931034081 214557288 589212651 856979375 691178887 19553737 889131332 392049538 629672053 269031319 784390772 115629752 803263085 530436034 608410457 647864258 462202306 859515779 321496985 32051371 800901187 22658799 916160104 777851292 399586073 602622507 5469465 309621458 260853117 293294153 47854105 629596138 488363938 235950372 369977015 119366988 821582583 434652339 861882802 887672526 800813886 905985863 859833793 95301307 861612003 591601000 276551954 809077010 243619383 838984538 380873457 715268999 159818546 340573281 199252916 449516545 999681089 731077443 289812093 165347721 793243622 580938280 697507841 366846709 509602493 673834747 14807160 466649941 772737214 615717177 939292067 447772518 59150035 253509606 610452340 609734315 850227601 226191546 744065136 558587571 504320214 533077467 875510352 110518371 419488325 333479601 512475950 408322761 885500581 434470185 370344230 811797075 544229302 967169628 907759322 586453674 34982393 558557327 10746772 297150273 322626329 784131804 916801433 905191586 937692945 573563381 336744011 606937322 99993284 372190777 734424131 999249090 599325534 579440219 473944954 779399352 823570184 354414341 49401439 28348314 622988811 888866257 552253142 907329313 65894168 834191970 183741298 671279354 745635711 644209984 973795770 911234483 317846552 234159597 516554093 315965188 725827427 60015030 433455026 834266953 64221330 124739521 756091153 38143727 62896090 174199579 199621569 592975982 549113868 808858855 295522115 712150048 562866740 130644284 165222017 60153428 608607544 653841249 622608392 48560422 414011206 79037483 176358098 277565461 86272702 28862392 3096660 74905766 790765510 468681932 972812314 843491360 537916667 80372076 946932890 645904008 784335412 111819381 693462941 853664395 179249209 78274225 148232568 863642965 253398210 946626378 379482253 496433548 208599984 236776429 734350181 681090913 980928561 557974491 547022235 121286111 319964767 56496085 171964105 976651759 406977888 620462247 348929036 304042727 721447462 909097345 591520163 865569881 57896597 236533614 436214872 866246281 582355255 988372266 686310978 94423523 19919293 53058881 239151029 13066898 395697051 208161865 71870 835397789 735705346 393193613 392921713 776210882 218571165 283115006 76477293 30057974 908334727 918825132 342713832 255274900 269060696 750872038 994805725 846026307 836196541 370877352 895511664 800323065 905304223 168366308 870756521 482044739 84511484 671834510 757096168 235087763 46523253 266322084 382970356 29380719 108515314 322124696 562235905 573211029 868986545 30827273 308309861 619433589 251586197 431930431 547012830 203600406 35379199 812478181 383466358 437502053 910901381 532707216 735570001 353966069 524701245 133970606 555968493 174434119 772540106 893737552 128024905 464932349 580199487 940373787 89987126 244018932 314989437 471354332 897761280 770979197 406370192 725520017 101531414 677456266 734059827 819505814 602356358 711637122 597652599 161556249 578900611 597715573 734280766 183706500 852772896 129346367 836322812 283937301 738356182 240185979 194737372 554174883 557514798 617574812 672661639 436361599 991944378 874215208 309364732 68874748 851133115 370463515 559481661 41041683 413911869 438071676 673779022 510521870 106968572 328581947 645759380 757068673 485443267 229995935 722096818 742847242 505495388 411123451 576477704 68534485 899768584 237768434 680572132 993431447 544911508 479847587 325885742 242317357 405447446 696091254 677219433 420044254 431174108 360151542 535399911 77557515 988094297 962629113 146417135 138051437 452296867 940956004 772551627 248937343 674849596 746976262 442100998 780872945 85787089 468357778 913978383 886742387 340763816 221737913 768820499 344361276 781502713 746599373 910277821 905830654 977111416 343812215 754096467 38335585 73927493 215695085 466347919 235244334 824539059 430421945 987338975 660456841 623157759 801506174 820305656 259541003 829253204 724716850 843472527 484236916 468299400 199317640 277185337 148313277 94725003 6976504 87869457 322977238 349853000 558196480 208175083 758855130 352225626 347085647 809552799 435429943 971965753 232300485 757615356 650207290 240667228 312085575 497405715 281875107 653660405 717487155 730569561 904520654 388901499 426521631 112383216 445183888 233051559 361345336 391772609 243106233 441834275 930227815 410295509 338720203 899030121 949960743 754351350 36433719 942967643 612944500 388166869 214266588 165987348 47949177 56310422 872744393 469582336 793774086 779417864 329162259 29161000 26730178 38619331 784463120 190859906 249409847 867966087 364686819 756644318 682956284 377532582 734954554 95380650 446054758 117695510 75512041 853824692 302785885 952095237 740632609 425582750 517568568 421042250 462660328 5414039 891462510 701007576 203751194 379702712 972816146 381726149 491593654 597386547 690473738 376607163 459816603 585216044 78499680 800497504 645963980 221900 848778402 331606293 488814783 904385815 313293112 444537421 892498339 702616452 959114161 673586550 811095793 860861444 386132618 292004444 253929412 662515746 459510612 358709642 126644946 749353549 196856615 833934447 815139404 432065866 686332400 396242203 983897593 991847675 500649823 441638487 485458936 495667278 425177118 112285902 704958032 929257332 767196940 390772330 611947405 884527935 976205552 491971651 848658054 447429701 473287015 726275478 765555562 533176740 357844872 981903685 794650292 205272186 158115421 820778747 732133461 66684917 490875833 776258532 212324985 383639564 797604204 483224790 729151743 55335789 275839062 105404815 745107213 444509833 926992494 100370690 264367207 357303459 924406291 694452874 133729073 735377761 290606995 119091415 327999040 965389675 925591714 99832515 56082699 734012802 770060468 551705934 587986438 846723699 437505571 339984270 914436095 498613016 195389228 165560996 462384898 211360034 328305897 633909941 963462956 532484017 198890625 350168904 568331595 495428905 980207462 266009120 876921699 444496049 564902629 77541069 395802129 764195300 843949892 838946313 215962959 419308648 893035436 3398190 15674338 599185317 451149442 589524030 557694373 540360839 490722389 48540338 759003814 909263880 30031446 464808462 480890540 557922724 387026429 4118483 303015855 587631282 242241822 960385893 96969779 413374020 46051697 456311132 982240052 472118183 884035490 844964433 433024117 315349584 891533589 351826842 604971468 137690122 494063414 698430518 981637376 486455297 792199402 604814511 91785780 666484924 692263052 550593531 985673414 93328776 685970329 379345071 19738148 175942828 448363192 811764682 544073134 760062427 280085381 735699232 246451214 576255410 253522930 565451712 879143177 88256747 34796442 530482183 814084222 333316261 125748236 248553445 950235347 881170614 1285794 905688142 296103824 99431359 229117222 692294498 328205975 998835562 863905378 48013982 499542866 201408229 196021391 146528809 750014685 251537889 407461079 659195607 844327301 615551993 754060419 279924796 308366581 551471053 542043756 591400503 768707198 221035018 28226821 177866507 4145978 837796545 762392468 24900062 773920878 344434371 368931338 510371636 221810871 237394905 258951622 947015266 418487760 351336263 725736147 637417315 312683885 887400272 17423871 649095444 619231169 832258188 650411543 66612358 308079952 583092628 821716961 537740588 701679522 860399431 290710390 631767699 231512294 366172720 223950123 60006288 346678910 5728477 570149425 474543749 790578453 288704278 401425301 221404526 37778039 805330853 917606986 869034747 193969545 476565588 151064716 462713439 467857552 835278144 991806843 367871165 274391571 317037345 180805927 158053437 471175893 400707903 283897310 662409623 796873152 587754519 540385693 944856318 390354572 886404334 59086838 35537410 285962885 532665380 327505507 188357836 736706506 69700805 460834869 596270881 653744872 449057999 319864196 640704624 495427949 194856638 733243795 660619046 258583324 918715262 27216865 193048722 358191480 44238504 148861684 439600836 506977808 43490486 357557742 548598624 216375407 35666634 25211768 806142985 798681618 421345413 410079742 59731524 730359325 88191240 269501007 473001811 825380856 964813333 152706032 653461669 381619374 841915459 975986580 607810260 914500165 922524471 2193068 603105373 559948001 398872506 834747173 930075521 650384814 915308250 831192270 337583059 635383109 602461478 550594394 453333409 841175686 419976311 326571567 300043502 507528052 94073870 149939477 265885538 491920473 394532890 182065090 20799456 674519610 329810003 859496898 542061909 688436656 642024512 254804804 312431317 429375012 899335924 578586513 491778852 548512284 504400332 168651443 942765827 77410859 174211970 593985597 785538850 137773484 395205846 453476207 269667055 43232791 12958739 56609619 507478024 659260772 556750487 97328803 247791019 233305109 67735666 815413606 352876495 749425694 972267815 928711518 846990609 491016718 180387500 399240081 21933556 351833283 229167931 378148024 438670270 642276827 73196729 641353596 924575473 656906848 974751613 742712325 900173987 882182986 490624305 673743794 136192468 846354705 929162165 341927756 21615631 816665681 824649300 400133141 525524802 431258216 811834736 587917529 666716417 106763019 956678715 552159602 107446203 834315934 744795334 615068920 134364399 23430023 45022646 567952224 468184346 744766209 300684971 713628814 910164432 880987313 204394987 939445373 263259675 812066546 674284681 45272116 902868269 867522987 142091376 664340885 913445162 707668573 479816068 299794438 761837529 707520204 952420727 71079298 727324212 867707017 480357200 991482305 492687887 329022379 899042064 990152935 472076995 136177717 915975277 382899273 838474977 169775718 283341071 294396495 790603111 520311944 580105253 776339079 565274485 917992741 879271256 75887438 512214041 31634842 915816842 538160798 721564992 487305392 367505593 212634295 786496952 309190876 852634691 958949194 392133174 170931838 737364875 677353233 473799644 862991012 642778834 234366272 586627450 723904604 236167429 193160715 434761917 311448877 542356181 612225147 363850201 23708580 737245997 549599240 404119530 389069514 653325065 550081674 329525327 120518599 66960416 632022430 914249851 833838035 723906951 283912620 703719028 78035479 675740077 760320081 75115173 520266491 492364033 293353091 774792664 418784879 163544617 927791885 354380801 402208718 609376439 599690364 559566911 731065907 758248262 85485995 807198127 655218354 448065177 995887677 864576957 326740376 411768071 510435006 748242009 475645860 838641503 609707965 485199450 52938631 600438780 516968762 652733043 130262438 120221775 957312153 545104988 8011363 715574771 95691802 996413789 12182812 275123027 258931828 297063924 840555484 784408400 26947070 369134217 528869114 117303367 227617306 926126413 539991843 32541243 295761684 69365820 27490850 663348391 461364972 746581181 644048290 539798058 40195387 345836367 60443858 806507869 762401663 453302741 217980625 198347828 748989751 94914065 525626160 318138346 760661767 925403891 171315501 536010404 43206580 547875345 812323290 670132305 236975648 40607368 205587979 896976325 134800236 290353079 729824031 286570698 561073934 40013066 719664902 808686719 776901984 264990409 992241625 412274833 244397786 944184966 313869897 995022666 439804006 483598209 803496954 279558248 733641472 88629588 783605749 606646285 213356762 12752488 399487503 474945619 320019814 734878992 586579163 846153585 176323935 676264364 39172063 447213469 742454585 506239340 429908990 385258359 918725625 858230816 615056974 487317785 358014306 614537147 49978739 406438488 692086992 12646005 529842871 722737000 437082842 207640883 469144812 35611155 226764671 687667218 906310536 240659568 255498239 723363723 861943650 545658914 802049129 414868010 667782938 871211286 310752733 807529829 344488647 703870004 709624686 145638158 570558395 286273876 722055871 870593230 139757327 58502378 574366264 598638305 422883327 437772102 956325475 995331868 344293067 918068951 386606233 630864592 140566688 850226266 43278082 657634139 929401116 52041002 588171542 40006938 356435357 426156699 461939544 283724700 488078572 644778271 575172533 265907251 947047901 383301559 195283755 218070845 215270867 182607017 124565412 760012652 599725567 327099365 386460701 664580151 968845362 231350762 799894059 359529984 991407284 672174977 469976854 939013357 870286614 108168483 451706213 440209136 958470025 703160146 311119648 821449129 634945213 269330860 258940265 773721609 414866289 221919648 15386249 986870817 881704374 348891274 66280393 736109512 951996814 898138705 460412752 15230798 428900202 981077552 341506583 509742964 925897138 371002168 323134352 43441054 457113114 408807999 11120595 718646466 813167242 618085995 202238913 696000128 526689516 208722914 206300540 872557560 685829402 606251324 138355126 901387896 74541171 941353548 501859253 444424050 448479937 120711493 438685181 571610094 105333956 350140052 1083960 349303040 669111054 635875007 233147475 888481851 237168638 650418484 196463197 380436341 542027239 662207934 88728732 84033266 440288286 137518729 422679926 809309879 733610384 215202694 294679838 965132696 481443214 716351765 942523707 210714900 26354815 913091812 807140471 643291876 39814172 834088169 207531282 123240123 759347859 498669764 607330340 181397733 565162101 202017157 154768631 929344238 982510317 486772818 401279687 942421000 498897731 227013939 661473934 530962884 163662175 36585865 94510641 528592897 342057717 949017247 847951258 711796023 980405138 495415549 445763625 395055874 469495188 271127400 297483320 545640568 823645597 48611060 516826072 97207340 197729088 445119190 238731609 704456091 781678220 352573914 82422545 596361749 235093053 413446345 621689036 593946676 552550819 429076894 717244772 957330779 677573186 617544487 132628847 194235229 684602298 772731850 892385515 961851327 562188867 877835761 891933125 137379230 567292439 176583222 696296029 457399311 1708950 73463197 754825731 752642098 149618317 234387299 276567573 96700516 821350497 882020626 344014353 342075543 176186516 957762099 155030298 677549208 916033627 621745343 22759062 439576298 947180104 278322087 572945579 167641964 398858657 874186406 313258870 959395012 409651597 873024354 487184091 792982445 829571269 358660435 905845515 344759395 313605917 791075827 490597558 969226532 748878996 787077746 443419191 384253996 567298590 870029698 430936904 750315099 619236643 160349977 419957898 94271276 984013995 437934513 332705909 211525367 800652230 48564552 336467554 585026987 278318562 45065702 899595295 642210863 3779982 713514622 652382837 144015424 745369321 662945424 111912916 505071213 917502830 941651388 578673000 186118796 938487841 349906071 15259976 181190364 280565240 80353483 736244198 134923926 393396315 35233591 625456449 902870813 388662195 88222548 935397807 32756086 836391285 957802680 126949026 316853528 333049759 44680688 462848962 985557689 99434694 849424023 859040292 790068426 82717612 932975854 21450751 2729946 481465518 609565235 678442880 932876625 615426378 30833821 241715987 210173365 384859994 827604411 200668159 992751403 31674139 24962270 173535714 810386368 843146162 377301285 856478018 267868919 86062604 987536451 885441081 273714082 513956154 220912101 6170682 236202025 888367402 711880721 933048399 275105384 204529107 833490113 355600143 991848722 344323215 176812399 332133509 666837879 32901262 634032223 691261412 696053663 438811629 782036369 188154869 505404950 118496090 899406929 140421767 929793363 616891499 207573848 826697318 553796168 997360147 115504328 481868144 255376099 585622851 890051538 672540566 117943214 897145899 597539550 647635940 420421369 742887223 409472680 314972387 475766537 668203329 973008000 260362843 154033650 64865547 14172532 431466871 393816701 235235737 117009383 11498137 735740238 675109654 262015915 859472551 432088492 211067225 372485710 529338766 73507236 204583029 2412612 168685212 655546920 437506136 711142635 452545114 851252006 708073787 150099839 939343371 217451481 605087931 185144942 427091756 980742621 85192545 644336201 487191650 846104144 799867682 160356054 259030461 429466111 673724867 466758193 367760920 649009627 383654921 243387388 31486940 85805283 546483430 647602867 578298265 362040756 297058901 868231181 220822215 737412446 406767975 210111130 425307231 857274208 331732445 239466095 2608547 945231770 899171908 278548060 137261326 944266576 997558743 204511595 837085705 422103136 864664804 976231880 156761687 235604041 709824098 431251808 297118055 479973652 306862131 481945652 940039827 757415001 542052477 219471052 353723640 517185392 76471239 637741298 931627662 561210651 463449764 171261309 591807879 486212128 373570305 544267486 423878675 241792801 228071470 446531205 426439470 948658574 830915975 920561492 481051917 146508492 878313206 197658131 715269336 83920373 935034859 230381443 142562465 575858210 780379289 536024518 661349011 281353852 36092225 261169134 155940349 303873597 855648254 374913143 483639166 736296161 328901142 970021729 656720170 106577514 347341324 831827542 446404013 812156090 998137878 446852144 324834568 659722737 507742671 47285517 528977594 247099059 256895908 351006689 820696745 416025795 64688480 62706385 245161944 888016256 108203494 629212437 131068157 454085925 837368936 658725875 807375920 783657675 289783345 793708845 950458081 406116908 68728825 43162895 478828303 894857019 537902911 515746298 977369570 669157272 936233769 736629165 314186687 419677442 290171163 493874396 941353434 416898411 362085770 302904724 678936949 929905078 651868497 557135844 915261238 905293829 756224737 999808693 326941972 238077632 522734155 255038291 24243741 376419846 919851619 172029472 650520114 820130378 705873314 933810109 548951715 222043303 64217037 931989726 319992661 381792365 56800788 301954572 65351921 470786665 94068602 805436642 867515063 421043556 980472469 414883348 792684391 209514938 762738443 503549268 156604817 94239862 381927171 943665967 924777351 108185934 886669336 287511066 999460464 420247276 911528774 886932598 509803188 137335375 144984166 520389828 799768625 219142450 216163129 223223031 692262699 278985856 510167333 850039210 3042530 271519521 265753620 20502635 745060165 529557805 597213407 498963038 347775538 111398014 698135725 487620535 335351769 539540398 566800984 431976295 341411447 80964801 979089180 227203979 804947597 367856787 94372988 466007547 224767424 69317020 464878894 979741444 747675607 89960900 185327856 813749707 873798165 253554980 985564765 804583642 31228472 256882945 839471634 957109642 489768314 538412598 988506284 804742744 835569050 56355240 922234542 788655778 234409708 925649536 454284377 748198170 459472118 657716739 502934010 471217005 415200373 67890827 337320166 385373293 567716999 142942069 415003761 221278801 54731292 733381443 481469422 176177013 605146584 503616214 799077352 682404469 142031335 622520927 804398079 424927475 798951657 966113048 572715704 556647924 162120374 774441466 728715265 969993449 205955667 365099840 991834823 117847066 985025781 626691767 781791207 645710758 822610776 479857360 33432375 643699475 812138006 993072454 923493396 895440923 82661363 158981650 230845016 360381463 492878656 656596251 516121501 859841903 969124561 866307225 400899090 207973835 20236655 940213737 769971929 558354520 660293928 540429466 533364236 858347183 748652943 28822495 131770145 545883450 455588090 748978197 971250117 998054032 689394460 901183107 151092397 967198745 204808796 190370161 442810875 558407174 836591104 168429163 545397762 361354630 803529543 83954084 401887257 905696783 988830629 804106265 211648274 965109055 690713292 603908742 571247044 195839083 828375831 398811784 647200163 677799650 496804176 526222036 535409544 402955249 26334176 21766207 741206350 829078344 250346449 850737732 168769615 261072971 138480230 824139662 244745177 425032977 511503302 847356046 386629929 19237028 613195424 259883596 616988291 440097606 223659221 189637638 545679778 511879058 50360933 134099627 34604048 296938156 407299181 997316744 179846528 812687136 257714058 543723649 598490199 859700489 492620515 73121290 857395087 641189957 774180298 367525687 674234146 77310987 591641937 551352933 48604051 132473805 658204926 989756412 763102340 814980310 343656653 41888231 890400993 367195622 698590832 665878114 708336595 245861153 713713677 980901945 773346601 536707054 740035282 283341588 616496122 438746496 938397730 605796609 294470365 518501228 820838088 72272463 412694939 282676241 770717501 857463144 288860779 293757884 910307776 744546136 574197124 917307297 857312817 411835796 20262274 894864919 525399602 712835704 614571322 743843785 181016148 27663268 581986552 142452770 193703866 419595823 705273469 888026450 544209304 638171308 287520045 320242396 956137152 436564133 11115855 41245504 58912497 600712524 870529264 330522476 396433467 838122974 747242475 338534958 318116922 395938362 849150571 955313058 449313207 540455930 709579815 966021579 877991879 590281508 424808926 359570861 303441959 118237362 320530126 451707934 314002634 406992220 803132466 742977309 944632390 471198276 989012143 328490224 585661682 12179835 127837062 215089412 344706750 15699213 663549037 81378918 216307247 928463353 919786167 918166495 687509034 589024437 671157959 734396655 259504892 189039700 487554681 993462746 8622540 34592516 362225953 812852726 785409357 449674861 705320066 178045035 589408418 986891271 313295647 956795540 683652865 212926361 623736771 813960409 363194044 568044187 129333007 634136190 753906107 813236966 210452146 945221334 630359823 387127835 495202842 591319227 496826645 657610053 468069717 304668782 429920418 990225342 39606309 581274115 889222126 754822312 209288920 137416566 920689664 503645033 412855046 982437364 239465975 759584183 73263581 401327739 609524994 262883140 60692536 94467813 144271525 829453070 293856328 830886679 38780906 808007755 698576690 914823818 936547283 591925514 994989876 640105258 781284677 953645853 820948466 332530984 630012603 726351876 382128303 575727375 980195142 342577042 474619860 573361615 43949233 930322939 917869870 913719112 999154129 597096072 827127688 443214395 310287920 234919695 290336121 80185706 713582343 190455930 313119910 499512940 181359981 272990838 441467859 237645133 198627062 471668634 869657044 708379995 506895000 622011104 537436405 577761589 337784249 857499582 621590509 308804898 749120324 876091815 109442095 504240096 833099100 584414579 535402370 687941059 576486234 417848678 602191430 132597255 973270708 840035476 464537568 469414196 395435416 982160182 36944348 669265071 559653171 681047814 307466305 873299387 285009921 640661234 842521017 292404057 822509009 826665172 15660938 418280704 892997651 670281629 80208658 646291155 403348725 156393416 874987724 877576754 591581685 866765576 194680605 924369086 588084448 982150103 982560836 289052445 985829134 294408226 399928820 505121369 136859535 980726359 780000774 281506913 692136840 872757650 958961851 661208846 917656430 462425151 875523620 870567018 313639746 722952321 759308956 130506291 19401119 683151870 162793663 447063031 96069619 53527926 464402132 147071667 9641181 993476587 647826585 241616324 954175295 627193058 974468073 835309731 238046039 205924092 399039895 707951867 986024602 949847053 404327762 206137973 527078192 578945755 19060357 943214472 462539757 619116073 249204060 326359901 551417071 767469687 398005319 320712608 755029709 497197062 783220914 246672972 870084552 903352911 420948143 199442262 3546672 743566635 516671027 588651300 78289910 79805577 845967091 467576153 83543666 818562813 360332133 515921964 568015465 712593441 333714073 353011052 758273182 621209392 561459912 664387969 224296527 418791490 746662891 415641072 576734947 993967681 109523229 440552847 880682926 632056881 93311429 183431628 929366626 487333462 91504195 805450064 239536760 318826076 565363932 280329571 813474238 386604121 162524698 214667877 655883242 379761139 893816755 258920109 279752199 969404855 911783097 136429942 763705299 149358438 897117780 940413888 492268767 272955978 298874419 443325126 565259950 766498038 129108798 520773525 335092873 510545069 240899389 550618894 715220006 260533652 601420366 756644018 861163997 482127141 376561244 243212997 294309084 934570720 982493426 819956583 285156263 8836375 447631932 14501760 137665102 315499311 524903180 965607741 592575271 542446817 448191028 548841076 631384473 149849675 619355060 396963183 503790448 750544878 852412572 659682915 210294742 17213427 244346272 401491669 177901836 719945002 954192280 793287989 537951221 103888986 350440063 781862837 267867173 226837090 676955227 167032624 355821431 345171500 600850588 787371440 237903570 605377487 260883797 562452892 34582944 303250146 204533891 445804961 634243568 882450451 822829536 247481160 425748479 938284747 74779132 990001762 885699152 962829776 628625034 770097524 911382870 652997222 312106609 285489432 644319568 615224925 412232055 941607014 235709096 13417995 962958791 102968465 223758713 378420782 931146250 780436541 43415083 267844119 267969447 706534741 217533090 336463813 262489424 204929325 425165354 835588675 912206793 177802481 216135697 215414306 933585709 110749314 860675060 496015135 438357286 161483154 940807124 329934280 127012571 206519340 978255060 110646300 68933423 554847499 471201613 791918703 420120848 11391280 590140659 439111976 386858010 448871532 809563448 798237888 433954935 251557470 623490251 679375412 296915062 805940252 402669531 478313438 659495675 194179817 15814474 96734727 182491975 726828610 752097817 763871330 266430919 729709765 679896573 271602347 888315212 623910665 721681890 77846420 909488289 886061312 4274782 500788548 599843078 952311908 920006896 325796935 261293784 864416453 804898955 350279845 156521918 234503286 28220799 913332082 838879121 465860030 378402876 451981732 383816471 240660158 791569660 456590115 518107356 163378483 456501291 928442363 38956510 687947674 42462182 699953349 910069466 504926888 52383322 708796079 591076744 649566858 590208924 471559270 951044678 639717844 737179718 401970449 661614083 221457815 509672554 285365475 653140155 727161751 172702280 941908575 680373494 898658098 102685610 739757072 610949347 751327203 573899078 349575018 457951910 901967372 10273130 213094391 575770536 817154892 572307172 200045360 559300334 108132877 176942577 464308011 883919911 759045527 989558935 886085642 751889408 794636516 733363767 4131701 626325059 169165121 750327826 2154906 339873811 777177717 286475519 277694296 120203391 551743389 384878582 787297784 998555200 88608835 328140911 993783050 717874580 780039213 112733849 523430254 333872727 803208442 350437348 863233668 985930763 929326458 363612500 542057806 916216048 668073147 235615750 874653548 756571416 890294996 114617595 19861619 393963784 125163460 494593908 82827623 149462978 38148824 854039567 352560518 597799786 762896451 413658798 187100683 727961384 221508951 36952119 811366705 779192820 728500048 137952754 658518976 249177704 295533618 54581001 200813089 407710649 828351966 849479283 438838128 47868174 295901647 650788024 620355863 934821049 311302274 728394501 286010509 330713428 550321923 160068913 919728787 115125248 474599816 246970549 543408171 376766229 457596374 862198782 560765670 912280429 291081045 522286338 111485021 136660479 182116933 933824876 429848979 202674746 902726553 788818943 893762946 823484321 260286745 592954347 836161003 951649838 988011209 494778740 682038971 356511617 554300977 491292976 147288229 798416211 216531962 84875083 618496792 33171167 428779393 768276713 63690881 717895855 168402921 107148696 767647434 37515898 958645894 473897467 197942825 58274875 413103046 428968640 180725844 757346369 300033445 69405923 573624570 365153967 772850986 627867220 508804745 441102301 464153389 430302263 250889569 56889696 982493186 372322538 813384012 889368270 839853358 988742082 731175627 913102028 317908486 807824181 465795961 400004883 874141422 819588841 530369360 891565094 683182745 572462321 385387855 234994620 532575623 461946671 387087509 379884062 317690014 792479735 364773735 231999645 394412720 882482622 582017214 56477660 646245515 851344016 539934886 12948224 892666896 153875133 509340269 122425057 781043717 343169986 247881803 426244656 461529512 514855152 383508161 617276849 272342034 348673951 896840222 221630858 66243363 547986406 317027077 819653269 981546992 109855391 413776309 114113416 55729317 146371702 610894505 780370859 39300346 987448185 365974334 236721795 404707009 371889902 926062691 356799407 526714471 753971809 840151678 217635533 724898170 745049140 85899270 406992803 147027932 362311272 209298575 513231903 415356298 477000287 969975727 599537732 992550462 594606475 900499702 495633269 463836134 59011433 890057147 359461222 621127314 827813598 182997229 387867113 127487784 80922147 66788065 487727974 761826013 919126889 845007567 284767272 332836984 753140720 96215273 709876302 26249247 273847228 6962734 935960997 484075726 414704862 18263297 188414588 934090139 997938720 5885815 276638623 476713520 29383339 973991918 748381100 402106649 912231416 323101397 362347913 628191799 68622016 713947381 326062773 225437533 880696899 715065944 330999611 875835336 963896466 98216261 972349108 615705479 585152230 384180124 531243181 499640675 410548727 525289925 619258967 473767387 963118196 413442841 223202585 463333145 308289521 137252269 150535085 609571375 134173539 110844730 181851067 890990290 599683690 473215179 638081358 667467070 477169551 273733815 899211410 557262016 315563833 698160575 640410634 341271630 460015855 243161454 706395423 299691992 139394915 430179765 82476362 155177653 79938627 968792162 735880774 462111610 303559101 782539407 534566884 932129746 488483716 614095481 561119615 280045129 445404525 140271483 109411968 677723741 366414232 367560154 720704087 218119962 392179716 438821071 52575708 523075551 545443164 902249320 787754220 887693556 818528489 53071552 668177678 694471097 754352054 228764231 332301591 421218405 667868416 471892645 439883278 108605738 983014306 628749363 288083435 574628193 82694471 489940583 143738495 52957348 527331084 316532133 913544269 893658028 907227851 391739099 588260524 355482062 255994512 908345652 562515298 244368437 46121106 283614049 547639517 426296733 304863482 796232023 310615367 817963582 21242423 297919515 139523015 412683031 316616231 246072702 794161936 600534106 573804654 619100316 910287171 858865916 559840974 650632067 957798275 80423803 750794658 956967196 64002182 153999814 975520575 24599468 97397320 241325041 2617838 969559383 186965797 243708596 50821113 315296727 547894083 9179953 928778283 450692562 267453974 759060640 321707880 216578185 650470860 828802506 158821066 864729068 984886779 913724431 602463337 263222417 451275557 878512155 448461375 566662166 49842258 456186311 705065205 778445873 655686107 725825098 744070966 589027695 892431336 49610913 333338413 750423929 873325670 562323676 631213974 491425960 307550683 346203599 75686894 561148210 563559681 746292997 977501758 993484585 960515550 561889371 94644619 94073320 75171598 78084084 406399918 267274276 696586664 551661397 575814119 74499064 505061953 507143429 152222732 28846147 395099188 837970483 370935961 832414429 789828607 756083429 97005913 951619591 931263465 650680593 45411745 153980764 415741357 413834648 119656992 814203771 308510426 616761923 608913035 868204971 152483951 470179784 195837804 630276183 30854935 716237562 383624848 586282975 405633916 405662234 490368178 337967810 857420700 766146953 688940468 932809622 239050934 827768253 646696256 74473218 960643369 394458593 232006408 711803481 897109353 153741351 362917906 457024181 689898579 743414895 771701245 814316102 26622737 877868810 740450994 544609347 159019156 326938461 287926214 982018474 773221277 228244058 821241396 765486134 807336256 194346680 135431452 898676744 940716282 599995199 655539530 893214653 251478260 27144065 999522398 515160940 418550784 158985258 461138689 282433659 498001130 265397679 796901611 778055293 849154048 817317020 502886985 694753761 5024118 198814576 1535456 519417216 583787173 293280927 46229876 358321471 530343018 662941028 774555254 184891581 774658844 493938905 895008934 602844950 552294493 402388915 793383068 510750385 567919676 249903045 541442331 774997636 460675001 154391377 147805019 757008591 267193034 552737514 896868028 537595457 459417012 469165947 47899502 578858957 256590043 430909422 384728817 647744840 413044032 78809273 274801117 132943795 651176132 612920285 620883467 527671659 666721418 153607651 785253155 108654996 144594750 730140687 480059200 582017459 715429041 252071599 23947967 229788643 837816735 873915215 30128539 743135091 150962321 410385889 565484681 761067663 536142701 318563052 875454709 920527585 134672616 511748204 992174770 870419754 80132561 271179920 258916270 751934641 446405 280930259 976317455 918948645 159643323 327177213 22438348 509395495 162184095 424421563 723482323 5441307 765898732 445344079 915569764 485990141 669388884 175477684 784458125 533358734 651537425 778757352 111681373 707364436 803824924 300300002 318714051 913690729 949058181 618745141 565385292 14517959 86599157 985339788 496130998 211709983 825840813 110642892 320192479 263674380 921490539 392053797 381262229 814784654 972597193 921004738 145290257 261325628 506896215 58502049 79148056 145318086 795221016 105529459 139828842 614036924 270537423 226103094 847025229 81211510 808432354 742698115 98501009 9407599 928858475 423004291 610738716 37678444 958217918 731778849 9627570 511739310 455222296 102412481 192554644 179565564 596123881 398685897 67205326 270769924 830635426 641248859 469802423 439673128 232457274 848466023 273854578 206399013 332115001 202861874 613189218 684346305 416439726 551095377 532622709 677206559 482109981 420073112 52435563 468325561 986433435 670317983 639726422 508312533 28236895 590653881 344055907 676762348 945990135 475752773 934469517 433029078 516774741 724570795 260806017 727336930 974794649 109095805 674831354 130646640 780938381 187376293 809589669 113714342 203509898 625707624 773810333 842495286 748978520 947791430 434699754 574883948 110285520 819334929 384311412 538940164 575983824 330110756 724571136 456504511 665904717 820442181 39281645 91036922 154520579 652293385 344004998 489886780 449872505 440870547 270117597 839300993 452841482 762505792 844714062 611398566 936525144 799186539 480566949 689115365 950388924 696223128 758551130 49733484 551948402 385073874 591300196 637130628 651218809 604937822 920555582 859454153 12328164 53710173 634078203 325811142 934832591 699381689 78217764 130467286 673001830 972074344 382479178 207274824 256258095 590239327 127499371 839433924 503952772 418588788 868907981 276655723 387879106 837473390 326943083 41452917 177447667 82604656 49236794 431321380 733282158 298005330 581744708 826923762 27850366 491958488 56690841 359176310 337571913 506458760 229396460 868894513 241345742 297559813 997531090 919929427 871156064 932940414 311308323 18965821 509222604 658686374 43451658 774998889 10950992 630328937 225931425 910075780 538665356 106829408 867679882 666232305 428796885 922320885 484591289 331098753 231580704 507463788 203507616 611211287 267643273 663897635 926690452 492461613 199966804 653493798 995397425 738755213 676742877 948020901 422365362 470755291 235807391 869784331 541221590 231583645 779042002 572897464 839716069 47724167 222293681 159731301 204853985 441206554 279433764 318256902 194583679 158797843 390053851 922631636 16340635 866012986 165261074 178698584 132237649 323191606 453199462 98493964 304135547 30616875 936413700 598925053 836087961 274426732 489758518 400896345 724475532 943821397 308937134 834567140 60950803 721410045 166576847 630959576 815786532 796324259 433910412 480915647 553830560 19214070 340927769 818131661 148774426 713552539 393622592 536921185 491613082 718426838 780247677 53356532 86800839 52333391 968874298 212845393 879829442 429358173 953683569 803982071 57770785 530692677 92084296 189391005 309341432 379005040 10960129 872731309 208384171 948676889 302967157 141414014 324161625 891645998 940895715 199906705 273517747 747096626 727832955 516255948 955728765 252743047 345946060 445592316 122588776 175667017 739986417 84500851 796109329 877446401 337600911 229696991 548008507 802786924 765102230 165533480 852888242 761687844 563665142 375896937 338958613 732234147 200398119 72103656 999297555 743330706 901651456 985147553 166594124 503526184 11020913 710380030 2101379 184157622 570650074 323264443 888570720 257262861 949397598 82698617 378435025 587572907 231284939 667297492 792884027 451218393 182592534 286762732 519035925 303543180 130070353 992598089 525194603 940038474 540810310 353431732 783024810 784926822 200637216 93559625 569276826 305239713 766922793 755659798 549584883 406551987 201591929 231176472 922160847 73873500 499874489 485975924 56732090 903499283 942807912 67135729 587288993 495865917 94603325 569907672 467915144 65383333 427760977 780371090 391725958 490985014 795082401 436932643 564913421 791172028 305336503 406723974 373284231 591305824 979087622 181050553 844794680 674801834 394935133 591197136 526808346 279303308 166896173 592067279 255130132 838396407 397388781 507832619 832212028 491018635 602781635 155994378 980731604 734094581 314075995 760261272 179326917 620999056 754796602 440272854 279850737 43166002 125841779 761588803 781096352 913549073 727559129 286216738 491578531 436546795 707527257 595794546 941628447 784779928 230135882 80658747 360117869 365198025 9794040 33021623 570814601 362415127 241468705 317604501 917434860 949088941 808381760 924288890 504626758 448440619 36213321 670453054 695007465 930833516 751249722 566438314 314664716 123852777 67388296 562595689 820107280 181363178 346475045 407077301 360946085 49296047 618485419 135227564 161233430 227274114 137069293 229912524 438351564 210748065 538813064 389315181 199539666 694828920 280805314 48549452 507764569 876967146 777205116 970003861 234252891 91528123 132737762 96044496 617952472 992259789 384174442 419947116 757877005 362713308 88452516 680706077 849429556 219433567 240557284 753273751 141432474 236542752 394497972 486182529 679291515 768179279 422675060 242733523 791416031 741119775 969100672 142207400 594262617 192512562 749017602 42096128 997148379 367485481 879494197 309635312 59886085 503738341 419026229 422142143 753773986 62287409 166968158 316208999 332954230 613721435 599889906 154305250 574807895 488067637 646864942 524277710 66848017 376356893 214864958 390979766 693106796 939511479 904733840 659206421 388327002 546677504 470976160 83092714 695528152 712253842 296310578 334902376 986599097 19444231 604440276 610949219 339393194 724741814 657584177 773253488 603324262 594716806 811993217 855117673 231854795 143472665 835520104 591296545 432342989 949681672 372408007 419227706 993536103 926182095 661074274 898537788 123011623 57527011 734110535 618039276 296189939 447086167 488507283 382417294 74400137 123905636 486965208 845598741 84900636 72808820 848280123 448413291 553170390 984911751 311217181 825160665 543892055 429925123 204817929 789106544 209683118 777276361 981101435 775415776 481346428 57457858 689458127 881821698 435383723 876950186 404860695 902141067 261236360 728758893 945401481 865381703 190955427 234477019 847994460 934961913 68418951 283421749 170284880 512893590 743715862 445907516 254486087 435715690 420959502 490611315 808375936 318824098 972145810 236752802 38787737 708522777 117922941 867918467 487012605 535569872 804996236 315618712 358983270 239499183 864296304 618575125 515030918 265834215 556861511 532827726 802223034 586772950 342357705 504248858 91609233 776652297 372627007 240672056 625542612 690608574 731726355 367238148 138027042 265275472 743691047 509732768 407130000 671122476 180682748 602146161 575118724 939401407 56346918 978658350 864498600 590710305 749416321 836593057 238942673 308751593 467404372 532514231 637002049 930672925 202826138 217129820 501288666 833816487 214745462 370597665 782975439 138975718 955046483 838246210 118758520 832346544 218668182 797629246 322659170 347229362 216038175 309952441 605157221 888566089 897683754 203277678 82206686 365802553 890674748 89836082 136022064 909937528 598040785 846725592 463649020 619552394 197219982 747126680 610343753 355325685 974936975 799722087 184062645 926752022 561578521 6798756 105529514 828465148 277461245 988525730 769326528 961192397 552752821 92604159 253244698 234624403 303120872 519371155 116965598 192507855 498442260 627968075 245200179 321255050 408320615 270851424 870858798 107234292 318481979 800940403 878893988 957571038 721453903 461227189 752785277 383918580 366969286 793134878 81686380 708550259 915659252 222303536 411199740 173547253 333474364 581750977 970490244 562347942 312910991 252021207 694822702 765756153 532551364 209830906 765097627 5370232 143959067 896952929 952947404 37651197 954278718 194826283 588207481 377269385 682474044 794791907 254292773 667235308 416346200 987484001 178243616 710609410 278402612 355173395 576087480 205031131 501080383 835786215 670647409 739529584 452728577 336467097 778583531 761058363 962941543 847750833 905231299 330746309 498173775 436863475 712746030 980515203 14651353 919202287 171788486 166501624 200679303 811067505 726301240 46670549 431222792 958492863 969524642 143385112 623977781 811192504 83545854 413285834 555596994 595894519 535531880 388585126 775018756 896249362 859582933 320805849 134269114 891798219 348497018 546934231 554130749 236351529 423453010 638598678 600521955 388507085 839475851 145713655 971405650 404222186 679188883 703936850 164728633 924468062 637412868 31367245 131944400 919352479 928893842 258675479 701780445 650877750 652450444 220331818 430765552 323369242 548605988 845951987 840775593 557735270 268959382 93752406 508044274 374063136 481291140 638092355 769728925 11346325 699702905 533451061 276251518 445888819 397287261 992822621 790245172 984116822 449481240 958481969 68139476 342150410 294247686 672253784 555826975 45913392 358794164 49951860 612150836 994790732 212339223 306356056 528685339 212588018 14373830 562244866 289149084 781979442 78458986 660539724 954196799 807841867 224952761 51749633 934100169 438273024 528342790 136885431 722820322 704959172 864446493 822693862 200237786 893464190 445214520 449572416 807269023 320580086 918684084 594953543 748840981 375620825 223081437 386938768 568853824 602327174 734164394 451974977 874640469 889761218 482522890 172903752 612876627 723151282 466378312 376042052 648564724 894867763 292827392 177814884 616197820 526863657 703079409 118858006 326087269 150606872 799818908 506525775 969171377 506904172 127356083 129169182 922403763 713712109 331064810 14424883 90867314 383873321 971154746 24960400 104584369 323554061 763591002 451856615 377034119 584309385 472922475 553615607 824175697 796053797 526438095 550389542 74147519 919830767 440519413 716887934 888737869 614295275 182757690 281160354 720726389 50185458 333062516 967290337 277624588 932482109 843418147 916528210 636627636 142262390 413160629 174665786 830357572 924386001 533825283 9771276 684758335 963091848 453881960 280484189 141127656 334428957 519256314 969264620 663349771 654046479 157888882 946661486 707556465 589409851 665967958 536426366 370226299 245898791 533014886 227510872 255798683 959896078 417601829 65358971 902210623 798699525 557480587 942034216 469767605 580378832 459055476 120888262 634490977 47682592 851798293 554146716 289425234 867756747 546721295 787041196 492652681 605144014 908823958 443945326 427760753 638047965 133445942 703869009 696980911 869451931 470535988 16242542 900476797 712283482 890207663 49122436 8127696 890913203 159173728 396219660 368058812 785348344 513025832 370833245 358783217 359361116 169213303 160298043 494088005 83823541 619235767 788605362 362410560 859066190 361807392 885812343 542980024 921260062 310661839 529877552 66072769 952313435 14168009 621918342 377184397 150881250 53432361 182407377 623258389 839326460 990495784 516729141 817276640 385783135 892195771 503545858 461258593 455583227 341592809 125875297 26999808 456793397 312630757 938902878 121739824 520100569 914229020 276429024 370623911 200483783 341093883 245013167 246094720 5067511 255965011 934088841 550152146 452623281 503990600 366739524 675952790 398310635 204234838 825158205 150377592 189638391 78877563 918970604 816168498 911047083 269299992 650638808 970397915 152629594 316707462 56024557 761516628 753010102 672241594 792089981 968147217 385413501 569372292 825992907 683746320 475123313 380548897 287934363 765909246 320883957 887771238 511867312 114602981 175969511 886841572 296840822 948317877 905575271 525279565 450027936 309481216 853050270 790356216 893768462 307827066 807590063 701048187 455857256 956798256 55842887 333162501 669257948 459178399 754651976 256730043 611612560 859268475 156302582 63173010 331448155 800945284 215761736 449080183 822445795 543117358 549197412 733048580 844377357 656913537 940542670 914701681 677647557 834358945 855028829 665457545 673549224 845026394 973234881 657622570 495133990 209923734 841110193 380121670 813550691 639952409 571755594 891961961 738157064 930554661 78904074 156300516 347476822 540413265 785423317 622382651 929047159 277230829 749224175 855260595 935311878 841362704 51381044 766709547 865384765 705909588 207761176 246785018 782289516 941456425 442520544 590978303 683679017 689046654 300671144 260866512 371239914 400256528 5703823 130708274 709337972 674063547 512996712 172432616 343852604 461024641 427487928 639865945 195224789 112898577 731289497 233817003 145291678 658130671 861117147 339415425 591146270 552747774 731497163 168313437 459401192 928117945 374770513 113947566 265446842 720004146 865762434 56075251 151695389 250017299 690413361 254446026 213578503 549919083 70305372 548799317 918491050 430566243 913629876 338228930 893695210 242809219 596213403 310923384 921883924 318957399 72614432 599097498 840899060 481553364 225988105 327593728 79208813 653402105 263247922 938512365 532164662 148963293 902806313 957666937 307209313 296549523 932966988 628178087 261475162 781349662 828903350 420082286 428563536 2510330 57209044 336901296 973743004 43707859 791479824 953836769 389167525 965788211 261907456 865960886 784003306 49235317 343268812 555196129 443727556 811715401 223515158 269844142 929109934 591219311 379369348 149116366 978693499 537575491 491270193 295777024 54978465 944976373 178592937 807371043 271267120 345530697 683603042 384632050 735815087 215914206 326876289 151501524 807186126 518157013 461848692 781478099 660430285 704703399 199607946 60123354 34994350 651196222 124456178 671648530 355446481 225360429 478681034 383934400 665198432 696549714 27189934 703319900 825432466 789362491 933447274 332593931 655990474 378093141 498190086 525666409 102823180 154288213 733077401 89864294 720855651 19589455 186115825 809890991 11189589 699444233 690979819 504894205 429808208 120208180 397772704 700821492 861721138 998439853 288964162 334985606 795383560 761126255 74249107 958836904 318226477 980974718 492568570 693111997 587677868 176603890 560112038 392423977 862405951 847587225 558975134 547986618 200721044 878290626 638899476 965386703 620520554 967234622 250933520 421647449 331457412 335103536 685007692 302894224 460018373 81456131 375592281 169073918 33036469 476001265 953403613 966860292 690599461 223322575 382648345 514593036 778553214 214022148 452925693 885356096 322410415 93056482 834439965 868133995 778914084 586181242 696418081 987863988 179322967 373070668 286307960 714827286 757965356 857974678 750522656 524248262 241902643 968153667 113885676 160528593 159563657 636082741 32599734 272195898 416139408 968060920 28883168 167821028 385606734 270399894 160287324 986072144 688690299 277144960 49354098 514529792 553160951 642666566 242245338 31176638 275478194 742043951 515687447 573053207 892369664 484853682 642011 407423593 798806860 720348786 330404839 118084785 727958382 560033277 313614093 100550377 491839997 899850319 819251904 828443239 141022632 286991131 221229587 853016885 494445616 578642055 667712083 551501153 815657943 653906105 574299356 298297041 716087959 976091126 589709765 589493677 986323853 640831167 702971569 676152981 540789928 984779353 922799702 879239286 95541400 572424186 126414097 455387481 896506950 23587554 642605362 307784710 524928738 86837558 814880672 944132837 893616916 687613267 911281217 16042326 157091276 671865061 601255849 449200142 725437876 87672906 761702762 551101815 423834648 492307812 538844242 653710757 42689652 967269414 420291418 663492913 516359992 752738083 630444772 233058439 965809043 712639058 366713670 26452072 182064495 995371347 333021401 112270148 574904096 697250708 807950611 183756561 579167660 363394803 640978496 734494582 910133953 569364028 67666870 903797495 120835708 423646791 466086372 988003445 788910103 193860973 218907830 243203414 217766360 622654422 156518459 560809855 960162556 632301290 962404294 908365870 88736242 583118655 666363225 210799541 843682015 491700461 376689871 360488705 880816840 101108305 5810757 98894238 566167472 977897857 10342256 584535762 66119586 133170641 878841901 188259252 791877441 879447187 64267434 414141509 481127409 461437082 586852628 360572406 563516423 66752823 205814004 217342044 952479188 852187682 83208311 611763105 942257467 488598411 939035283 586705743 921396305 246773617 533011917 778151504 950602466 410833402 648090539 700187993 339727858 268664670 545477743 163277611 203166301 854331456 793648216 597962636 871870403 672294283 817485485 881448283 379339172 30919112 325152929 326412482 933061713 679566687 169237897 430743587 103262270 179077851 883143171 97166772 9553577 479033726 585045285 553507736 252716026 868626684 571277506 493658559 810396462 925169256 792711313 762360046 814139369 416882695 327867680 930019690 999245338 387400689 100734754 615296987 630206601 912765441 69408739 564986883 59982921 404248460 582208891 496555935 117044358 807250696 144235142 157211507 319964717 338374853 231193114 369034818 181422923 981085495 689165261 229344294 316281350 458691961 860970845 96272103 466853173 137574971 181294331 590185742 56000732 264178665 955083727 599565664 157048264 778644174 309060698 764383988 333790908 230965515 709625364 671444304 893812179 137972819 583979172 313762769 569756526 159074737 847775307 978018895 963872215 571073984 577028564 8573500 249878026 857259780 260150454 855764818 965159399 331021721 196493662 386032742 401707410 78318454 795514688 632915795 154642200 372132252 297344161 479882468 231509746 322019254 861598642 136428050 972498617 424888016 735165089 633393603 985128365 303036604 547633513 951107549 491486180 607014241 562930116 898402191 818857141 167807692 930596059 932891530 644440829 335070692 862707213 269030342 298517124 257958397 199148606 600090128 160261019 669118008 312180097 481886594 641367587 854218393 519167045 992993177 105445319 474889895 190862111 226509505 764063787 604800121 811503185 702770076 305087452 342819727 432360504 583969183 990193467 556649455 604729661 816261493 601268491 902571100 590812231 109438792 849304983 432532771 483433624 757292953 439156598 620891600 300975594 748899791 92207023 619809588 714074746 210406761 909104483 94587626 468186812 183467009 156036091 526878567 232057266 927396606 364854145 617054308 690642792 832981782 737131929 700821700 151332033 99492364 218726805 479004795 87029922 284931519 823079637 42683103 388960207 308119491 677871339 809361797 431246115 807693864 558756228 760865711 751803586 879029881 125919682 350882347 648193097 839898290 949517716 167775838 452702366 155113456 690004477 387998262 35975883 131220090 50114856 692194983 488867061 580002863 672317919 547841661 885507347 441848400 723443349 118768904 39195777 157444481 897077509 256866762 347170883 217248130 56185441 683585639 555215100 556973831 968327818 369218542 283689517 887161815 863793492 837474387 498320728 962017565 441196192 206047086 721289681 226927299 297656483 699920666 379394028 16408347 374997830 825827686 129132221 939166414 121627990 13448922 243030086 375206543 633496214 258194275 560598853 651570771 108424151 904980677 662504944 662422005 471378943 876537617 277874492 234106601 356541426 255269672 14986410 975817626 803480215 760992256 285065400 215001254 519499383 252551122 91570523 435166063 80969689 965536422 613174319 830376968 701379759 961508368 886903860 39792179 222323527 438711583 46459387 433323862 694170845 348076286 648702024 330931796 761503312 611074284 565223380 982477585 459064861 134958223 326773431 836865380 638366688 65952954 593976547 825250390 834647253 61040391 827743797 574172304 630590470 944665352 123096752 9792385 163539725 534992105 789237486 15173968 240037606 597531124 684406084 31509499 460128574 865215600 43481906 164534077 516381040 440383530 748585038 778865212 100475341 710400935 160539388 885592461 686666085 578549185 293494272 571748572 964550620 201407450 316685122 468569092 689323694 180625344 719122685 200329512 123082303 463136924 800949431 701733047 416076935 132156479 917819520 77528184 988098499 969929232 492864060 844513376 12052380 82165524 409423387 625513335 900758365 554359646 789809393 110988440 55341638 711347251 376576155 234304364 888261550 518248462 302016513 442555433 376765578 41873797 617816087 565724161 634907487 378356108 95022614 31183571 978174041 992022379 239262856 451715078 587554515 905945840 122705641 636723460 999980842 770614438 655510876 156432275 452989677 711478559 38410828 840651820 735406360 928482747 344219606 26130973 284876463 717752619 923898487 946168895 555503317 80843274 629039688 805630851 231879729 30369475 969408956 289543771 593833287 382686716 635183187 664722784 732027708 984248195 842710681 617653181 231679310 970405122 324978146 233586749 497348595 459410974 322045030 821613075 178767354 80223831 381321444 657106201 512002301 699035592 234012682 918450771 431999077 298070865 320350127 989253054 948131696 826898787 740910050 831282295 539187338 779833983 541599094 750053306 710515654 341693592 629648876 392479595 732365686 578563818 663935346 526767319 91938479 862125773 606002774 914836334 371600757 360995305 384179805 648425706 692390343 458821322 209722708 629207849 727762320 69162371 18845687 598721183 108132015 441462237 919863982 913265835 553732166 38364054 161052123 988931883 793262745 64310637 179960024 721011946 489993179 582989749 500693521 377139546 20423311 881506151 785004810 911985961 46207484 30240225 407526490 814116814 354349584 911153980 257973775 526852569 182733993 370080320 304021063 306735952 928013108 385514326 410964322 197523490 919687932 981912669 755980447 959082988 359460734 180265613 255071133 224838777 465393942 387355597 896151803 555538716 652917607 348731819 287536880 971351141 964207854 718498766 931348181 154261213 829305323 768048139 490663658 841796101 655352140 953841112 771355369 11195984 146630106 66612468 312461409 745314719 804446590 634438425 574261219 557637897 49562241 182326103 507778070 823323189 154723182 828837075 133005044 426736779 80489341 832580194 617947690 107004067 453165483 119026969 958539730 80869988 457721342 302638718 744259870 364957867 654191566 645385540 542131272 925873768 158384745 931251102 72569275 809341117 389132425 248017989 668963897 556958589 758401517 722095375 400940161 678118783 519422763 812128971 66754630 842790716 321690055 948189404 602755598 579646733 855991082 636070340 132440368 266130827 504115013 517455073 668546020 534804243 544986329 574507659 624087114 646215440 243486290 923794138 531987445 670715682 326088664 541131866 948665352 789912180 971280405 829417841 54981201 167326122 484812702 668627892 211058680 770133780 870966353 681751365 681231465 165446931 466030934 367984419 637176703 483056229 748519099 565795010 862391017 320142187 513981220 341520619 85842759 238412751 416785510 48113488 834418821 682455846 75988170 104292972 762135814 443265624 992702614 985856914 986640091 776075684 587366055 792560392 748059001 675403442 212020158 119004059 532593745 123969092 619623384 381515517 712414921 573731278 656359247 25538643 706211649 94271512 861493434 105021690 836892304 410061102 930872613 774070303 541246044 807887360 778557047 10148466 208474605 562197295 362523537 158648191 409938071 56439343 407204125 802557820 33012617 883252896 996330167 304187588 112699047 656878496 475511968 567604380 772054852 503492479 62287433 442925466 755856442 147294320 156329855 892584126 751722898 903359071 711362758 697034573 767094586 592708420 100833444 607450972 618714447 430283367 398695927 402135902 230247455 412987686 496673903 155298930 67576918 617248338 794841067 333692773 329433081 922380611 91552326 707966679 615035625 743149562 289669940 636715567 292263697 404596920 196598399 167719306 313559004 85671566 479772492 599235412 934441841 254353644 112104789 652450814 966826702 353248565 54394421 944453054 840325200 542444629 131045359 127107820 218026144 609668343 807802494 414827958 435575465 499116162 580026035 321940274 67212678 344081137 392265813 932236349 586562111 510411899 818376728 673991033 479946214 736923528 580894052 158685295 77261584 764118730 975165902 824283032 457818833 255640825 437241499 421913005 185851876 854667017 22570831 235292649 143518472 574469394 532782962 310934746 176867299 771651436 952730154 960968285 234786806 460932141 612065408 685469268 918534138 929659096 507707318 904507765 717001185 952839531 164561016 142125534 806318873 859033418 136107512 720397045 854787614 732026141 625037317 27887837 318530889 878879761 874245277 631187523 864451335 456983079 729059219 838029987 818466416 198361790 750546234 741628629 293680408 100611502 927501580 105110827 942552598 222871926 517982382 464050104 756648537 46849251 715802412 498274519 663173613 245667075 751710563 831382669 796222641 325250722 811984375 668469291 554473957 346254688 283087091 262701861 811153065 459872040 990071236 593490359 136535626 431988577 859233586 811364791 678429258 909067443 783064340 47824100 82915922 969829333 440776096 248112047 154103913 840470369 353923831 183825512 572855859 594527311 291255000 147126827 879947562 530299024 553079033 567616422 690698758 919171173 324092984 568806007 859437263 184249485 854156557 579989900 500873971 783304004 861379190 48042567 41968605 371634986 516693933 674018684 779045121 261163290 224874169 920816736 235324949 154861704 778164405 873387296 904496495 872594108 662828567 149200525 360827732 606025390 429878422 895969405 431863182 844554077 503780730 201131602 707416476 390753433 640068185 140738494 978275853 62014312 529536303 907340810 588599921 169890957 750679137 894959572 480684049 30913509 383046543 236536854 174420711 811408685 733243237 377291539 72672821 222019442 819582965 971658736 196316573 995242834 355697840 715207479 302752845 76716048 123784508 15595479 869514788 558596460 457298278 490561637 211299181 103829128 609415428 955941721 714354875 851106252 439049766 427001516 448627416 626380209 180571545 367330771 730720354 893849478 681434392 932442927 148702672 108879446 330678776 890215542 95354023 743094904 938522450 889079112 528563558 710476156 384751687 6986203 388243305 629814816 132416184 840208656 740043049 198788911 661297166 653938867 760964666 13552083 839059894 492939067 658801812 172830519 128668557 965849783 632698503 252199665 250431223 862864842 300494702 179705368 398634924 293469453 736153986 214876580 804504379 324435853 184317932 327832068 591349 900565257 736171863 413140329 612542653 657542355 318560780 814251213 323498841 94234969 476210594 698520924 6309291 321997759 170545744 867254490 937390679 47067201 995465253 220607488 35944728 382373151 863622805 249008841 470299083 845912444 647170708 447035779 204772925 158123887 595777489 553293383 571074476 189293962 770626555 493099793 39724550 428699870 859398711 297849177 349122162 733699722 745109881 335901466 918178489 785657417 137003403 334515828 988879083 577078149 594523668 571301475 475608686 475425871 890893904 952670154 787813760 865312467 543600081 723760611 714261782 653556778 877692265 89472866 63577475 183104548 875882823 757202048 157711814 903133398 184289049 802289342 518771462 168350204 247008389 113330517 524572714 972209144 628729997 961902533 535235174 580052820 336839776 404461697 839175171 924306400 794448584 576369571 16660598 37146316 112090898 5638801 251992887 219865695 892412047 930394729 526460201 286092955 513942034 337754435 371600265 136627051 483393861 180330282 705880344 34456924 729765394 260457200 302125278 593378495 450617726 180032694 288223740 720488241 146519618 590185172 426032442 495298004 443107948 193764481 818977221 727842113 22736181 913724335 306769250 475544360 763388240 98925606 110244695 217536836 401997129 749881808 384118443 102497550 554018170 708269611 793602337 975949233 351578633 970421383 226230106 42902576 570612627 258677928 478536537 41165268 716952711 630844514 702091348 875471035 289193229 403575493 433479329 877396841 122568095 438720182 52971059 191151410 677252530 27681048 842588383 336803495 322413863 643765120 972557127 985467469 293792988 522744441 376472309 971433637 813431768 765251575 623364153 987763891 940738480 243950040 459858714 501943772 52680791 908909792 187169826 867064236 494547756 418105071 155956403 59825851 449145408 315218370 314672220 509481840 606234136 543464303 664027160 492109511 197042189 215633589 342281051 444214252 153950052 51303854 458349734 888188844 421962707 394445430 130586651 888328661 419188632 510248759 163449501 514067814 354648239 848120938 594490214 87608819 599152801 829282209 157724693 409324677 931535385 168194524 495453332 776156797 211516246 873955491 246691098 663229510 150911925 716987799 559312537 180375469 665212143 962521007 660792830 173681388 507937168 605480644 652589112 192929423 543558433 397380866 582252830 507498945 218395686 815106651 17684505 470996868 705711230 927883390 958564818 499920797 575022776 659835370 763388598 641432990 855384345 821966261 871420944 997380793 905198474 338784495 867153584 775789860 347996746 476938325 911900230 181525910 206470283 970042075 516975598 41685781 120993079 622241547 663788609 239963737 115393910 768087633 249878945 732983545 23510804 791995946 512724714 895596574 606560043 635889294 786229388 214858809 988924185 553788531 889234212 292408110 587202772 258752706 399552507 48793859 408540620 713160893 483350509 353466508 955792399 572737586 704320603 37848283 240982234 376179253 685520891 839734126 629892889 495732081 665919890 977144211 30614008 312622564 2155432 865823779 671108442 463552517 513837332 18523362 846996707 302381899 29770499 697600735 243093913 599358373 767596754 653733165 914098715 834536121 748648937 114744005 27296390 818105238 571892543 174609868 417258837 123838578 381325466 154534095 864959598 446767060 246662871 490865536 381221579 850200552 575326219 258768322 837912654 945398459 259040714 528678207 685966774 175122285 662564402 867677452 227211904 930921773 344117637 528553103 944580242 735019819 515648654 727543849 602439226 537433087 365075848 774019828 430361427 147329679 880958681 659420125 810042017 469630679 84442052 38666695 602982248 845705445 127331162 314189371 714523459 658861552 943312890 886404799 899251604 462140209 915610802 353792936 774365922 490655995 113485094 714611328 264815483 262831742 974495958 931014053 755593950 867807203 821038738 895270476 199261727 121445667 270365269 575618828 563232038 420390755 308253115 993530723 865360025 822108798 626244971 319012934 463637054 23769698 841890812 873872524 664352694 601999407 151781196 669915360 914975792 761590779 964527249 908095751 564216301 34400093 191885565 297233684 469883423 176055272 371787264 471071534 195280624 96757378 316646788 141261764 792405291 912934284 776960128 964135348 664139281 548678466 319884862 770770360 509842814 290103097 816100983 533857703 144830756 671408804 680917003 863632547 544934256 851307015 568073784 232720260 410936996 396193979 818179955 575783505 90358863 615054365 754590447 85580304 928275645 240259570 714196248 1778633 596100834 653285951 403702145 470448189 829972065 898571188 476171707 742038761 990286744 356490629 217933471 364289504 668381983 17333039 733914141 39365823 512529355 50005207 446499797 740207407 678283779 626613500 315213322 885896333 423993190 60065345 386601474 850867225 829679932 985416618 661825234 168070224 555906592 974454370 865878875 694726930 803727490 753174400 116899766 240260683 527122204 68589566 586447872 875614228 651089874 533162638 826747662 889924763 795367939 843420661 146196391 761065817 126789206 799732073 270177820 731478594 906072546 350351578 484542925 463285892 899320392 825443640 111345115 382533465 847561768 734535227 106343955 929773061 367621331 376568902 479778018 402392864 86284093 871962247 807031682 592726832 448819363 279074918 342227517 924324742 744023070 798099143 8013953 261725074 469542086 281627785 677152966 712798675 582801856 310089906 309085809 621376283 450428062 280324431 420999578 276522031 850974824 674705154 509336393 837176940 348157885 222481441 661994289 678743175 419507993 170223530 957710496 824458354 112079371 587404477 510171356 594321026 853645722 523488845 961535870 693333218 165513585 728568851 383898975 160916405 538880881 756408573 156163418 531157180 941912819 521467077 399297128 850457248 574428588 617286185 31099848 257210872 927906204 93643847 25785820 858494154 797205327 229980544 403832987 945790721 991787465 730013388 747743579 863677019 273935949 759879140 619957761 974358656 279236995 812474250 912475245 155579279 355334528 994209990 32958271 295862039 849324301 266138245 413572309 315063862 850621301 642558960 554320010 175432730 990974465 664895224 192367541 479069309 404413901 154003655 767056748 363066201 406412295 770527448 676186345 222853203 393895514 938804457 96573322 905384392 789211113 887831924 972737713 66819569 540748014 835671053 272171654 190305445 364886678 586749163 905144587 304711190 319663793 573663095 986073383 68683528 17687577 81109225 558533076 734329518 837592937 831465185 636939878 900425985 409304422 655751076 113382485 140893663 824856983 803059892 220225723 127155087 530526095 881918214 337504345 972549540 665573489 707304474 626317103 67877664 680151693 902038749 328276892 218993677 789653222 664386392 451470429 307972617 835083534 777649722 449569630 944289264 134390500 462527128 949797984 404899082 469286133 856380452 424098634 45823297 141017832 610740021 317314118 6775757 960825942 832642835 736060832 640793905 234071311 168200610 898667891 586118520 979699452 917233399 638301984 2961883 236452081 561306515 57740799 480769717 902738598 474431681 350633860 434777355 316532695 882449701 585638431 742931048 473599032 94474251 610751313 236308929 786527984 470934613 53000698 792051828 76145002 491298996 733159003 969155650 865990042 733618095 770997370 686964596 418325830 867739433 81446115 344864216 397541521 839256072 586335510 288200737 141134843 310474898 222955419 624524262 740173803 202175333 348598090 33238367 273084315 866863281 645673110 172327827 58569407 103513396 76608971 381100209 8455845 36712162 60754892 766346407 314309923 524919236 646298990 450364992 363531173 670981302 241268204 333175380 523152143 772686306 283266346 465362951 333033732 431983248 893590209 732529004 357631363 945770475 875041862 58730720 394003310 62262845 783153624 540735942 246747856 267822934 570528222 677817660 631780552 207264931 16264697 552031832 652193944 548966762 915781128 596884275 290745691 809187714 232471061 769879049 797316659 264462591 569942076 741156606 851905492 491693484 400454123 650728356 711144015 276511090 10384540 573501014 690970605 108168583 530762234 793299519 396387633 891333275 323359863 961908221 558757539 5241159 540279357 517208720 935628457 157536013 444810330 263523280 420828442 962726926 67925162 992742911 430729593 8251901 881321817 890855431 653637466 721182893 575889602 139064955 27933781 828158207 732453741 350688134 313123134 239087018 711405974 794091011 936281954 231559653 291546613 855175477 939382217 976878765 425272058 444550638 540174306 365149740 342100238 171948803 223133590 809167289 576918302 705447842 676640345 637712529 55509629 12982904 125299121 525478501 529837546 44332551 628164370 664368241 452652566 24550752 670466905 886607062 793176860 521821458 686037000 47559985 251076161 321149806 602086114 185408253 939530894 628104647 982571148 399262560 473090787 726505923 823183173 743134879 481907473 660457495 782640073 842695533 158546829 569711239 349957940 718105104 125803226 867472056 283389849 870622586 980148481 660588904 400634374 73291718 149787858 301817786 78221222 197093155 868469852 339947645 870504400 292334266 206261618 516310815 725810365 617303714 638693053 241514680 91453742 748098365 816797137 371113062 306022858 859399642 126807573 35241649 28294292 974247737 384793710 459761023 697686964 369883660 209265275 153203204 435800660 202710349 446333409 676986915 210556215 201968117 236337469 946426792 246070731 140844008 269916320 67315381 730537347 888252639 574281779 368650878 690939544 598677299 62775640 23265229 983115081 210107654 80531964 428611038 164062184 734330278 401430497 873651353 604614603 821641796 639584510 940088618 998375984 551641331 764012270 869141201 765766177 804056800 356514623 358368318 984740501 933751780 912848549 792907396 774282555 650586418 373261629 173844169 271584477 643191174 937681333 957589851 567777277 964116289 142804957 11200482 599914004 983485335 700850002 549333521 481393728 451195776 677086247 773278888 239492986 669236917 658550577 140793787 617173445 431866480 62169748 431029520 977878217 321604496 220254059 60085591 828237885 657786577 724451819 468567812 84878083 967246952 937226879 363620687 519180018 309383259 768554759 112170660 320877865 607581876 389219336 622805320 178889609 634771049 109414691 513344451 532659079 5237354 622876003 378394006 209066726 676650892 362638506 665601604 544037970 453785266 544892451 935579021 873956129 698762957 781938892 479518265 231158615 708082101 526537915 437084612 956705615 72799688 193923525 844805110 85667259 717114825 593254081 272223616 455148145 570545176 5866924 516345700 299765510 691486992 279410306 907681287 689902493 623296740 32055698 919706941 693727564 178544426 172819007 757281288 149317372 735005007 22853713 990337769 110422449 480294290 72787373 836390762 354575629 379035231 724854279 146969781 766715064 228782612 131699392 813697995 685142966 95467056 261082398 796679662 568400677 396610687 152049216 52662356 618205891 466248465 445208271 686838808 361333952 906093989 975960059 405381339 503324060 250436106 546766555 222972237 839645401 471387787 119128079 706000759 150938385 152635343 350342647 41380176 320991676 575515312 810849697 130651881 343687937 619602732 627684995 750995972 463995134 332567085 517678143 511091135 340875110 576286019 826554579 64122532 946910507 842712228 276011473 747351446 39715229 284285961 365292180 47845890 188990148 282161894 904501450 488526865 586117241 766280398 688358404 716989265 37819681 249343165 420415636 687835348 256457659 432682869 657524935 408556633 654930743 130978833 161260065 125523474 462581543 329900848 220619375 37103729 817477948 827315790 427987891 65668162 668839994 143974222 869285440 661504970 829239232 744057286 432746960 862465261 288731145 439667152 582346193 529652661 390195841 11635224 74462309 440427531 958299505 819240221 442068008 637484069 528822494 917789091 27470949 346622596 796057240 587577085 514180572 54929307 935208207 538221100 427525463 212713893 901517528 104347648 516445167 556047225 350901217 437124587 657626568 373599368 771605012 613138606 830474785 510524345 754691027 868563414 261640681 334205851 753172628 416492912 696641094 48451487 856776498 215868054 180178603 127651131 491269350 156414409 279142503 478470693 28688926 368888948 22222706 850235868 639874958 195931493 421766268 134003047 153984165 889662587 426276582 866812730 862760115 595404749 483904724 556388604 855364117 904782556 840841394 784931046 607930551 432766484 860457804 615504724 4812883 308864704 718421262 806657881 28034660 448767741 120188961 98058598 260938063 883201399 217506309 913979271 40566167 511784676 640036591 556397961 672800588 804735409 433936483 387110519 293761020 536844970 573806303 498375773 424260278 768772487 332971152 89585213 106865739 486497716 206428974 920370815 461128602 880195901 301831027 997047056 67959294 588851869 296394046 93777825 40019687 266235671 266112875 190527358 500838195 827371619 190998251 707055988 152130869 839437548 380524994 841153494 470855408 568965312 94312906 351554319 383809023 393941594 717487967 864923692 381832039 289675220 828596498 948610667 133804099 101735421 177740998 914879289 313210958 725054335 160638768 593836680 651471232 836240835 406795991 787591607 860450024 455967771 193142715 924750727 333634083 636421597 761015402 15796306 804072214 19090515 502563913 127720654 518505856 597632335 640598536 292352374 17440621 183922924 879986366 525957192 604626900 157316624 735675476 78147432 835819498 405262853 413048913 427506133 535642441 158428120 509200426 454536738 427488814 104474872 950386675 140510432 244025551 474666565 629924371 304966317 61718251 895222003 342067445 714678972 932767933 257631614 79251393 933346834 322003411 992011697 843570868 196315560 36219975 121607382 225904170 28538300 341884766 67195770 734579206 784131211 584695165 832855276 388787629 147635039 160109799 452740212 508953694 715477578 380290515 273573744 113198896 190632699 245345119 837128214 835673422 400944545 32120555 739677626 391941643 647192003 989639451 777149395 43124218 549846955 239406695 320406700 79817988 829643347 648021946 191625591 139964739 971286615 220386871 146750830 627471513 374775855 81311253 363187508 631764310 315386325 632580567 9531366 703876866 946316412 569615462 584184078 563156380 675608038 954466566 716638286 659853093 334842738 705965831 947201549 322746842 910328547 11209835 91478810 443561038 154980126 773258549 159444183 244319601 430112088 207334229 930914161 812875204 352945058 522853491 789260841 42775830 95148066 577311347 671891478 738466866 956540286 588549125 684237190 509834891 289323660 627270376 443162303 300565933 968987723 542345735 59328916 480946179 88759083 110872984 619563495 589822229 481428209 658521236 733103977 335135943 681442658 483511611 654990005 647681783 541063673 13172919 683245788 292250961 439580343 39964694 334084195 42792321 347163814 288874246 229545760 777589129 107390906 430016204 572958457 284448354 992088963 705867959 921157225 763038743 477206843 531473551 364959862 167280587 496418865 391855101 899297018 530176139 57628313 209332651 47662775 448821473 198374876 945990250 637472439 446562839 925970136 36453986 459540146 648107528 224005591 814740362 576691702 963486878 593139670 229201227 617245926 11692867 967904716 82705607 40159384 217252049 470113636 468827317 676697888 791641169 398501161 993400016 995852618 280476177 618829248 616576813 709852939 646687603 715714718 434904734 100980863 369819404 422514074 574957928 277125498 781936129 80049675 910404885 431738304 676738156 869471260 379064624 417934840 494409286 473624261 360271231 73760144 461946695 938085919 834988425 901989503 915203197 864034519 58014486 211400877 825413617 713461075 937371879 630101821 551341883 652626670 158741698 784125097 297550280 520104382 25158695 173610075 60859583 794667634 148068338 333824509 166624546 175754011 576535098 193100921 217752883 830862866 980633275 544350889 578416564 203776607 108656912 382492230 595507152 220383939 974866898 676463644 796713910 8996458 896100500 131198434 966325945 623889713 565823890 454654834 363118022 953203902 559736117 921672515 513686405 725197530 676143993 405476532 506198603 202485071 722927910 50133445 5693465 31002377 388010672 943573035 480105541 164137153 641574332 83336618 508358840 334006237 526355156 720219213 403413210 665371660 65426144 955210695 142483381 292405940 746821886 300386059 853927283 920848674 187092274 15728920 459457305 971785952 300674156 716945529 94139843 753065474 860276189 723820376 796736511 447209224 87362979 572086144 927784480 344736670 567791684 206047430 497030083 177700163 832102652 936523442 143731496 693537887 706556895 996291392 181508224 593484892 974157645 923960821 823207371 157936263 123475021 987655888 337181367 838418270 143652315 227045894 592236015 984845962 568332375 339986961 208505634 737749081 946123009 279589124 405120752 972169551 695256920 428942774 813177552 756739646 440020465 478066776 620122723 47330421 927825291 584602483 65053446 353116616 687973575 742349929 326209487 990557699 723567523 350890950 967681988 578307480 197762239 872596222 362177169 243702463 250302003 767639979 923029782 509243675 386952564 666843762 38897332 246432500 533661924 485871133 788968442 432703751 37829595 737405319 353995867 514246528 967720019 718884372 563848256 447804460 583444368 447433408 976602392 391932501 349196266 917335816 954652897 184414807 844937164 821910234 12635316 418141851 305953126 410599692 761597975 272757690 59727452 260494470 639492162 137016006 155641343 920864760 237182085 91198170 221857935 281793757 418330077 149904803 590446569 993496930 1955810 250450832 904426087 156290873 553896335 149046990 902758186 117915262 911908025 222275447 824692226 816847732 184715202 834908803 114278075 496708137 858453280 31883367 225202880 998734793 236462918 297310905 596826267 21402205 868139489 75190062 270748447 432987427 363606067 56908493 84414244 842610661 415440987 591534019 469132404 489148864 245052694 598958342 932534746 174314691 202092342 230087403 969576906 473046191 65295083 42551253 21491468 643368887 141611364 137044269 780693662 365942534 829143340 503499129 725065575 608273673 829639462 12287758 772675965 863564971 239343371 301144937 451936512 50523998 558745271 770468589 985099641 1914212 348500698 177265793 89872356 669827025 772445833 392254820 203075515 124392655 258573088 41144408 578983222 904968590 624727106 625548503 20986676 783347725 734594485 407002796 765861170 457791337 682551061 389318632 215706935 205221281 985615792 804349274 347137483 40157689 225074917 113516241 90231716 177040169 691456236 456230525 809598980 622171080 839528427 735050878 770200892 294722763 793995574 653182179 894760052 475660050 45959374 921413008 30252932 941813245 812952701 110313678 904966324 726018919 393781622 446633057 171825031 434487995 483787682 610708903 87926076 589127743 750843466 465188401 88566662 88766025 51472581 60451803 445632938 951248314 820216625 3479012 695924396 983061559 426140770 820252394 654911922 15885606 869390424 619659403 378577702 370573967 346671675 591204186 996195341 103252189 612838658 848992985 114069715 253704378 768884830 531515487 59908177 928922616 122285565 138173378 361526481 569099014 506360869 656735445 554809066 541911563 888686077 110843354 407723420 698005720 473044383 168895118 41279152 430322896 898740974 668949680 281710863 404178469 2589358 318172257 706561648 904040531 669168748 319275683 243223623 130082735 190969497 481939793 970920948 735536449 666570549 739300268 144733185 3000204 378734587 486840777 731162694 812868619 777092872 446022023 969261054 843099937 170752425 637073865 765687735 865485165 773163060 869645443 809212199 797985139 305879908 153239693 92893262 857708120 566904204 961522264 26376724 118989935 559639155 633455887 334712238 381035587 737623606 901098794 288527871 807600249 349268382 737642029 635595603 502712655 797631254 320056109 562646070 481667725 55746218 139127363 548517057 855780969 444498454 383381901 137324114 76902715 75536035 335488325 788941008 894893278 55051456 371328321 642073346 170138440 247426376 364892446 55438270 79629955 977837520 540943949 174447866 841368840 112136527 983997868 700250132 821813644 498684144 849558741 293756963 619415993 164440044 36849698 49881105 385609197 40158143 327768924 334086037 64985896 601977170 357653834 764458487 1529993 465413816 162436460 665603035 830193685 393668104 60166863 947089572 22039106 104681050 763251542 280289162 996671111 16251515 220681411 577041723 860463635 637667838 141702889 421302744 183119434 907705196 577240235 122095972 841666669 280032054 520594481 15262783 697596222 169931339 502235170 783230908 397900536 376887170 557627847 897807637 577985810 38516762 576191673 933231737 112206318 442524593 762543381 292911346 497913453 175351616 541208415 150885009 889340850 268492962 923990825 905364745 986848444 303101426 522349773 484201209 385248846 608371384 875354011 94851218 684443247 23559682 704357479 306365301 429974597 427110525 734813728 167762964 332932659 508905195 396793961 352862039 362324635 565246050 291302731 818063820 698679895 13129450 45315996 708336731 517256043 260305410 778297557 929347427 565392514 954309302 401514758 89500458 643010412 177228071 836943982 802166632 464757983 172794102 403382542 977305882 234694848 294529517 399630262 719412214 590961288 252617206 231904083 748347982 59330747 149113703 829354888 516179748 373483286 515485234 913196169 997764189 386208151 804607572 157009787 586698499 894325411 43515022 777195081 503181184 217466040 91185809 232778242 834124257 688020752 11196316 156773729 855187185 699199521 595071954 214035307 795273854 173639059 284914873 483178599 946250251 996575517 697342353 53114710 650623867 165946538 39671273 983322218 367303929 533796937 207696313 930523984 663587216 818572551 992277052 164209031 319959228 659849432 124475308 270786425 379992471 305791582 714755794 130084642 962848912 43891406 757103045 526964330 1224556 308491645 624699966 423876181 374096380 582958787 454180467 475414098 178065195 601336281 42261282 864929529 529808856 402113185 477712136 46075183 867384965 349229288 48949328 255630433 594604031 919636564 514813857 427727765 599832226 712607039 180285322 803115415 838855831 736173921 925725392 840737766 816546816 305470262 691999985 488774486 622658887 181057723 573276417 784661294 328719611 295955999 758450564 90954881 896703149 474497914 295642017 454862662 118172480 687099528 890305180 424223134 231542173 913744984 436350022 20667651 785885087 60737693 302127958 444951158 924267143 104237757 246037394 509018812 585121342 344626338 593298351 764154399 658840069 231810800 914225261 102972064 927431793 703471120 443835020 741404352 68977470 268122266 91026206 625652450 567171317 327172075 655376563 630839257 803900752 383784208 700154061 931575999 164253486 605066251 157069572 260365442 312357827 739011873 509635084 173622218 475442888 311428253 266903725 680123170 883864547 29044738 708769324 236323550 126812958 724386633 946207953 496680772 912975972 24308875 248698718 712830469 891910336 396402420 199541157 502353049 695164925 349763121 791196463 591225297 296418686 21487791 64507102 955289575 20471744 559730068 427704816 421616940 758377373 820231507 14102949 942622533 647551853 705920069 125785841 460786578 152210983 697020755 614766284 231731187 218295877 545185163 93294657 112469370 243830480 601645540 849464915 406049962 242273004 349248627 131184368 990927329 364087567 51124416 812267081 711588620 248206371 408909096 785472552 890662840 155211688 511483464 763903593 864026963 90242741 664146132 362947581 8247721 209363742 179800506 521297618 607650542 380815505 126304281 442426592 387634901 540689321 399013144 751490571 48122387 931201405 804390272 450980944 415427938 252937966 968934742 999175843 698904984 894900591 67927129 129243137 765600120 171577263 357288130 203513699 565077267 754663491 952751211 791659219 36354018 942416654 178606604 608461012 35904076 613653368 382413835 945593174 142744949 832456161 363308606 656607310 637102662 381518280 93863091 26765532 229842658 860881571 144065170 195277540 601164392 815464841 343795514 408964489 102287858 745245880 385696753 643028797 261689579 698615953 833972217 889980372 11129801 358245451 674016771 558950074 799069573 133385937 878242086 298563085 224148877 743151682 7969302 837150069 790625175 942579557 68511575 973496705 856796579 472410726 469128735 501563716 531315207 110134174 426895138 612710052 567391235 753413819 148919109 587588729 43746405 601452181 219442876 73845005 88712647 626670972 572319167 979167218 5366720 793145386 142269191 406559804 787010612 295606264 260581601 518743980 940595620 978779191 175015895 965552368 160102607 616177685 839791376 234561989 14195874 494817516 413855535 499094567 521331956 717492441 938660114 434403518 299646835 357485564 150955297 530205902 182242647 149749970 326478621 599800687 956009786 266811107 959714398 450076109 927988113 372361926 794503394 845636327 671957270 573282852 238609630 43688384 612039606 231017538 670754892 740028893 408737131 191568927 142467629 698123623 529766479 824685901 755605276 317951572 378574515 495327179 990641120 244659338 106044371 148655 460535057 153913700 877310950 845225952 442466435 937249901 780248968 422943847 628000618 603039901 108397248 921349148 335235654 86715378 614276385 7359736 736933018 41904151 802171897 263391097 948057642 784356150 907565331 257999495 665966694 826131779 988012905 689261158 352445916 847800782 423275542 595463831 88057620 155252322 196831235 209271369 40733143 639716920 711885385 836178100 6286888 706285345 110999413 407501647 441608828 690793742 669861451 664713597 543601083 583379660 681225856 460677051 496048700 962688846 868051364 805868593 675251041 484166291 962278842 511030827 216337776 448456580 524529990 776430046 792754073 962344578 52700133 425854622 389905986 241543592 378529604 854292132 953038416 12195226 48746257 428020453 29340144 2959514 331304645 909302412 640257299 983727365 614395007 150249403 767870465 529090419 595068860 473367476 363056633 740137281 509514423 600074922 21946635 328214608 374565135 823357496 596707963 924059021 991206767 418004070 452376829 802494876 602585218 354316105 824160240 642303306 810579247 995704203 326687260 107986040 271939062 91596570 718516785 154374933 397752163 731681546 282880876 730222788 908954911 369753512 992779662 393326431 692414152 84190426 99717035 617285940 339231603 79891497 539802673 658722639 234632204 989941498 714037870 901304321 544238934 608078667 213877812 538104979 380522912 180177460 293898969 872982318 577960665 191078149 89475019 25970539 382545213 52269449 24297179 514172932 524948723 170972144 202683465 353697348 688415983 249022096 182572457 138315137 579781337 742832499 432898015 930111918 342515477 538906656 659538712 94091143 733778313 662547634 841466744 918847462 390842024 919001831 961166380 174785175 945563759 113509110 125996925 830418511 456196591 349040674 994750220 541709674 825650334 842209634 176545984 11070331 838391914 924983890 31428006 948857843 266871652 735834279 750731979 439053572 964558444 662823741 466762133 377580030 176787061 995747022 302824915 345777881 281560744 743325437 19472034 269471995 90503570 576872443 481932827 807437448 978356802 777161775 922046598 993547870 136699409 134514128 205757639 575797275 905319870 188261239 272315356 103478027 941298028 878654639 823311471 37885179 527731648 328526471 897800540 736322236 410764125 495957228 362857362 597676301 415004628 772272690 192286107 767483685 911807444 478416429 921065972 728330050 22195997 488503186 604027078 572656767 842851594 120996779 299415904 84294245 402054740 595672315 807321727 46229516 54838501 343861476 617489854 715925011 59145180 115427595 43666261 717342873 713249533 249380859 428705799 667953150 852432364 380491087 497806021 825079335 889748506 48507898 630240652 485193144 188688078 821804678 436969346 86938494 433258808 660800017 928246279 489209225 784073405 189352073 294747754 858183946 529243115 739238501 801308077 872122012 933462240 512497289 995893938 70168906 679787650 370475635 435740370 597772038 144507546 453472490 766548980 313467995 249395332 553811671 4540891 944464796 928428063 320898286 372319326 723011398 667263851 929454968 235534071 985514643 647415468 621292015 754953745 235339924 899293522 195390596 668663415 691495003 460459740 502756471 164959009 444096178 839544108 198434114 913335863 695562876 389713263 167107499 76311056 780810987 123669071 535695354 641430830 810169 224361982 240339635 696155252 852492964 390167523 693581500 974459607 724640900 953130360 334827059 580702651 105695255 889886866 217386982 771941087 249435016 458094872 468591479 160406641 5641651 30516446 333871618 499387085 394822939 267350884 924052256 564178709 600647847 668531199 530359335 117615135 301391752 798026478 515792407 866747023 297657891 948344949 452624107 498683545 934428655 73771487 129053698 841565145 879934498 759093083 366829502 747582269 51929302 200091391 296750279 759352419 357893947 278091843 711095976 644525706 88544316 883679067 564716035 577115014 900136059 445717211 303133068 754217224 541426149 717505897 248663519 764507357 557598537 566073377 936061310 254549993 364127864 296851983 70206783 143385456 212904712 118583671 49195259 560380825 271213112 939240850 425993965 877743009 156618592 148665843 323734577 562084454 414156845 578621895 288794713 376857601 449303274 626659683 832927577 593264543 986143858 745707440 988189883 755401129 10355952 344409099 137362112 921283111 468854388 662909496 340093864 123785003 848950291 717693533 991386833 209898072 141249559 354062077 977102250 978689418 405171046 679421776 714807238 2071968 164756440 69337200 635298050 523381344 275541432 423009363 199941439 385963001 797728606 699490167 200474251 282941794 935355719 74822600 132320261 96465141 743278687 147259145 69572857 249322840 192965653 321632473 336265333 886214317 683213984 661818584 150683461 463606453 946490737 349230579 106787434 115617782 700522640 736502022 455918207 890928498 369922098 125797038 501474632 893537236 773619574 369721228 466096587 70828303 214151510 358817244 414786899 872770557 136793487 461218886 430407272 573832446 851260032 718295931 941364229 950406858 657292784 741095534 424388327 979343982 315548371 838574791 516367086 947783559 675105100 639066630 714675766 816151465 128380245 720769899 839477190 157442765 806600338 566059060 676397933 13431060 797953481 626336003 29672178 526427268 549163354 740772583 105455475 98136457 135518540 746883166 978457151 217885378 992790505 34783512 111521574 22298573 361361462 466538075 425477703 896940578 399714384 66700679 172886278 295836372 818427249 568517511 322949870 192360043 760460655 697330642 157933012 610346705 432576022 234351706 860811422 343628516 373265494 61655700 49611703 366289387 50901027 297064057 688535361 67347126 532574251 314907913 386118498 946494879 484167088 235665083 896360208 104790207 181999569 795652542 471741666 373269084 780310670 491696118 986223628 766255264 757961753 852371445 300937088 402932575 232073663 123030109 945418739 679865524 38992033 264724984 951722548 79088219 932307110 804685746 41035578 5430242 296667790 785788660 300700956 246957943 784830458 375522490 474665317 915500758 492182985 234942902 243878365 107183692 716725839 188365398 428719028 957134282 824789165 606949441 368478843 952810243 282991865 592577685 506434108 572013911 821417024 260273391 371800216 234020504 998441212 58235663 486578250 182293160 592875335 49339021 345040340 85419857 490336408 447986212 870201490 85718233 541810650 653822011 725129768 163654956 616801046 576463357 692494894 147949609 165688286 917185444 666130228 437090800 278450935 729269401 826465791 469530971 45812557 296759929 983504536 712297286 240827445 271457095 289232575 13301501 562208796 10388646 643238794 284818199 806130497 900197973 264181329 734603243 76146186 909006679 787723725 352920320 551979382 510036322 313359302 799975973 309449521 790994886 594418394 525048806 823981142 840099580 403690938 135317474 219577846 145737131 704237559 160606392 719927872 380220786 181352045 153620550 614147327 794487679 915309140 53366546 403686637 994320114 852313722 808360863 156303922 998506616 436052964 131295793 191191436 460916775 609655211 427155839 726858383 24349977 227782499 3365602 10047490 279754792 461483691 149918661 908301591 439350053 902250794 335946772 769558506 934716405 697842089 776545614 48325297 281500853 466082791 536395336 466530827 682429963 600819568 70587505 978630434 101534305 622856365 404627543 887992798 260295184 651034424 160117084 94069990 717803042 481893995 84556228 546155924 801344527 919561873 508990939 242266027 712256887 496692147 578564692 594289 971982206 31186271 322863077 729568633 107020517 969600260 556526140 350746500 533485107 536518141 144118926 639060479 136574685 723082459 838890863 536267916 805887087 576660122 873780604 86338143 457532585 563097215 259877284 837339384 930435955 395233758 414851921 776337911 880733283 101166208 307425805 579616845 626030275 651136820 384028117 863735173 454036326 836214677 801556251 347158352 209096057 821321015 763994601 932718387 386090463 860117851 536625299 331183321 852261361 961559919 166186665 508980947 179365722 117932925 806118260 305047847 286160425 32281068 86701488 391303716 152267414 558872396 770009593 360888666 688006965 632970759 272186455 729450282 468599382 77280802 385339854 57001896 301296622 750496042 282422764 359478620 37176945 689139266 75280933 504510037 229049424 376817429 898397799 954924370 359433831 147502360 701866197 325237984 345426518 370586581 749578242 735774690 481443500 686348901 453984122 776170787 531384531 289223317 95185954 543750329 229608268 558465904 935654102 617355679 668773165 299580507 703123166 307870121 132467179 795471517 261482979 47709357 849367312 540527767 893158116 220836340 573840363 795312517 534245587 802073864 773952633 607770407 476127813 221056296 293238560 229433956 36285739 51153917 806111995 690506962 478409614 295677877 868593781 631561070 895481715 215401624 823611383 657557491 554406441 203067449 652543040 1270787 65120048 960665731 317065464 92412490 894709527 107286508 626333234 273467144 61902721 278810741 664567133 892660924 940663084 253640335 258153012 612759708 961426131 578031207 7307075 676283870 539724907 274329461 895130931 427476487 656189052 828896422 197046718 645026979 411882477 591292718 203746359 901993581 5736548 779004871 793337621 764513430 985270577 336100466 976723572 210150269 911351541 527059591 689940413 609727539 756842498 208492370 907522066 160414199 523417852 585865812 806036706 250543616 104458766 858438292 152914428 495105812 19231658 996773608 644721008 378803101 371085871 419852972 351293551 35346718 527913039 958178421 881171070 214911457 82849875 405229521 78269090 19686470 720863041 406333476 837990236 795555476 297795550 541482931 149494018 606142546 453418043 397820184 487073512 198393616 196122318 629590784 287529811 575579694 994525447 939337986 98550621 717725404 296030934 346464011 388867531 414402109 715836203 326670300 813360785 386428590 672831390 425245712 353397465 237417503 560470139 742901950 280776306 788752905 852032760 225610923 989469877 247761453 566428255 171618012 282982212 531079111 796837463 155902152 963639252 371678843 710566100 62294833 659325393 468289138 619112249 71092467 986477972 825746087 874126494 497278502 776173365 460285921 376083623 583135221 302316227 147325232 16544787 287894600 707643210 359521265 533578231 777441299 312519570 168746061 700539659 527132369 596171725 920753417 986050360 600881397 162644382 564773884 986520264 358022763 250620686 691399424 935654403 100028242 802941668 338591916 391157737 372066350 522622419 423860360 738067050 499648790 352191686 764644388 966080055 675121076 963170669 416803599 356004124 617816358 257389629 828934438 622739617 195495034 924728081 93584462 415893098 505160964 715643205 838912393 5056268 262838401 620037094 669795278 650328735 198435033 604159921 629662354 903228535 946736614 707998542 189893342 414063775 684600813 290214990 856004194 963978633 981384216 720364475 206033221 335186346 32122431 705813921 795424837 474871522 267140981 841001432 273535399 425915808 485183309 481501992 591267140 418630801 601670938 229445213 801803906 2391403 797829302 596857344 953033969 996294669 265432713 84591805 730518649 863101317 283211234 726142934 768006382 339429521 928012938 829254815 628638981 705701617 142455843 510301478 678187630 161323990 545732408 23608791 360538760 963537401 481982046 822767793 241040682 226996665 141092229 503504340 263646618 879388365 986760156 803980091 925777697 876589424 49238347 856016026 938134858 687752842 22443067 353804307 852181068 388188783 367828944 43875474 750934310 924939188 405856980 436568625 929467155 750566486 40215923 860206466 258956192 325563163 325676113 102842403 306559544 424903976 74140985 575624243 398447411 925402775 182061933 513288967 958370393 308588413 29570285 772413629 614405374 332310980 967643316 488818636 231327889 258188158 976097613 343570775 540762383 715985966 742177438 384981861 152491155 846304506 650161764 840553620 192999311 157540309 317972913 22855301 213654320 725527946 403474923 653070959 467717177 946088102 730100914 181845251 624061832 362511680 212127087 896019268 265845729 888135253 792854897 143957403 671162541 977509697 296579652 67206788 242223389 310717448 826445435 457340577 112373532 648783590 386880225 30728077 323894573 693515098 878955847 840315194 494677365 665381232 475527903 766376930 377652863 543668577 984924825 447519554 593061738 164323136 957866721 343165368 99265473 513200168 10021575 506020312 2347037 479570124 933855237 980072003 176328321 95471751 652584626 635664877 814842747 294858364 859522131 640252091 129078967 38922589 260923558 59143546 351979796 79524825 942229286 744375144 957199910 21108785 547259108 208391924 982032805 218677641 864614058 395483748 519482093 310334390 945919920 16347292 889715289 719089515 140402488 243812012 546520360 976041202 458166857 25611313 934943852 485549068 118943411 558916668 96210845 478844488 949587762 894874514 654311277 37644119 767465874 965304034 737929337 62587461 928550489 974664444 248863410 680718992 743555918 128066540 38151111 470285116 42600754 51925626 130056264 398870699 72779029 464991350 900708880 238399336 685961061 427234824 951000272 119142109 413058725 227886006 664849880 635324648 995449008 403858379 628288292 234887830 610681012 796575105 910842679 566168606 654026906 144849229 656319071 423333815 687494760 659098505 108866878 220268917 20383984 600987754 702053201 516437590 437798282 39142653 225039099 172451076 146242461 369540532 194267228 231244773 758475301 704009013 274331687 754085259 833765020 73976761 224852106 410915310 83056633 127800537 238565484 920980871 959202018 629451395 184376520 718772393 506699423 456375939 204617498 34922905 852271320 321628925 425294929 29001924 760796015 298994923 213709240 123098535 107337507 351201837 894327896 275596264 871331918 316515605 302788138 230789009 614112146 878157031 924474675 624758800 498701671 632114286 97296593 817373229 975181943 982635480 760039913 219748846 393786907 640266181 124287746 320136797 309366719 139114683 591522748 307532155 465139079 718249710 670437220 858161607 694797296 307694546 815520194 898540894 713494344 730216362 117942951 831695533 140026044 470446712 471969954 804570049 806321795 256692700 567317546 916023379 860373202 188721725 538877094 297484410 738317376 443295851 959457725 925389466 551586484 661207679 988459745 213085276 659008591 201483393 163819451 535521885 586147529 120463716 752529477 154004578 479094200 202485034 723390105 279027803 824185156 614547880 259790319 784006691 922437420 487637110 697468821 158823743 443250264 505697639 93454056 339337515 768647758 864864480 832812673 302037377 558372527 669187932 762099944 908670648 448542549 906236318 669512650 540233383 46979896 859936085 752302436 352893331 757894380 253414345 695411856 521912558 564652862 302743358 663032989 191841752 410171966 627899452 776744284 133144386 637526379 563988981 208705967 903518481 580667508 532011311 871018235 666983012 361156432 193610921 953176318 32176459 621072063 842135288 922073379 885963003 679443493 846671324 978582958 964532644 185053372 922167804 784783945 57558435 425093119 766805561 468650654 333727088 689150298 729049619 956744696 495900666 986972705 379853941 819126546 78559243 351408315 852004766 721273737 578285941 699391147 958577316 412142893 701954154 151164102 727762755 562035684 682428323 903794669 933796219 664829803 642586924 837983408 849762736 440242291 322991785 418792034 603671777 685249617 140818738 613398813 936534709 626080530 475555796 994909393 116996395 712147493 742551631 967547394 448366087 603040942 244085303 585531884 665247124 940122147 121363768 919706538 933733391 15805174 854187791 327031992 292895888 739176246 861375555 356531324 182836418 946435606 510309553 580683404 126062736 360646389 118069998 530251084 5961883 655405243 267812216 927688628 104776395 494105409 11892663 929803805 301640594 922952957 532408984 519823416 971458148 85172833 198621476 685724781 911088087 822613235 912070304 843222488 752219415 711861644 862913543 388494969 279260418 87925048 312929476 377951379 204811594 183552704 224726259 768800158 695982124 461948065 492333111 305435359 747227627 908700736 680077295 840236891 527946138 385539759 409671955 747899953 180332090 401467303 848388411 373343338 229698703 68934948 108595647 364660437 896905374 841163185 488689816 255288520 803146585 141912025 596838618 147761985 948959340 5839073 175940132 206295126 788447137 208658879 967916931 882066064 432390382 519781568 145616917 34011891 317080708 800472666 259582586 745002870 486535836 748122608 876286401 324763163 515087953 594049653 906901563 799501380 330348077 59914846 186772088 274299542 595266566 365818181 230241968 622643104 132542864 576952868 83040093 591112328 585126093 381875254 62679445 451162498 556442274 827284729 137748024 348226383 462342606 665015184 249660900 692805174 57926697 671540685 703741989 80812121 770128187 443100745 95099446 50719069 967521456 299627187 642155477 980658021 552626412 865791496 660876198 846926882 568340081 645388977 559780762 840100363 43304358 962153654 886828656 742483503 449804097 327551767 146034248 901674541 866939523 131655445 562568783 584615571 655495065 198269090 686316189 930351375 410310106 240785384 521101468 520906621 746051512 834216077 626698876 642664929 43682567 420718209 617485320 401813605 15658827 269814651 669509168 195562879 822752610 76679912 585731886 917070177 18510702 172164910 785177629 252263615 312317029 607565778 538633348 497497674 808049953 895125526 623673766 348116522 585851693 104488729 426165349 877699954 348280931 147702098 880780121 450357848 713133327 721344709 798859254 752256182 483220778 376404964 74931579 537456583 218692211 352796377 83946514 374479221 636787095 364470921 491261695 727763516 803598058 313473449 162898058 276732998 747747495 274368876 822869071 629530842 594134318 556088820 961839783 770911215 996904006 238792893 382319135 551402125 686391289 218745145 166918598 527000177 628541370 847057653 428295571 905444513 882311904 728926621 22664633 613021030 74817550 488105424 136564676 655052271 380130383 770952716 87901562 358385365 81830783 713264639 826574430 303792711 260019137 637977712 336047075 60959324 826582743 601919735 536636079 169739193 160711480 336469454 829690317 590165394 112731735 30737041 324054388 316750823 968131811 94113909 532916799 530069772 16090875 103321526 881658832 840317988 917471664 870141478 696804802 504849594 106422116 186521743 818245117 481142822 678182438 311892261 606203909 822066918 942619667 735534285 356787839 338335228 159127718 638359401 931181774 660879595 149338308 73787500 785178422 90563877 136210235 287754704 381555049 696961306 660753327 923317849 648282445 786183352 86233317 95514324 733467230 796773176 860190700 976357349 400631959 465912878 33491665 293495751 744428063 858215540 97209104 864598952 55214267 270273696 829053229 719955199 463054199 138965546 572681722 954373327 105574303 563453976 967471573 221020952 922140868 723945329 86823941 102751677 397380561 859145848 975641214 456041857 72110821 162810931 108624364 198841266 964120029 310339784 696315664 752110309 36673527 71846056 269202018 226771585 624286822 755356179 714835624 406715026 708774428 316277081 724493487 496378836 355101096 444930332 579795578 796611921 457359295 179779849 852381383 663334757 178181785 222440859 613823258 957800896 334289614 798174248 839933841 692764434 963484478 348462420 835755011 767295679 63561451 843029924 179035478 320755123 109014814 879076189 210640886 692543496 718790319 156331021 442840692 620617965 811269963 585230010 531611150 929258808 694596113 384019753 357751272 887354200 794172555 349985487 447726907 354447585 414014707 610702719 582493297 220091248 763228385 764624212 99917458 333671247 10771357 480403022 139037055 54735348 935009061 210756738 743106064 726359654 55778658 736106958 468509412 136274625 669305671 932795322 72762425 900508577 50985325 986783761 636123382 459303934 732848826 357797826 619362736 400809729 95141025 648119336 993544320 959305848 465764099 250195968 957105660 596189946 466542466 477695497 177928192 943664195 103377813 495061046 400322187 622855346 368132910 484638616 144189227 852479727 995721458 981266246 461579743 529006468 342864460 510872489 93836927 659636460 994906086 570362520 619258722 797514324 59492140 517029282 516555970 905125241 723198479 273350696 410502982 370595329 344683539 978015983 308372844 16425651 388179131 963579365 678052225 463323436 985134439 582313259 842688328 288360183 591923098 204068606 979411364 669315269 570342201 385339068 607765846 756237795 783270025 579620640 390246359 228556160 376857437 841149731 809161010 228912067 935927383 914874595 431124396 713501559 714108453 440032895 260031078 239175692 752900672 441482560 216153678 630409702 406992754 680352133 439624962 385479243 521798199 354367650 346943443 529261541 104633543 370289811 186240475 185367282 758804224 608585795 694924577 685176303 241085138 197268532 692163521 387158792 342290041 474272928 233851541 113448866 925453668 971943557 19788479 327414014 642828021 981326989 675909546 136691326 846058840 977505225 389941161 144657359 955179821 837767736 788342091 250075116 326311263 667714148 474224384 496834 450597115 961309585 121414384 532543362 10965839 74382594 952680916 595532166 707015176 471018924 457590892 527127481 607457749 960747571 925825909 100696763 184749582 491817051 255638254 406134316 389780483 624057796 569572194 562582290 688852037 928292967 390466373 237475051 390277795 254513250 372968766 389674948 170817764 249391074 145743930 241542940 212426191 785256268 296952093 538149354 562853091 289645193 341936143 125623442 373921930 859847618 199232154 363329214 683034073 679612939 964158609 393073227 300417565 601985884 170169061 645229371 722240510 493070581 7394925 847522758 787438682 37855280 177334589 113265321 142554685 26900585 541964461 794061685 741743828 516449924 142062004 7790582 552936629 386157448 407655335 709023918 255884350 345671020 159965856 483856670 486189626 332603515 384538550 487646597 723507198 560585819 335683871 407631934 60890075 414645990 494794588 426508695 672032499 830054339 529517693 757827654 653047800 306721304 428017496 693830308 885651548 248709164 857636124 27181842 433130277 321495397 745857233 960413394 537854338 739600109 388303025 777935503 955847556 450434392 498320893 759270275 803950349 250196623 956451442 241090688 328936663 853317886 930348273 197955093 805408176 280257915 214643731 331190498 802340026 383254158 98255473 853737088 897037231 620849842 583378905 391683587 668813599 374880840 66419343 925499743 242998016 638770497 541576504 462767653 162461147 785532653 402922048 800679628 89494464 450905862 233466017 948943617 529222200 449599484 291871694 506986119 169902212 586414301 85369186 599635644 277932528 590737837 908614102 429812535 615310606 599205607 899688031 30893429 533587056 140374787 193648390 156043472 734446863 889232624 260287705 134213863 86887904 518759837 113414069 938537394 412200368 549804150 938592526 630837661 689994880 38149243 205667370 89158525 807971821 822037029 837103011 149172298 801843615 187803462 415653848 221583383 840399774 345127102 295513041 466315644 943021028 249406382 131737139 528750990 317829275 897911639 344675643 275535287 821690262 859018247 743431457 427889928 327396221 590075465 497150784 378777100 978320529 613145628 339181237 858562673 596036126 786279933 753820746 367672291 84995686 618615926 335754186 659787202 77698325 732309197 62802823 199754197 174460273 969897361 973250414 876563419 157619620 535492981 880259197 943824939 797395642 98317764 374264122 959033886 342269917 967541707 254131861 932135911 947033830 832704056 743344851 84313448 965526752 680676506 107917685 934880569 928741168 942248696 203057094 698370056 614312433 589656409 819450611 152903729 142940226 2679340 402822582 689404635 612385244 116013664 55030659 626437169 151702343 467899942 4675995 501557592 861987977 656244399 859674313 160853338 401174013 83477068 631415872 945738500 261012343 551454457 88654625 567325467 666177748 404592011 42196387 265844026 536891954 161136542 377784488 608018433 744335170 442058570 836279528 500105176 125658672 205934804 292507635 888503579 400083717 993509089 155598523 79540288 921096525 384604158 973233127 649187640 186820166 942379736 126283131 17357489 313872043 903637930 475982776 185553557 215105919 752948316 165023874 205303617 8951219 169384598 480995737 488867729 157410899 412489474 362574722 381637665 567576423 330083669 785506062 117787958 340821877 334073509 621299788 140506859 619257095 522942331 744081386 469936060 572881962 425333672 369107491 258132078 983351750 252931583 619527538 568552808 677619578 693359106 554250662 109428524 155234881 20528742 78863065 771370256 336044953 899798716 151185977 325408945 870677590 189984486 354740858 534847006 338572528 237696787 547727085 391917845 36214099 936652007 806644052 485446496 273433445 478995783 373788269 504950525 295833749 645408210 728353220 236453947 376559093 107012807 198732674 633769984 883714986 163214596 210989396 850889582 474057852 657982604 348876968 255334247 254051342 693085264 997834476 60026537 769436895 924199610 185194167 353556198 371197331 171740229 905872545 66994769 344603543 711665597 52378459 985294257 698008954 373505045 945232686 89318302 901878674 211942045 358383237 912491682 890857993 843222336 487052397 623392086 222660972 146026634 759775217 827176003 504413894 907825915 943102868 877064330 383296400 603549532 182776388 967801674 14643407 538345673 488548293 593235340 47900801 897680313 293059315 688774735 817389361 453546199 587242831 404010557 179789852 20377378 46828357 136968326 124898326 422502770 448327571 316721213 618223364 305667014 599254252 827632454 384906871 856706762 220441347 566455697 126336197 946153938 627305075 499877496 427215268 592341975 124794590 718734357 168103039 628759608 675407773 195331087 602278462 209849716 960174279 717533923 217546569 165013754 309250819 57998602 49956473 632570156 704072406 405200477 98256039 270743697 546693110 937604925 325052032 291491667 907362944 197898455 461001267 857253825 680086476 303612493 973741316 880519151 926705904 631729198 905367547 413832508 679738570 938252311 144653235 508308893 971784828 455393644 509610382 229361004 509837614 658743291 891154443 112630642 80111122 585016336 153662757 749051663 450571472 807578758 672261875 989223719 70921589 377158776 507419061 333760986 676228097 638407883 802275386 732275461 201673918 778127277 6109893 823774549 944604214 404345189 237400970 657090035 259196087 137994598 591953975 874182695 664734037 951709834 654961409 841790877 211024393 799863601 937596107 178343852 980703114 725730943 873554178 487009813 534271941 772641692 788720640 118207645 575010233 179320650 669557534 120965691 854299648 680255249 588555360 662561740 505310959 175361369 108357141 426028725 421244348 96669901 512640190 30932076 938717137 841440118 898848076 250537895 218849957 734571808 386041671 484565292 556967009 636446849 139984434 413668820 354832346 715425513 434193238 81232371 244604548 113308839 889366332 784697166 362335839 419530559 46639688 531626027 433179242 804447787 834155556 391147006 323503373 792183752 306385119 56311894 886867548 318824197 375472830 670656997 225705675 947138086 672051796 329603584 410647756 751685993 686828488 744156010 470562034 300655206 926976380 970323791 139993552 907489957 458151151 347496876 937323233 186658832 396605540 158907947 665325643 817727379 766794227 294166169 195680163 455429183 475611071 437615919 213730767 49708219 879968324 245099219 554272238 524263625 86358710 511551027 710034900 960356567 197326139 997140410 836778199 247788498 854059907 872364801 773886161 859883230 107266375 810608587 128472738 557182371 62901178 999933144 223013556 797669014 92069250 466660678 298037241 855334491 213253395 473108194 922226159 138703005 344613614 954411933 13309082 235064432 816491396 535441382 325290715 199815193 272157835 224436055 186238833 956748335 913805968 954784549 136687723 11876674 995055517 121112183 758413059 660102688 479364395 478322584 512759007 263759790 706578417 373805476 38356897 798681080 669901298 268551138 796521168 906859103 623775794 990855956 197319604 673871509 655912909 15977514 567155914 788623586 11315996 798790887 943072587 546829397 709134719 343592626 862353054 508764592 494309847 175952837 228731581 610108062 284361743 444633648 379450140 476097171 384712586 824359324 514541262 148045256 355716026 167797314 107166389 540055478 478724894 690957174 892916902 225245161 288909988 192226391 421626039 58282477 346621533 741785463 322447296 54711186 229257496 66323 428536334 405908719 350117692 856586879 460079591 300308733 485955774 357582630 101814136 285333943 456778834 365006125 823533348 89581677 58462845 844840559 899581317 137235010 907049326 571802905 264086006 520436233 392835426 129037818 419674063 166686953 257899521 608374906 766275885 234560031 318941893 712836672 311047701 603082224 866056358 651727096 920058058 530117135 878302874 99202301 524297570 525126427 94771332 219463879 936509464 790591190 618110830 266073187 567469981 959256284 540708262 846378675 928476117 326432343 825318465 294380562 655395926 53390907 237855487 837735450 48726741 222839997 623003566 578683282 711487013 191331098 76737576 421025828 162228901 882525059 422370186 723084372 708718331 805784284 910550805 526621413 221294216 545616183 763168045 995583045 479318421 158663278 602080092 349592665 777783423 876024793 903673752 647558327 954435053 738537840 718790960 734314239 387062861 74151547 820036830 823497771 456943093 592195332 394797243 191099476 16825075 606205413 267253868 696369702 453560521 915875079 916299620 754778440 359406677 483916153 175729958 48569420 440154730 524102571 961039901 672911899 327100081 97940591 413102676 957679488 141019094 101662821 492512209 376337800 988278882 993887639 578507270 541015895 318079897 661556654 974751368 37741868 254469478 36581918 337630541 266554629 402413540 190877606 363903969 41237620 841144437 975274257 957702003 93444669 235576083 702124004 462459971 856009622 595984832 63150280 366776548 118916155 40193719 217360243 141475324 625930280 102396819 845253951 823782422 575258832 445551018 880867986 957852712 791751356 615949395 179050122 7586786 408269990 531484537 722015448 418078226 68511747 253570926 152650335 803657476 303641710 622762387 768888979 987569043 125395738 48420368 204603873 521952422 885638852 715324499 666058337 917965819 118010338 136131183 397242711 562790810 214656408 122146166 186496160 132307739 374866704 269006469 192600633 710230204 861572576 8016254 773257978 403310691 949816655 100224207 997720765 360866934 169239370 494546391 332916817 859046401 610447310 257251144 793310370 253689751 205638787 426244477 386264268 963326398 235325510 992191219 126534503 97266820 496478893 823241889 791042143 125097808 102769516 219772604 789916899 639507743 52011385 420161721 53731992 42135942 908047164 482934868 319356342 557355824 240706158 507249508 467950092 844156470 376748644 245233942 963385490 399325524 667382688 645869922 885875382 806798109 355386819 704504574 530926786 221746796 466917909 65710446 245173468 357253169 687395665 589733730 308969872 522224590 473272581 429937194 967504770 159675571 511628578 62272329 277590155 88131497 999690364 112676511 485268036 41633091 434431121 650364836 867515433 968996932 679555076 57645376 417408781 782991998 998209003 508620464 440630556 975193301 48244153 185285256 315312143 369555347 233800088 641893590 481670211 479311350 677642275 202456193 665854616 122839365 63027641 715847022 958312708 415843032 665650739 261839921 535026432 985375740 676842367 727277092 862614540 845841029 701885923 822618626 971002664 140190058 269959600 435752561 426237910 620935103 649804690 466747322 918220062 267994270 855147830 280639609 443179680 994083465 851218347 293039302 749842903 637143007 507961824 471720232 155243448 948471609 318995579 222535503 861977891 747392056 412941251 79123043 314888130 237889976 406766345 429480634 878514921 599555639 15532618 908034215 27507716 718629888 764799780 261268780 808300389 463332299 828720286 977985613 282897184 80473203 531453933 75803686 918953615 801636056 140097184 789385031 102535611 372298017 730851443 697919385 834886715 24915457 274086181 589918205 928839152 724981104 537272050 250281008 923571119 371116422 320509820 802277959 928036176 736195068 287120081 3234348 852892226 662608897 518200642 702580028 106270873 487694105 1262548 489502655 957667916 807964110 71142243 27608607 559644674 219021267 314451724 653669895 980513355 702086267 483188790 300123204 430559003 270901127 973466 317907599 675900818 120575106 225831821 629822241 216777611 161391382 764872157 213152795 397831157 736310120 805881529 74708557 501444583 592183198 196687591 509216676 215935530 330511452 844078781 718160603 338724265 100829261 396659683 330958298 970188641 804949945 750116511 824220951 854009630 930947986 657204779 384050840 268989450 964020129 40247166 852511412 708837753 736018979 220694423 329737590 88852512 276527813 377679838 626779191 88285000 342465127 951126661 924297934 285837129 35181720 219276625 786402190 187934832 419045170 680144001 738555673 726647467 723819481 709536296 783961202 151190971 938266802 92080219 969594499 425016339 829134604 749733744 563981448 153330105 552183578 712584651 784671583 202707930 173452959 985342446 365253672 425463548 262417788 797297839 932420682 425766621 445254428 198666711 790431985 485463568 24516964 793255383 60528529 152146648 97149743 934246333 673418833 613655031 584820982 954683128 95464039 61346429 407166304 568444754 893372673 739575109 597531211 616238325 417648182 766241594 749208342 119149183 461890877 756896030 380320999 172475358 393703861 279694305 895003255 961262599 390481624 573200310 522630083 515741743 598612944 892155817 313586699 657245433 514099368 690604575 954156512 707200907 909673911 962165046 769585756 984731446 791134597 253783680 572039005 843864553 891282397 212398939 134365855 820178012 291442507 594015823 327880892 515314875 49279077 602931886 282853540 212279609 151790839 93811908 496761247 291688085 622142491 75488312 934457543 832001511 126094947 685358234 809680266 417722208 672216452 483710847 494403239 180342338 334147813 49215873 98787516 552128176 558456476 49332733 245726336 49323009 803436262 205007986 502247186 607653978 463562357 46698772 576278330 76658617 129637173 911834699 302392857 350496889 391461686 172960783 313525559 957475388 946992616 943847023 779813141 10440769 721071851 72761725 890956098 232502383 657501301 818458407 689957314 558918770 938946396 917907872 290457411 21933133 303767216 545022795 402222077 118367035 309638568 157275888 675388932 119683966 956378011 501299230 294511939 305899051 759726215 76191011 441368581 826625654 716234812 930859379 350510363 321296595 306311787 431991592 113938842 32945152 364322746 384678399 342223242 705637721 650462391 518969334 439440513 570790724 874691141 133217439 203427078 467112926 684986210 768256588 389293602 640326566 956904230 467958192 67874489 25879547 799660411 351945376 377577368 301466099 950541167 101172722 781900776 842385675 15160612 811076170 816471426 30241696 64514957 584728796 941375553 304058485 259406168 486003975 856721034 412735067 137271340 690494215 299141261 640189052 349889887 418394784 457794467 382049030 279918069 176452785 797889104 98802467 11830843 864967223 857368732 806851956 747713509 869420642 903712342 234561017 705856524 54416488 502248146 205078621 753988057 551004595 48917880 661303947 215366091 20867337 476526625 804165226 26182046 76674056 704287593 905147988 976653737 343099876 906054154 620551283 557057271 170047634 716601898 556922950 118908715 350597298 781501275 507586204 261271028 559987607 678641131 441338931 481534670 750061679 799236954 83308600 413055598 740717685 41469064 602781628 923561916 878462516 48250915 797411440 723663399 926276406 58061623 741343008 687350765 718888663 4947931 295479032 841370836 328268239 656884957 759686965 307075212 675548680 757640816 418344108 261043458 620327815 456596055 783032467 552646482 208245827 980737662 804795812 502837104 91743238 920726030 39594133 872243171 730375122 840617340 518992754 644955832 711283819 738189294 249851230 609224742 484269513 291692919 477904958 162991291 368503846 361940756 798124021 750426278 848431931 880813434 85291548 710818724 364682038 148898896 821136002 419473870 164993728 154852179 777153127 406278314 889590510 767551915 932696555 199820081 723976159 933092296 313090489 378645463 802527315 610566306 715874573 362455944 94329155 544801703 479216267 954135092 845243630 819860844 30485829 466541317 891201888 909243195 844836711 407722290 46826602 642638214 751436232 773098611 593188817 301826164 402634178 451176545 749052951 906998452 268303908 471848778 202871364 673095791 33077560 189348807 911626423 230597405 708298717 806025317 114869223 337735478 255922202 331145692 443294286 468965987 647097799 651076506 191845832 209160268 320266906 840217434 3162710 549789809 747871031 966617124 514146951 471487718 926658673 579276985 934285215 165119600 571080614 16917407 33261152 210416875 827696854 362710644 395518901 572958602 31558738 852929779 554852137 227698022 630772089 320938431 406772376 931590685 930731788 627982926 823580400 981196461 912268043 961333059 922799426 951286796 684048245 392391464 646030166 112193908 774234760 816269928 994017196 811575109 218767029 323742172 451220359 16235251 893631626 270719765 254113288 636271992 161020725 369826949 366838312 172154310 993603616 716814863 479242773 339162524 180144836 128730368 266439601 831305005 123662399 533830672 330155601 104232953 842766919 189872771 668463700 857310542 674229171 236537703 272494862 466781541 756331962 339458250 793444806 41049867 2416098 32002122 241675207 569413011 375277089 904233989 94596668 605286524 341363575 695055864 639301913 508783455 650037213 18310433 907303757 461177438 718048003 299920484 510139365 784923373 88852877 602969139 122487384 702033476 492951204 256012309 799477784 791239874 406166141 27105056 86280589 334213458 871179718 990670215 853815056 126431588 21451034 717533456 3563761 159979939 840804373 744013585 925288686 818188463 523260707 784399712 7884793 31213905 866166292 827717953 843714156 976188288 590613102 496244724 314084317 329364854 342259111 22133024 212714851 745827215 510343502 230749369 677756762 786136751 456806671 333131706 801719204 837103929 406880280 895640865 582049356 224157952 430816936 557957792 932104135 74396307 540933850 243887132 510158027 689798847 390523685 282861679 429674001 211205531 354886065 238158538 814624968 905730107 205758713 910239692 567240665 635992422 215762772 68745427 90066600 789366669 783453892 830609028 541668827 491458631 565891876 285707159 607693307 699921960 30125223 582281845 493092936 249949538 168577753 674504950 383420114 833710918 142388429 932182989 787660526 498376806 487531351 634577500 94715850 158074573 576622262 399019468 592793694 28626258 394732407 312851564 179458897 804037726 263068666 797596399 434867082 507974323 229180570 816857601 874385249 125835077 80142718 767648382 719479858 350360172 75767864 867081978 51900849 367977713 550639500 758581904 916965273 882253851 26650223 2799777 741495941 133715952 329626203 868625931 48027699 719534380 796955798 365582668 34851751 900663303 696041414 935495543 511459816 628507661 829642139 27802111 540765454 4374258 113358181 68137663 173083655 710465507 627343508 991294401 372359200 571633215 409000338 147085738 690875891 424769401 97497324 262895185 392536406 46644433 691520242 9968978 642190816 712884079 512255682 38359690 370819613 433715191 109919820 503119083 4738356 304148711 769168383 514962913 812362176 251669427 772049712 621028298 348777365 170383886 442049397 20647142 628611023 421902086 830597435 272185298 260870161 875905061 839370695 125531809 876046231 402705448 85400268 25517770 425843948 479584565 149913623 243808015 374499433 725495845 791920518 844400483 675768700 802217694 836898152 828930794 810719339 581991702 881574812 188081005 690073152 729905179 777331057 117696150 78871219 195919105 499320409 306842985 608865050 691925707 689678604 615070335 728613970 183226373 481494163 590356385 621259800 134763181 901986945 300739283 516286174 337230073 626689798 209900238 463803219 135771227 194727759 601436486 134037582 905864231 589348370 846064650 646286422 25932107 817357763 507630076 231102379 630296143 319938296 116542794 261706420 31336185 408331011 262579731 791906212 893482544 516831520 477008900 57479470 651956740 451511475 965666196 861894097 214967982 252811433 296219622 739553535 862825796 789914208 911089412 794201645 690635988 562240948 693455626 390572838 662166369 10573795 468727437 726519810 552891291 425050356 489568884 229911255 424778401 210262808 280960254 797328729 191953546 746507615 718933187 898516847 832218216 844609233 724695224 179503908 918129209 771134625 126373504 967859360 851369382 284852695 752409688 669373350 363628837 791189664 223187306 864392390 907783182 39101229 898871054 856013910 744742317 306044256 735887519 378084901 684035357 809305955 972134778 22857407 648400372 677027134 749895985 451190964 223745040 32419351 546003242 815295294 521637568 444972828 737340676 69837086 236570301 988755938 326796507 492521257 888533202 26626705 334214905 856474820 559132620 388739715 278586394 515645321 941000173 97826806 368917871 733979598 412725507 93640468 315440507 133200238 264457239 288545438 81971829 306545471 295399461 217765998 636977921 90256490 190396197 887840539 438566774 143564079 766771594 715754019 747507863 630911665 597697307 723814803 676208671 885509573 334173080 873936687 49749731 699067864 616741474 153702947 779976932 997490816 460749498 95963446 463063090 787201623 308891881 376139480 29656062 262082001 997817599 835785856 283073733 516916251 920535251 821160252 747077277 702433325 101763032 221854396 921228475 788312422 707951060 189058403 227136383 638984443 767907480 582542206 96590183 414089391 819181650 992083599 700784703 509721299 517485099 437439049 417231123 602717004 517627117 717687222 480883053 977332906 354144144 424077813 718396068 764387886 344607366 618447270 431210471 94357818 896595710 513483847 257366024 306683500 503720303 37658410 656733290 968696814 316100886 951239538 141198416 410096537 391796408 525321259 688342364 167909687 154060337 610792955 340740784 239558304 804860009 553766516 774020779 66972442 918266078 474644096 315811462 139919094 655578699 450793965 931531354 811192283 242447443 44641281 234963681 728607017 430924657 227424779 895332378 956731854 127505626 871004953 575971136 289102784 240422188 764333825 722750394 437114535 971464413 66453157 15817861 159570964 141796615 430036287 683782366 574949735 345972226 715527452 46803330 831492843 224695790 891089316 378393886 726187681 176618046 105431960 40917036 802321428 88950546 711500505 88820009 517571896 394377579 751160040 938143722 595759072 961447118 818233398 504087622 933905916 388197531 145264781 427889866 946566907 184193169 263309688 867965590 85103793 544069090 921649553 394675274 96804253 423642914 302752660 255731132 548746555 116206972 660525839 56312767 518461720 334238341 139385955 863217118 810059805 35050959 347415263 80879002 827882611 593040261 48528924 445743936 162375713 746228843 252753744 138970914 814458893 775425996 421975282 491368237 622278343 301818084 885349141 514075014 876376238 451878706 750092450 320383914 161925921 621581179 669158695 760144097 533665927 793890702 534721788 561071393 726230017 545933951 730581850 370212267 179940182 519730740 647246754 308647517 443396089 610577058 462603962 574040622 195887143 720325101 5507778 550517930 803911769 332615277 560179814 600849743 88830958 228479664 591958513 830285022 25779349 351565377 421525675 133281782 483510966 86007810 276844202 106749870 767991978 409097459 656580338 689871275 593250303 986198547 848844882 442149479 625562356 711482240 646316582 799371480 753613983 976015258 655128367 668801617 402880637 72258488 961101144 827476746 372586709 834241491 91746988 273780785 809288468 206911274 490070037 977712365 269497396 727172811 366661632 82517445 658814637 878992150 47742476 926369242 146563026 973160942 193411622 386148591 487150266 60668099 350127202 336567268 105883867 529973208 581391609 606659966 419171123 846767503 411011939 17801983 124532002 691477932 910601815 209253791 108993142 494592846 76520933 272130623 44418659 905215083 821123374 469800482 776752984 44199439 296152945 200822465 461415062 158606574 19763678 667776158 468205387 189064206 925563530 650107889 987525039 693497016 348416036 634435379 995244898 846262558 709200703 504104648 674793384 886387281 616442508 393129302 111335053 925669506 942158181 180129605 481488635 530848584 749463223 303717282 303146176 321332211 768972509 738321075 735231846 123570502 423600891 814328084 376905071 109677188 126624006 960496647 628498546 713630048 816735858 417758474 343880756 963912291 916237785 890363743 829734305 272145744 840658287 323769852 514616917 816824076 269445486 519837839 993300618 237804855 642969491 487745149 443791212 523633868 137334760 541562536 153021399 801992631 555546699 750196080 939067917 583475419 61216105 477495652 592387788 485653597 772023229 824803717 803869895 560871527 857425279 732102909 813166414 323764054 43207227 475726727 626840201 15579238 830598211 213447906 384004782 251869500 381866026 947217665 442861561 152551082 492213089 268345843 756304583 488459991 591577944 461313909 453427593 406042710 445875365 340512875 926619931 792216716 108598233 640629129 983807687 877677242 795364683 460706616 210549884 609554787 215161062 909721498 720119629 872221107 859700404 711744627 488941280 813779542 636085573 285956251 916172162 987061022 902215881 741216603 310011895 367543235 30110660 770927692 124007507 787588048 255489530 677057019 464091124 432465775 262223680 399628599 531585489 118462514 480119360 223218850 571750528 912984852 107964548 581891503 342055222 835229582 874977563 261163030 743971491 668527076 768901563 644540881 429683417 828276318 183243405 582583761 632042766 613202242 982601479 329813613 406209672 33539059 944865123 672896109 282683167 820081797 651160596 60361659 102334865 805275214 108223821 296857240 409972450 574729712 310237551 189088042 643877083 131971412 989590032 66662406 259452490 471172717 996409314 319326664 658612111 317324914 819311162 809331950 234179958 575143034 260856324 930865485 450867520 97893566 873503031 38952608 64698311 902010863 8366690 760104359 40663873 522216689 394029525 933340492 417597082 572201420 975524817 950138368 530729551 242659658 591766385 172045788 6156779 788772623 728966031 151693226 732482416 978568003 523787960 698189614 662428070 40405597 80340691 106841145 729750245 295287575 264779802 909734783 266752457 251970594 455939863 105643032 641593437 210857043 55947993 350048777 836357935 850308717 844233011 942917003 463344406 867477199 17931919 850994386 520419572 392166118 271089821 507374391 810180768 635278315 94891899 418446363 157366619 264666424 171729315 653464405 711989059 980867706 186791813 435624559 156099713 346378567 271657320 901716228 386519444 503609145 646611084 431831677 377665363 877060640 148432247 46790733 233076070 171704135 571651309 529859778 318220893 556965743 509646997 697844924 516664410 161421991 492754581 418791827 333668682 947117722 683470204 68239253 34425306 599613361 637364484 415452052 390732194 376817201 283297172 722817588 395033143 234230909 127940689 907806921 794493923 375289080 583596023 87675890 380730749 630056207 997053767 437477845 548704317 754661590 52281553 15349243 70762612 628144609 591131567 248232691 332308607 963685157 293177836 738189832 330289558 538838470 43233851 821647618 851585535 230541918 324694028 184028243 64047402 217397910 955326988 543691260 90855498 652121357 419325061 817816378 905253399 805821469 175044353 971597511 316536559 778798449 873567616 528479447 222662646 396564213 255441741 963772034 588115420 855663748 367551362 37329620 429611480 122981013 912261041 866564816 233191256 70300223 312185679 406908898 953685564 358512337 179739968 197674942 670499356 281791666 193028448 468989588 156262529 851176844 452413805 237148913 605001567 393653067 723973993 314436677 916480306 233588761 417703996 706708122 94832462 205093426 501432896 783612225 371892378 194128638 664154142 409857707 698962910 580540885 634524443 816654937 824123985 704695437 845263886 492537641 453908956 118969045 438254261 440731349 527399298 577636140 196640147 300329617 688119139 873303550 299874374 9756931 839687421 382423604 197647759 104074694 396708725 482243914 542774418 715160454 74965191 222066396 797725653 458194094 220362454 804805087 647667422 611930151 101452742 95358603 220844282 276096115 580464567 139857617 822576732 411064335 41501205 282585289 864176189 208801382 899436224 573178731 915325514 671382129 968397073 491509314 509854149 230164505 303096652 144352705 376757642 212967453 463616083 482409436 438858661 963428038 802680355 736087818 77187174 728998329 434825252 858858361 344261121 728925375 660679140 57370557 483025136 193831908 623273348 325162435 854313401 435882327 42663224 617198576 121809722 989144081 102097322 226835171 208702245 498031775 556609510 120771357 493466436 936906558 91226896 910629753 538247356 348762252 333142702 344165089 165833194 144201578 284073317 245842151 850980708 214789210 313163445 867023982 896256169 210488051 77646808 405741729 951640212 235774663 888720337 396753916 525447771 971114216 64833922 645701869 114990897 731782030 997718782 725599622 78014497 287401620 412277700 273450136 351510415 552066546 629888748 393591401 509124422 564895465 845216443 829011711 256416624 796402512 4098239 874436691 243725386 778019533 219787909 76340381 605327800 481326266 363323254 925283842 440234747 139779122 528534860 550211668 29969218 281135241 348666286 52190787 132413307 350024006 797885317 391679292 666190584 499445323 50541085 960017064 89192569 16767153 691544445 870449108 367941337 10345783 421513137 482181593 905845475 921068062 718561514 305202929 168611530 172762002 790276332 919526611 495328214 697003279 580520301 422113296 418970405 976849700 657857341 897389134 844675322 453244614 934204572 559706600 585401841 999164879 636600364 187215956 384436096 769810645 851216869 963294360 301621568 365921397 274649606 508151089 334870197 919985056 778895562 189325616 315164241 443798318 543175990 397459870 119248987 997348332 199116383 178240527 714116461 686982508 953994343 920796941 229417566 33311602 286411379 143856115 121450907 659350299 956144195 476465181 119504040 869777072 490519253 534581340 847288903 230829762 984323288 679877154 748704044 524877447 739900028 290285810 275964992 5719394 474211477 969976524 83158089 727797741 751973847 337432487 234941058 68484562 254657447 899059600 346682179 602499000 250117885 389663060 805315652 788103952 572226463 647010317 161677582 408370278 63863592 263438070 920449378 424724882 282008297 159042251 514897811 372659155 474967345 741652593 566186574 362829222 139377408 185855721 320496059 308482089 237545297 964147484 712020347 342552287 208365059 827131740 124424056 611616248 271388851 711056537 257747344 707210577 693133110 923556053 287517234 586195358 897463741 38826264 318634389 277847057 914416125 827430589 204960580 704835833 36043097 30849886 742586665 153410766 702549395 103238924 154027236 466170217 980874039 674957701 315225768 412677960 343124268 619692619 694140828 284222911 905651226 742998498 125104609 418318701 753745860 920189866 308051470 950712464 650961666 35056410 376508886 581663941 439174329 86175516 7212281 938278522 718926347 41617094 527182656 874654080 374303983 119516046 767031780 156996190 226908187 30050667 807198526 407990604 117542976 336052198 91561100 970816899 756428408 375745453 933030911 353654896 274541739 74153558 569676666 550350488 529860993 333927885 796761996 503928579 689358501 430887116 329638005 75120860 771375160 694527717 943637925 23561343 204581245 269091467 904968839 755675977 752494960 621438695 492541266 826606903 785280449 198444960 823479471 497863610 5746992 668277756 631550683 791288585 152598387 447039390 765315818 165012992 656827887 383102402 307522166 469620867 154623595 33920729 540587844 527196680 30130414 352921210 13810958 113617791 618580307 964878996 600214817 300794238 590764153 504749668 788632993 367786071 866894111 41383019 45951422 661958780 532110843 689181691 722254687 444202931 901536443 228393443 843953487 395295843 88255955 434595360 793142678 267292826 60924424 304692253 596544709 90783393 351856338 389847016 57626012 966281573 728139384 842786810 14158553 168074381 609199971 121201733 684492957 913711615 864722837 840874975 902545206 806286376 261211463 620929704 813354792 709508950 185573680 668912801 466401837 383169798 792823281 27590387 488547166 213595273 453260561 208754831 668151694 266273125 9874687 889143974 542464751 227695699 303704155 500510383 366085954 868039259 26853195 412143306 251882311 34681384 380566899 569565281 545110580 396725516 927939930 716986013 380730499 42889183 827544996 972400050 459251769 138275827 230014502 553699114 899078064 852693153 109029482 94760852 513193178 501858818 554654679 495080957 311725239 351035482 75001732 383815961 413692012 677559281 814046012 541860879 819480845 442964239 394302243 79312970 890580527 457642963 892384633 624940231 611580138 429872268 636203390 492363059 144461196 873179595 814869467 835907491 477803744 261387706 150351026 180942280 124218497 644195386 294642730 817617487 341620592 424983828 644147745 558620327 398155563 321493380 760140089 25560115 187934795 4114467 204748017 157583884 28275306 595487474 175923739 829197991 726837448 286116574 494027528 636541820 756849880 150616554 483221966 43867960 435576974 446641080 180599699 104895419 137531713 70033541 619120579 302510030 998848955 842841925 953819264 779507056 37689517 118865083 765118933 961622142 640663706 330508089 61326880 779175069 673066129 792248050 261411698 161171057 817426052 418892672 70695914 556372514 675006100 60775332 757906113 955509904 116447705 452587057 937789126 522649134 871359803 263643394 685291279 37704343 385573795 361631601 704212599 633307966 436658140 105938405 527095300 45449750 386200581 124772993 210378014 626892189 695702668 320960931 670051728 864130563 547589615 182269446 963068545 887992281 174514444 326258822 365268817 210361560 290534642 719345415 392328851 633178204 577503914 46388304 154855647 660500066 912809317 851893995 133234911 706366976 996508861 914706419 402531472 218317643 485579547 287740504 345470948 319952166 919303019 373369071 801988328 280909458 137992197 192753555 167137332 283028687 112369682 54725613 630100909 254195940 554943015 145847920 105138128 929761667 778884656 201582583 139798296 468472251 590035814 527190560 482241896 181082599 309836038 962661045 283615835 682601694 316656803 784962731 176729319 885323566 548707881 69134236 248182983 685874158 528431363 455833807 854478613 66545812 734788544 51244375 721873445 141783059 205819306 286833497 294880346 405836397 378485392 281357273 94064776 802680516 263119741 442806066 506588471 934754600 474676385 620528212 268166374 613674926 632593913 253384949 218616575 207735834 587650700 372943936 151443669 315835871 102695049 158797699 249928651 773392625 800739552 262425520 865703648 638264855 131490079 987643158 790103569 508654544 382996726 802166643 817091836 555538515 13594424 196348088 75755853 881043250 731011751 311205077 620678376 20991640 515853082 684593681 246662700 75064668 413791975 841129297 876638398 326442449 489535280 597527804 764889856 239258783 126164452 792462335 42175676 479649657 231113390 193456780 582840786 427728773 101027597 93144736 858684713 354957070 7277109 132600866 430997919 905076297 740435648 901881694 318208810 73281935 984376559 501181160 137168710 243820206 877612417 88394894 723187455 519040600 16597425 258238931 103733741 56571085 418271860 816382584 422509741 899218641 619376473 226639271 151343531 864612490 982894679 720964959 852538906 373460899 460964273 33404902 890372335 39008917 783426957 755421656 786460924 997342172 230693785 763029083 717252658 667136676 834912390 560088196 493514177 751463011 379042591 856319181 298060557 879502099 4409575 377682586 526928523 444163175 319342139 792761802 328438997 372068687 76752350 714688366 269942766 993685284 858723891 46651333 593160110 50173143 668104802 411906203 539280783 978230832 903714087 334675393 447868507 441827475 550666381 488906083 261058361 972228228 398082777 900138121 772054410 567672263 940386057 126737223 371820115 356008879 49513136 608979400 692839212 315773097 398920987 517388817 175403672 922969574 241130819 998277722 863091159 968718095 917966130 418557117 281789296 24122410 425552379 139957942 515192964 911842857 416825859 82057159 847123110 430246939 451448573 326116220 388082947 730932099 675503474 41883553 131089238 559782846 347720458 608444312 347371333 362819086 520714975 56316508 819173521 983864801 503932621 726941310 251158799 484911499 311567325 787842415 244261449 123264143 288445000 730529836 288079718 49866614 507400535 813849384 724557640 318366762 946048972 508125031 437635486 93863535 248932313 163632684 305518215 639611088 791824675 276122444 979541662 592430652 512755447 961894350 396075739 173462853 983930046 489415017 898480800 624057378 853859820 571207526 830979718 537140595 744791 224774482 243481990 165334001 900881940 611728284 118691403 943064627 652742990 28142419 298638494 945500147 247204097 186029566 254308016 348937820 136959900 471896649 714317381 823880144 249201571 746253777 697054736 821631768 235050542 57907938 558045720 117804502 958236841 142029332 263721337 646530717 314367419 605503982 820548760 217553223 570954075 307721387 347404174 715527082 760845835 87271930 676468952 790312035 33397649 120668731 699805179 945861688 259442132 665887739 280467640 264014140 663440710 161487184 806183084 250069453 598728778 696296849 199930363 498669184 50616312 53887567 799708347 574728319 494403389 348039111 329521667 176927187 21582062 560186063 820282814 240587607 1234263 141218249 20842053 869396203 783257340 396607358 915195267 658122667 5452241 363498667 829051202 193269256 602887958 872149192 539469081 820101000 374725285 600967825 782531618 518488230 776655449 672112949 984222450 568842464 569970353 786441176 716349290 107257610 87269328 107852218 114916496 677989537 251175251 830728610 401470282 367421329 481393411 881148962 557812870 167974554 670529782 317502198 240851484 39506572 149096267 778828589 154451313 128171319 793379127 790741303 173785463 596614009 720174813 58408822 479635034 14642012 150560354 350710252 772772967 998279194 555589221 321452526 105538291 717922638 49649551 98996174 349422957 98567015 889432558 611294546 259722178 686122003 97845288 491705079 137663918 426891602 436600873 843107088 604221220 442550022 900468987 138576641 532099695 988304779 109493905 915402034 603548881 997893156 888867481 798233936 113906396 565617207 312185766 50532617 3305497 725342865 742617368 494162666 967379283 800340317 125319379 364337168 744072531 771785505 843732504 99691750 474777036 315787440 468316542 806138467 860245505 486587860 643900492 326155109 98063136 421047864 177228998 95507882 311779287 661719950 193085633 42012825 61461859 670391462 452454431 878692630 643217646 716782065 436237083 136266507 678341251 775513216 137040747 544528100 774802228 944982314 573642616 727165381 599410943 935839523 671038723 413702702 294922115 636432419 224331938 965135802 436636734 701078860 955953024 929099170 718906641 776699086 58470447 856429350 268374559 228258279 397736453 244829903 26473650 811647758 324945677 765456296 116273651 283704847 62721147 191105843 454557404 887726266 956713857 417927119 370715053 529546593 562813977 591790548 21913441 140977228 936403129 369758694 344151490 120390255 510822793 11623921 194148679 684772174 168174106 16658079 906825971 115063523 865045475 214299606 606052678 966490367 885233099 518392151 102191186 513983571 307422795 233371946 341071107 811335366 775362627 14404840 877049937 553894695 185031257 579970402 296474671 733672547 956005881 505456194 275654626 397562962 970850818 270872263 927036555 953705105 208968353 378073275 474350572 578384524 495620516 672903245 343183020 808073927 957030375 427374352 658537359 420923642 49484213 134055027 170259778 603269714 960950043 184834406 402451459 731056550 306063733 607341304 259022393 123127610 291806423 162110277 596859239 819588486 253720828 713588105 774242815 983594454 95586279 174510894 471129755 5658074 235166858 849645274 826781252 581889439 760176475 60857807 784424512 585450885 830299186 601975343 340031878 868969722 300165612 980262090 973277484 342533810 930944668 824826186 704444891 44012516 89489392 770080887 32037069 128270869 66328279 782846897 470786876 132533340 978616149 489067155 822604550 479006422 209656689 47279688 852168709 377180589 740493971 170375042 431791164 108497702 111532336 306148562 469522560 352224880 397775032 569817962 698549367 724405800 131202365 740925007 832030742 810866903 548534637 221862553 866106849 971727092 375514798 312200166 244519987 437962533 339157820 254244845 811075151 862780709 874591658 894468752 149475373 572283387 236218012 602606734 522789997 343884089 437929212 960038396 812157073 401881056 39929464 129362636 491198597 81835673 292291968 52568448 336247539 8738216 646816831 276562436 478408038 477200127 359699166 712992726 89381578 176204630 573869284 435760789 199079752 539130208 849740697 153638202 542571005 366580711 83804600 649717457 406511514 589047663 998246737 426774776 223906771 556186836 463277790 279338664 718067120 340400086 901511950 200728177 254848931 973169065 613451098 332931450 62858259 847388533 36727634 715664301 837361205 542131755 22777722 768113141 489854500 891702580 99409601 478454576 599735177 449405136 438153909 525143169 65560950 311401442 241557596 370323408 594368150 791054079 403339328 734146622 800869868 200973976 324541517 44507779 522362402 135934767 589403176 899805875 105986538 109207071 524676675 972381898 491447529 123345909 316911671 898477006 627287160 815929242 91502441 309055328 13513460 295890374 816444679 127401376 841848912 792910222 920968567 816790833 504419925 938551104 730308491 103279486 287393628 228273917 19561010 662715843 742070059 812287079 966721982 32726997 105154908 788120751 252707968 307749523 488073338 885511083 491347550 374541402 132634749 309320758 692973740 424610730 180059621 84405892 985974542 789935718 108055474 470929061 336845236 957708372 689832201 143727918 578775469 229822829 963475951 229758893 846682824 128082226 863375670 756292550 355044018 716320434 737038716 592421349 845598940 286013155 83053489 593151428 147870801 760701846 113954158 172373221 6926643 367374865 290835157 266877535 328397832 399489757 470244460 241214484 197963169 228575175 197558542 38279525 632063501 949155710 159801627 322553488 189776548 904118882 309409184 356943542 143451185 938624762 754369437 744574895 266964923 345305150 153397682 707054254 490032991 754734943 788168694 114562521 995868163 687850480 431255113 898325950 611581129 534824427 413762940 572514663 885220958 38152400 652217186 541192625 521599357 195422944 381759192 198389471 107086463 22933460 366021205 57509743 923345395 720189868 146841469 83833994 881603341 823580295 756219656 713978945 410978384 210156519 601357834 585020520 340112487 648517794 599831446 379008359 28933060 652566717 343718031 313440301 178199407 763952627 502029292 747285305 571459681 155460688 87096827 670894874 107885067 851149930 928155391 200086753 381877521 509043500 433682772 423747836 691126523 490646241 564173135 601243752 447557146 146101115 67498935 449168010 715457364 968029107 45712175 790117845 111718460 394457848 521252231 21188388 320940960 636059393 151826459 262360659 491267702 533218859 65291068 556477678 283212612 613059718 381100062 719845842 306921562 13895318 589885577 362041741 925977364 618163013 718141511 180252781 143614943 81256035 940972863 561158468 236729034 65208886 39503921 915820753 83063721 426233130 961317783 875246741 187626302 606242062 79180570 730109613 904030426 649746628 380633583 441355233 997405793 946477069 758091748 962273701 433206416 420479940 352746420 305793367 302752151 165739787 421374055 794800450 228343351 876569815 92569241 242344517 229042634 8343341 352304965 977428965 915080642 836782383 652739705 331213070 967006176 813736202 488648543 731921079 490716806 75789478 571385351 493064557 177252045 750679225 210058671 184241999 577941666 153170576 902931675 83499384 589128406 369395849 944178898 857715020 14023882 629568228 642503318 926015260 970515797 247392396 409320180 323920373 444193149 577159835 822271265 928997750 962651864 978163211 768652998 357667640 798100669 466150543 963144373 675817942 940679526 673165975 881556114 537968916 632054764 863639992 920859247 343240627 959370774 659839041 894472628 938036493 810985161 653474844 248659505 840214142 798544215 420791095 28240117 838979872 282786532 655411745 395456811 811924983 89022853 578728046 350324271 269972015 298180972 33717247 478861465 721966317 804225280 173745747 745409277 372103441 182228386 545015536 900990376 656324157 222750152 663292392 839305124 710092542 896883342 437376990 501321955 541137532 555391199 936124033 664048612 151682361 22777369 789665940 871605802 242066156 58692905 122265736 890078445 745402331 726772222 370462862 674426761 316999972 225407628 592499681 71378139 525296392 785060388 993722821 136666593 588530524 341582578 260031665 681095396 906583395 885355213 943039303 752201139 617833774 197567010 942225058 384913248 525213318 847573601 856719134 957944977 714165602 543634299 382792280 561549225 386077465 945063977 128831037 845401829 634384237 511000505 372426831 392077622 962060109 642277641 337289224 851308745 125615839 714789450 629595722 255956829 332146136 20883614 242996649 586429510 653297463 527884298 858645020 105579083 625407666 984268751 118176891 492482572 464848033 797287408 133754288 60848890 109385367 994669798 368194081 733987090 432580323 962567596 603529360 68701854 777580295 536506198 380606987 603632541 263066703 972544446 508666316 488968751 132769314 855822903 459117158 502421044 297459668 220247820 438974941 305876118 154399978 696553300 87140400 747948052 804662005 877756904 894797259 959999872 785656160 15639065 340875359 269651140 861930634 849590295 548016168 500430510 515349422 748973906 392509463 656704067 704795973 21629552 490029661 178118404 441585757 215476029 149200158 663634011 701424196 743794851 149467963 322956808 119960262 942129776 844375874 771045277 237207822 888687880 500944104 533549386 449503195 67688188 674158266 47140223 444349378 495054463 935625557 709261531 439662957 636094064 682570422 212126758 650922517 669446818 68651020 459265062 325110754 367237571 942494223 145757330 516651492 656168766 284912957 881900417 58083380 433134543 3154976 825937147 541826543 976277475 506086186 529251996 473857339 942984148 167671062 542170644 164602105 92497014 683019237 931279282 520189375 64689379 100016538 159326947 68093140 701232703 947847195 531305716 761957065 863172942 191033859 816817818 10614257 145011105 992130166 155456802 465411490 420825167 98386266 548942210 570928355 210773270 102399929 155322898 561183292 85910385 509605488 675888155 907819014 548416660 939480540 101147853 514877285 811729476 714496760 942303491 43985209 947375423 604555508 161990248 816933327 603728147 799595387 538768689 554961396 86197794 930632064 913953660 505596271 137728797 947294770 864118122 518959054 950419364 66572048 932929879 481657333 53831336 953716890 983744510 442384927 683654067 362351633 871518202 927959078 267349538 411494279 802467453 540387772 456760843 696144421 437673778 279524206 327793138 142888648 638581820 440423956 937724512 498268844 78889384 697646633 597276413 845337869 150052146 408413064 889540815 90188339 737053858 435994097 950912917 291676230 625295095 837155221 4028789 683027744 302246005 664458178 443507367 62778510 279615119 914660338 434368567 749856400 413126745 103704791 650792744 579723889 574805385 962848365 512824546 58982808 757289929 478724999 324540810 893881173 365919579 225784827 278683705 812660342 376881051 645759349 87832454 693167743 909718959 994729744 292208858 590791649 513233719 70730896 998917341 806935857 713331975 755861248 833810365 685699120 842061029 757874342 271696220 845401616 588926583 29723793 674709709 733385679 167390597 895582147 611896282 409200526 914521522 408022627 429243825 692446845 415373409 115729513 827609026 477476865 653157927 815445653 809480135 220432514 453886396 889414354 655262105 860892420 544821002 377185888 692298351 558374250 57989208 881902817 565067824 461425527 356011935 878479716 485051544 493408038 334225189 44188914 191914090 616098416 107901187 413777987 515296392 699957361 723613104 286628708 233913918 852933729 598068610 610284334 250266174 202255330 810466968 626980826 848749544 686559008 11920713 101688319 414387286 34042298 133785132 858514379 809234288 930991683 718719218 449336093 2067540 507421885 360508727 660263148 419097385 757714678 255106506 815880150 938401424 309941037 74278708 277027209 883125912 747351783 674151830 311113155 223783715 308419248 540204505 647032154 607639496 277207628 764342826 736594170 325595929 962130509 872669035 643123990 526450684 328508560 773516847 13134963 387721663 760203858 934002317 902832791 864635360 411537206 72234893 441139015 170393971 371682782 100251789 96736988 989606217 74610177 61162067 859620339 405472532 970752882 812139411 450249741 863294739 763921249 268861493 201267725 340826684 241773116 489860315 620441996 119742686 951784160 52140791 378146570 71894604 93486058 989827632 324746779 472368455 117620204 886689391 700435716 23365755 13100675 129421 587926974 79129211 246154874 353886756 415963250 830496435 837196422 776321026 98614454 390597161 884800063 424860072 935647554 293700462 668975609 363190686 117565125 810777569 305671275 948635837 148432897 702158855 184689374 359163030 596510322 20660747 44992777 610220430 323306681 187031331 308483167 5075101 553174674 945301028 630692641 604355245 183414720 746209074 357701593 82361377 415795463 623593282 354240757 5245811 667837895 314981235 499996216 417423209 334904478 709572872 677380824 451970484 320643151 729105001 81696727 908828299 871179594 749340036 644653881 353159644 39354565 766735808 842020462 84170990 52645191 413768970 248075017 90541655 903223421 93784407 412472654 874549191 383602182 247630113 777021172 367836 61999373 741310081 665993872 694863831 37097579 738252607 113771362 857194151 526334511 292876043 562698567 547668437 883129911 533574192 926955192 926840549 451411886 272716899 292346097 955008500 605400764 486270893 970652049 290632905 729768583 876092259 898875863 555343596 325679195 830694578 853127001 901953156 134206277 652861782 831442597 981541939 975441458 876281779 276580027 369512413 813385200 295929256 356700983 908487287 80227942 248137752 502966990 997147887 49225922 593590969 550287061 437480450 938139450 638244649 889296313 306158882 217799361 400337275 573776857 15293220 86179456 419231765 926584421 333773474 810211098 654911716 458411874 512191525 20188073 606540465 697133713 487081233 258162244 594824038 49414282 219412379 332507692 196082336 669656605 429965680 992169085 614067252 786609936 397281492 460007953 466736816 270338079 805419308 630620692 56573360 301619100 38161336 596501718 426558885 395012340 938054462 764536061 521375033 618682221 227436215 818305093 439552909 448650598 524492357 627307531 678981221 974021569 951777453 385172385 164756378 546085547 592819141 78965122 602070331 361176360 927910669 885730274 789752617 64827205 498935677 814344502 903624794 468064432 141929775 455420499 635582403 621533329 955390746 397856858 498359453 733197112 118924094 724858864 752728538 18759353 249890307 907965058 669719131 941589833 271142844 962563347 324951317 234623009 800761741 156622574 41551123 775625328 52382204 565085049 309898893 436988668 604254507 534491736 407443966 558015625 784855861 388568634 189420722 833710992 944552953 520752508 739968972 835414088 929672117 852096113 687895636 2539088 201045513 93783542 866152363 771887163 293338610 776281600 370471896 433001549 272036785 84124271 872760792 355330054 716241561 583580270 202492796 484114357 105044654 231869871 238573936 194407786 678356274 533626061 383228671 916043401 107957473 898955162 965445942 96279098 917587363 907577568 367156807 102167960 517126301 171298479 15215866 426960081 98560858 744847769 170388304 84504080 572564951 594655212 971219357 717312089 353957256 449010936 655286048 860848626 478384069 555230268 731907913 232666216 37837077 218037140 117581516 138944015 596117060 162867440 840378251 692445533 451760362 650718949 498812968 276113439 371641143 70905809 243146638 895765399 421053012 716902884 407974714 162749384 226590118 456478614 659590499 589778266 768980428 690474370 173130052 673613847 935783214 527649841 605741769 21436619 897852275 415052118 350387189 203301529 841991239 615986247 814164206 699617367 783292492 58734255 800244490 372522492 273820683 351384013 703798536 994922229 341370114 226365855 42363552 525433407 407914029 809650979 906431471 721577741 882605267 397881427 950078861 73915708 502875968 593321091 395427215 236546934 625923528 157404680 774877951 655603588 748959375 314234489 706216440 737775655 835462190 195430231 678640149 466333275 957726230 498876985 435697787 115353677 258504539 795339798 186551835 241766549 200499383 526974869 483783003 505407245 749407868 337444526 498201061 340935212 507229842 390667521 184920365 239769767 233261673 960969943 107739293 729564184 282399065 706797973 249109051 883176768 162630119 19395586 827357622 82952614 451948840 591857428 363012582 598446545 240260407 94654271 787230866 189452150 143010418 840680925 889952343 755694894 923011493 309989225 53000166 773063937 799348534 688907821 307006273 672351933 669110369 557798493 205117835 291655201 37738658 335630868 574581164 896105540 622621605 696721200 645001789 324638068 947175102 240926693 596360278 38044920 667580266 373838840 648829930 107570922 201333900 662843698 729842629 230917041 182753503 643192845 225785219 214349100 880383955 895625050 612987371 824963962 268215037 63721694 989815275 986287411 983582642 643237901 221529527 561743420 785036498 636413401 858531638 470899763 340392734 153956610 422104376 218074426 530717129 834638922 811484142 352767296 547634105 393807174 196599121 842250118 234704665 416232984 334634807 304244400 278583481 227060019 187868475 646229547 291969952 860939894 582133109 917834888 492039023 893458086 543563347 118047312 750662563 519670064 39666356 297249633 872473576 117413875 663590301 249445628 632570277 716784645 74549080 927289952 41967634 124494857 780593061 898904556 231289072 753430101 648503850 918558776 549784000 557233828 551010012 18210652 329852195 718983162 980835889 170447104 664761842 38460450 412660248 311042214 14578162 623810870 203476402 243205086 441534901 901634277 689643690 917268004 210496384 307451277 953779621 148188199 538694665 364990372 123763412 634638980 339705842 198830286 623693905 557669771 920156625 154549029 77018794 356260277 711079685 608206589 562264852 310987625 706912271 405055275 702222412 2979231 689797363 914415939 927741006 561913933 19005553 206751276 52836073 559110121 859927155 39168567 663466456 851185955 276328805 241840584 608569597 44175714 789759182 717484096 908502530 149949282 203283564 594489782 114845464 906630902 378146452 774039134 567981023 924109232 67763196 349701745 830875106 67081356 906818600 766640586 972562105 230012471 291022104 188959623 627968931 889759813 906937336 46858722 210085611 553199593 609215549 607122146 423316358 586960945 445332486 458177196 802481506 645709117 697645039 991804676 942993391 164152532 427088623 585689839 621926642 312600101 756797502 849698646 662186888 894339445 947881834 499507531 153687788 74959550 886942481 928307351 900928589 391804033 453020340 574330143 165651425 572732248 1877908 222546508 675016150 220615663 779630204 555919071 555309429 495020727 682421684 769087872 463279340 587583978 168058118 84344491 463753694 680349940 797437772 949202492 870963340 779191008 782959878 473385421 603144932 754420115 625915320 230156256 126229851 106165450 390675243 103122821 236717978 943143300 501498992 254051086 89117753 230522770 634580602 25797548 553131086 283024706 274393664 971422082 672001379 551086103 15087701 541279598 647364990 693888956 14890550 616869330 248276800 84602214 436964503 249780934 469473395 3854437 630094083 672323469 887683194 408943429 417280468 744826839 180726744 565613914 682089731 295884447 163584040 55776410 718548585 737103057 105564833 739976604 508364122 76582039 399045516 839293578 597420639 95904313 88232814 856632969 146140594 364419951 376573070 896576339 356666685 268879313 791126437 706908530 97733793 762956981 458687506 898623661 46459993 739100534 290893091 260353524 536709169 934333780 880088456 496058984 829512998 924544757 201188050 78752704 21316118 169786119 596465012 286941830 981523123 323035542 407812323 283058973 74531371 139036345 725286516 742790486 404277179 765100884 227848643 889028932 99936927 185870051 917134483 147193605 452375694 845986696 655594598 616038806 145302641 290724558 996374536 777751288 60299291 605989014 649676327 18449989 78872144 701748308 333791825 234438998 829998181 403646097 323305932 753018750 9570339 368100343 565568660 208017422 541084203 451816212 662880292 167187927 232848972 520270207 258780899 754881170 370726829 933951171 731723592 300303805 561365507 122210113 573725294 790402830 18020909 990927832 623710874 733997807 888866824 894602705 237368175 374805842 851985871 51610948 520291954 779518746 764490294 142178376 361237605 261317483 698770971 258178858 502564012 305313235 857802931 715275363 293853469 932779306 381369915 834498947 225159790 975466059 973617672 381321624 124360289 692655100 589156694 761059153 253781030 441662239 774200962 215993679 297200562 295984859 152406352 68872445 678985659 842291736 438087467 881739875 529126765 811325576 298159093 604835396 407625533 4100802 366760335 245172814 671682324 339047282 199010816 961277287 477425826 807054787 706423642 772736664 550842759 468639263 549187939 390132904 720361466 192428894 217501828 574495654 847749973 547630907 508238828 660527909 502353744 393636496 872721083 838404995 522788306 994838068 10956728 251554868 256501930 943431611 866954438 511699015 816956703 907920283 988811319 320464394 877657856 818770608 130373593 707955395 157177675 772112436 485080971 946671620 810531760 641797744 734658961 527419905 764675294 786356892 382423612 816076880 781806694 650061117 441767302 817170873 863015291 503803573 365688560 86698965 67696244 733299929 43913260 189972720 442363048 486975717 802836950 1487446 239903095 507159116 510094761 682395562 953409949 856754673 749995597 50035677 182072590 951203006 92109631 762699246 397190075 143723284 264240280 627986174 813501995 680108269 392326186 605057049 998210390 552855642 116873304 802256275 273142632 488549533 713840441 203773333 207905431 582717307 292648454 642504265 700944476 98467406 703402306 141293901 976105561 281234839 673035795 963826031 992729843 998601938 834153833 427677721 609563161 62885796 879229075 890692105 45375943 508407024 235547845 480787175 285586588 780731215 470579238 198162797 176235358 601506666 538388079 881873913 702874011 724252049 305981686 735255952 341373063 626516278 958460667 961387439 214258090 360998298 913109627 25207788 281481570 41669943 254984956 471059589 263863029 296349898 865590628 668350692 378858991 151264850 330867867 611743077 403924213 793609196 605694423 363281749 511691953 879860620 430410307 632509767 227817949 642815735 553410330 907921724 134483719 746013237 416271073 537985267 580376571 914790800 214254117 451289776 819878034 494535438 292887802 815356659 426631301 188997572 200551914 908003529 567908320 996732248 805940763 354783176 662936280 8041989 914175961 877314677 672542157 917821442 779916662 336378855 92616760 646561103 794273854 141407972 925571861 852936214 197367167 266052164 344869222 85954700 698191470 95719162 536140544 597088381 860684467 58894176 539225954 615149334 854374737 908166869 848301161 927905785 62433996 628500690 684757736 297523014 556005425 26334457 206306263 888340542 81879425 877695003 774292438 984095443 323496790 132777349 990569809 504017432 397088224 581845931 418737218 230111940 664570808 356868020 445467306 390964083 426088170 750906791 365759496 846204887 985455413 963365026 979974619 476342513 412286259 291590935 159017872 68199634 848342941 660161149 755069871 852641684 143763109 872310343 46033502 686171631 247129448 338103378 936034558 442020410 505846605 519493016 196158910 353100820 672887165 102328603 449452923 118902317 91074824 164787258 416701770 872920813 597269341 565355088 938159120 683293347 393804061 141804459 168975504 106709578 269010469 845111680 211826009 983080949 875223978 97173669 250185442 700821817 647227240 481131032 747452301 18261180 555702267 385237477 206669262 759624573 886171417 276489307 874538781 168751941 623584903 694450686 78852079 355879697 797031163 207587132 282664921 402593106 299318611 12036037 531543860 882989844 993355008 466046458 254355878 287693499 970452540 22984241 880523281 277752465 242201829 831384704 295025418 942877974 135496575 928373574 700898766 333559011 643114939 380505099 607032654 578074493 773395257 516639147 850791143 305794451 628473488 602289974 660306404 172179962 738429073 19316779 773199621 317681051 697595370 881147331 279852488 861869772 971872193 175533122 560114510 218003199 89742549 153979894 655250177 951511007 858409953 190606421 3151936 140884657 380151085 285742276 704676889 634041334 539940601 585548399 744814434 558144183 788804102 457839913 824010935 242299840 507173550 310428264 890067618 522483620 390499438 705285428 561468088 745944963 503821823 978225050 583377200 717128294 889579990 738116172 704775019 646568805 122095817 835757218 244433706 657568498 61196303 802198729 583927742 717473241 65787744 825945969 621845496 104831358 207239449 993680382 479197178 914564661 825829739 4932728 116320391 647605089 232585520 374353180 589424536 125422556 886470912 22701017 990299653 605561326 794740381 576792427 684124964 45176943 388397512 266939848 792586131 8339661 685718213 474614745 345534523 391674518 333382124 252375486 991805972 782847280 597271678 383482807 526578755 559548794 529114925 600963973 916346095 5183764 862128745 517101424 125568611 645010651 213695500 58710886 185111453 4422684 338119644 841772639 435450453 367423283 850907108 966828145 952628135 660104517 685738694 887602438 867473136 702990969 973927685 981341295 254881991 750136523 81587546 355286024 106307321 466021664 369694273 392960527 800135664 984814045 411445956 507286397 936350566 35333665 825026277 630373321 855966032 687478190 370666781 683107257 782537234 351233972 266419599 448365970 687265006 618693152 612218928 822197764 212846604 320247853 922704881 245603149 805357961 139857045 370537421 821315186 578149985 563771631 7648057 789863281 704700104 460308803 987451521 885857248 529086322 729591981 351255298 189647226 43932046 583841760 55058508 557362191 348181656 465427877 514920321 402898172 125191764 211386555 511293236 509255887 848879639 862309897 615772201 151072174 107568805 778400723 51908029 130991108 830019298 183087847 159163254 405033849 26454794 185200843 763296202 253668080 742069825 356984402 44940675 948412566 620680694 848963650 775593865 49159793 149525352 739485447 799708232 258732154 362546911 653639777 954214465 680039124 41103604 957790790 819883005 559954950 368480417 403783430 269021356 459738392 229020391 251174555 176959020 231680577 544673476 413134623 938515720 443751340 366743123 971838535 994992566 336382672 800038255 548274495 81688660 584945860 457022928 78817174 757535096 65825225 364908015 594031005 436804122 79595050 173342820 778223528 751022532 986837895 47296452 715651925 216702659 224524343 776100031 958421346 60386624 193604940 736275670 461617042 738650928 356969153 906115864 857488283 43209777 438713413 659179702 173827090 927232361 94959735 150382239 845082974 589338655 703589579 77481572 210006546 138583101 90276523 537904830 977025315 460667143 450161320 370989877 604358523 730130232 627496551 832950707 648259644 212291927 458765352 908908288 399612111 770995502 978943032 61420354 596753861 479842316 618238180 597091944 572102277 150449821 329566952 677153128 742500355 758898543 356460888 553665568 987142667 406631328 560624664 172538673 481618192 841257815 71163769 505808339 892592141 156124441 586278108 966291271 768835162 285512544 284380491 306644589 97893281 356797389 912983720 903011212 123662005 690989633 546105179 510036795 943393218 391393908 620116976 533846706 159517502 8378318 396793269 734820259 50767135 256249084 31941102 130612157 254719727 455527471 450598205 346376480 527175788 555905591 628327284 293389037 553161446 543751292 705786127 971469189 172115609 884521890 713938157 783245759 766934848 748200674 93238123 376058837 124177903 788491653 432070212 377643948 572354718 387577943 746752217 450791963 875079413 716723980 609250779 312208516 927593583 424290555 71498060 465054777 381265613 576357580 719226149 453468409 115608654 890062768 582797604 705752113 843563542 208147737 144602552 344374862 580666248 57338641 583538422 871179246 401100345 44757589 990363526 235958957 699390346 232194646 394178434 243171456 979357422 54363574 75312352 739526353 583976957 560509908 208721207 272691639 496689582 858811071 728898370 458844262 611798329 611737004 725471984 852060538 738257974 84102574 419851927 680456397 223394527 722646774 116360333 656276009 732657506 883819855 748088006 724485073 543130041 855562360 70048555 424253480 492635414 343436600 52791654 464268745 950470416 326130959 235032276 66624797 3556655 679269136 994041109 405161743 115064275 996782333 965684895 180198717 686012572 961536722 466286317 114121534 144434774 423326079 963855012 76979742 974693409 878169990 889401783 647654459 861084342 768220294 190854035 641966862 86191427 135405286 127696635 635252851 609113254 764851529 589710714 875982001 952550268 272149115 667601293 502643462 133323262 637199337 15911396 220458418 773040000 540656530 732255128 99331121 937483557 285057660 212695097 870665660 840666354 213578397 104573193 99664775 330804278 819344709 446298348 340760013 848003849 482450850 49899012 498197357 636142028 238234594 180486741 783330701 138359802 326111422 867816475 543446614 759163394 270203134 965082692 332139425 858492230 461315543 939799526 71516721 117064678 780656550 870385836 447312079 283362396 127940121 137706432 588515355 797017030 955869364 135457389 150910233 881111758 891189292 973953298 509755176 755856281 215538740 834592687 237274408 524414927 671394287 636782606 624576899 882549030 139613959 585365183 446479864 120023742 916361940 365494631 116188975 50345865 383190190 255650915 642734504 841380750 808605501 136968122 165743342 714652944 145525233 814836963 283812119 102189334 933387537 765440265 380232763 270790605 959230944 671654892 627467813 909766077 535689713 427680631 186831179 419758007 984093636 371264018 324631769 125852751 719920311 655652748 145509178 467106219 948439759 722081022 665541290 716898947 191290013 715599436 898902667 445958883 167239666 284082290 818943549 967671012 96517062 280339626 297661433 296173295 649948114 867258979 319467958 669472213 768108592 980628740 192279572 879084768 41402685 798794700 534588068 322811655 226548065 542669488 996320294 807247549 685300841 724836259 86849801 88655823 19337616 900593556 114157252 360715529 477371463 581009283 144682388 543130931 54441660 87202495 929218834 955607832 568520083 713029576 389829686 569674493 960629724 597676332 919966342 439948432 319955978 24630531 906412076 305259852 685675052 753507552 358827877 568506233 721428130 936902770 601363890 891189246 66410314 183549310 998875033 88651799 796387422 571889310 35467414 897868482 583650765 859628687 331271990 928808937 459778292 344412603 381988427 769553604 33069902 832752836 921745296 595137730 175470736 890829153 859045336 154609896 87631454 589194943 189862901 446343212 332432870 550327477 195820174 430403157 213282444 601547917 150765866 412810982 799785006 421733615 285920109 952548230 37655765 200001933 987332223 602822984 974511333 783459966 459781062 242929691 641798680 774872635 966737834 855471610 958006518 726197018 698071151 241874219 409732519 336017538 97332108 784047519 446299097 215151758 221259012 39838224 180070044 909877029 194981933 830890135 584974237 178987998 942506183 559388395 48272715 455242834 194134892 682612477 620712505 435191092 780528512 680080129 251117224 294891643 992388830 868583849 444465870 338435533 463324830 663087124 880904376 522264400 518714905 855985907 544482163 218920357 249259937 666143882 958746669 527434141 237358052 673345501 899649436 506256352 390117047 775681151 676630876 840949854 646883164 999061037 763858376 215449392 352905033 351909113 750379373 32462797 567958058 402567854 350265322 797277832 170645205 42078886 476928088 201755167 203895606 253537558 714862275 570382647 985435041 407967977 899362931 371460373 14780807 164667592 473536099 164525877 901590988 407403851 23914859 521375714 562116397 505778143 48594442 871745838 14869898 911360722 80478220 737062137 522377555 721774496 467069092 472562009 414958047 770279282 474186436 657628076 175169474 219912711 177229730 300312702 844632385 56482400 302039500 924964015 949294068 481721200 618211641 474260822 404678 605042739 18967013 762100938 567406852 929526292 821553621 126854364 993051300 842720619 850559909 721214323 893173890 794679575 806381698 743284919 176413873 481616487 994396179 105623080 531923040 232018187 4955754 570339603 642955645 166399221 337855852 80510574 859467603 97766785 927575561 82921138 269141794 136412368 357744339 357304934 294379455 34648512 981535870 273548584 780697850 952349172 320545663 985089283 745855811 158000311 633599894 817661558 141188423 243100169 821872404 808294765 772229277 674415290 65797777 880148929 163290854 49574791 790376687 708180596 444386602 303206645 403629469 500437545 584941318 295214832 408726786 596697033 103750958 815436587 199458071 974900452 751483161 763050530 913195966 879526210 617122653 498135149 943836481 518607444 326265305 450984906 742617411 407540153 677529319 907263114 360877924 11305782 834458872 582397381 296998434 658457532 802843884 844641967 520641067 505512702 937682837 676968789 231997047 927528885 104687950 292831348 466645679 866888986 291870429 498534170 894688906 634701214 26869557 241073898 75479098 380018858 724603874 311415341 879682828 992503962 322530635 899515623 420934648 730275285 828613470 974240574 202293137 15695417 452388984 753203492 931014822 978405089 906296646 965579786 770713676 367607925 327524089 814948847 677600777 841525291 736395391 182736379 678861152 703878862 529029109 556664139 318537867 889312821 503994755 130439533 2788666 408345811 778245178 205884778 783506068 261022131 665309093 568791180 828005035 253969936 983010863 743226453 905928719 918313647 103957594 277710787 827077983 445021853 755616618 259361541 718344708 694468160 56634170 809306791 788264819 946432058 768437624 652274634 171049325 565401007 242983511 590229642 721205466 578967179 464929143 628828191 217717278 618425960 576980704 383416109 750716682 594728666 426238864 844261944 283001153 662026240 138720841 9927214 12990685 240613441 977121991 971274113 105950338 673159921 697151634 824463064 539534334 991850706 562725205 394676523 507670821 184285921 792438892 576162037 342172659 224137107 636020669 38843490 827525634 56432151 963241336 113954500 284308735 10818120 343014815 720263640 441221529 136500354 651681962 886387393 268716870 976905234 139727388 474203637 417401343 696721243 431377629 993311139 295335894 512388602 546574392 768445768 437817007 602868025 147118632 635474239 77438309 783608635 195452586 42203539 946079373 77513955 396252744 892290300 646591064 950644329 552235933 659382821 15611585 548066819 67507701 173318633 527463292 165728583 885466919 528758076 112403024 538031844 207274328 657315696 813916610 447098968 430834538 892759132 136985163 145423251 511062521 508735800 254148106 526973911 415732057 189682636 830028093 505339427 925182082 918362694 420955533 376443473 664781833 120057738 426650519 855631842 759077415 32834938 513645976 711864054 557442661 241405367 437504863 145881993 798473238 302623908 477410920 846092476 697452364 696500776 543087084 548870355 817523257 336038553 107760466 815409064 633587731 535965419 97258719 110903479 557446670 953057034 463148791 447257936 765948352 253009973 68669379 67378593 902313835 929277268 856493996 948509736 414778392 727186466 281438819 452282731 442583667 308387388 408923280 524317526 925745987 805143740 528449468 302015801 415862179 581915064 677319065 138386215 476011074 177879907 178502033 618547059 787504112 136990633 696690261 753596600 80397031 801064765 958554887 792573633 658029577 584969280 52455210 800210022 43721033 750065902 30065056 343821917 114385982 747836275 870461276 350954133 692182933 119674408 617601493 996741076 769821243 862549945 894176331 440819855 812889040 125575785 237703749 299827705 356762918 944042112 974475455 470527462 674725103 887120054 932327163 719542764 271467844 477328588 899068814 251475245 379137259 553780967 397969934 239144751 789547492 520227174 155816456 780368752 643426602 762727635 323719525 820082894 253050700 936512868 53586575 878318349 792939993 744025531 594792349 500986479 328499818 899317341 794855079 880066426 232414207 762962774 167259790 39497685 87769506 915214024 120590759 906171207 466112537 800528706 794013240 368110519 984737703 456430820 434365789 531660793 262814736 731833142 648318578 149136265 84582575 164119774 265007525 790254310 750494501 356259801 852352464 926398839 647521747 348472560 683658201 214179571 295561143 546395552 165138665 551247836 365049162 317101522 729680950 818308870 29222584 321342868 60463576 223427399 778276473 788637221 93820212 151539270 264248922 295959051 313441182 107680588 75006047 98241144 944997885 816062217 781680419 95900474 343585934 365220266 212654586 199743043 656491864 345110652 343327206 652234756 368679330 65714623 486461093 153086490 20037061 581238287 996725180 399142119 428141971 42005666 113065142 610128264 151264878 800110409 709662495 722255933 336460531 990355129 767982919 660407412 319861943 872506158 58756645 976465857 380073654 938398451 334859561 44813093 145069392 816587435 989857229 925982153 148808589 520616526 419443610 32817925 789038954 170671626 899884482 100724573 241744791 443279389 507269729 47732496 296041949 953370124 614735926 882562666 733298236 204489302 985954222 110411406 197286048 804259642 429056433 906505654 923912111 44765517 882442573 869654500 180212130 559991422 754597416 61642893 135716095 866131457 952379102 628885554 913661600 312681846 787335272 981698947 917335312 965742642 130219781 781727178 376788937 923610606 729540197 937629495 427508638 572033537 780835608 397407153 284855128 766526542 759510884 294300443 697743642 83691019 850104683 883068533 792339179 743570385 38192689 281466769 899356795 411182544 654667071 364165762 775643969 288682008 522976250 334808259 96442165 559546734 370003560 391262072 491202577 855924764 432655215 735314417 111324391 837816361 254848219 283713150 904009720 97387774 563654919 150747221 68147161 652202271 518685127 376109660 731459135 987293877 608570006 531909160 686664398 322686002 633643500 567187982 747657539 132517893 983397914 652167680