12345 10792233659166 100347800 254249093 35495750 36429222 109836203 298458626 125441740 781840379 252526628 962785753 133758249 699840979 412195754 788403154 217913875 756736668 647551159 699359861 497041311 513477750 395234872 876533588 160769793 773200696 182785513 567062831 104561650 657316920 191290131 477596464 17117910 82042592 633850475 813720189 276882693 708814496 362960980 556377331 1555656 865708197 476580934 973148723 204302720 851020525 556787594 598401253 613379504 729076464 373109338 931816712 685290754 749628377 107296992 132741615 227255947 534635513 623932818 984410717 470456698 998875467 255172788 758479611 147654225 395371257 162615065 801459981 378581879 474761983 85957499 942880278 207240129 281015640 218523821 610044953 312024461 524271139 482408781 994413027 325143370 447415239 320571051 866033048 46304931 344519693 13883434 970584146 429466147 864923176 109582612 244465848 65601116 502169295 418341715 687987789 652888957 829294937 169169163 987731260 568559474 842021337 249126193 734587083 188950955 488583949 585771797 678058556 634559577 653584987 531121666 800736554 508380329 665592394 384790393 393686726 454331081 919255737 68387953 536695696 288927724 938926738 133607870 202161508 206674240 362145802 115887064 479327660 581895456 872242729 74921490 888566185 224454713 985600989 154226573 718307948 155564881 945309162 595892485 990092166 217807723 823211520 242728260 298286226 1054624 51449748 220157702 529651393 212144573 511550342 666080844 777480835 104338797 176539808 159175873 623285148 625491663 815054404 628316066 770992941 482512591 741449413 148997723 469761687 817529683 856397684 87516945 303338980 121827353 930086777 81158364 951204872 330580640 757630243 140029111 718120933 495725524 806359794 306105348 702878533 310940103 990733850 445215556 699995411 622711060 840374996 350309737 651237509 676799687 946771888 488904885 802444856 357672333 476271898 249973715 800574089 277515980 579364994 525731238 830347452 25721067 556703682 457273385 686255267 571508033 913633388 520360973 565002979 595924785 711631719 217783286 552104768 41258286 380888607 114133727 831944488 746884279 826306120 78190292 690872692 263655128 886012043 187154403 805825903 508543107 916200688 311265178 620855502 299550643 496381928 27064117 978759805 356281611 611802736 391755615 874360148 322908821 480654467 866991565 973133940 351202674 868509735 207909377 526926333 484641085 938655291 517578919 681490602 36007504 836884977 396526563 998705653 76121609 994200002 715019863 802757908 367635982 502744792 306884752 602189047 41717549 381714545 346024109 397306276 267082270 503702736 121813572 212217540 264195045 332292625 159982463 783896702 484947551 666588762 337130118 905678731 143894298 815012661 401548672 608326690 163774120 282193911 272908448 623924847 85631178 297621713 10072053 633647795 481457725 804586420 609580577 788046344 186932750 698445625 211475158 878304987 103837394 244524834 786526042 992610018 384813689 499125693 312413421 852400810 624189737 762985409 223046141 476389345 124559972 599145824 22998746 877431187 795040391 871010947 10523922 25449291 439146891 529848635 224831402 880356048 311253055 960056132 29477941 679504009 380850719 407745639 42741444 189206655 235452992 566403903 181703702 744676521 201576856 933240368 380682150 456340184 424373600 666238907 127290648 468991678 390126610 683873719 319582293 965584075 350876340 496035772 93983985 116393280 782504539 998626528 335852256 666691442 62657772 988051874 161134822 895232208 875101222 888922916 644099375 808189253 458194142 532711838 200093753 955826888 475503633 549521547 126738066 468149648 255231801 718366467 304443704 761269554 106459269 458622917 9699869 229141776 576227832 799440843 533675465 878936372 102806386 597797239 252859708 720521314 632675581 924205828 754839426 970442238 381997038 643984279 60528712 101700720 121406072 375857511 696954387 905955680 252152328 653498521 563137882 767095449 584350835 890538185 623652561 973532471 211313157 424685364 21071801 815342666 494774042 811059415 436433653 991738938 671264248 955733961 435934248 587532199 481428798 834504077 601525020 969418610 255703737 939233388 11908553 935819699 339334592 575697621 859573317 883616829 10287805 935296267 62853822 910133923 633867127 923923861 98374386 621040175 77034715 182716331 684814944 863783601 118837474 191013128 781733550 843468939 73737384 745163020 303742729 669939533 632828792 749424742 215383856 864508446 490446805 652146247 17560770 774377839 726043324 757737171 67459040 965263040 351134425 573397801 145118276 969860503 530005701 957808600 353417506 598697731 354958035 821481295 395753613 802236731 748166 405028890 72886667 564062718 779833174 842042202 413680215 540259402 151391926 740968818 160980718 593719620 594428197 769675058 27819875 788936419 276267719 436999925 83753381 240384154 214548537 890097923 633992309 733935710 395943774 849016191 65571096 956487788 176960424 605286995 674130627 921668821 666953096 802101626 22992214 500380986 163618698 475294492 112991825 516863439 4640165 469160181 81663818 805932638 197009689 429712048 819001268 922370937 632694724 728488522 805423832 941868275 306564579 542313350 644435415 679475680 160730349 586183120 237099157 605656857 384282579 407262254 129264401 985092320 208011252 270999051 389903515 510312483 17277249 478412356 89373191 434032189 593198172 601576392 489194138 972206984 420512400 890932689 324472727 987443901 289365888 546128883 402686129 715950341 75500118 920772130 302563059 873236229 78782710 969246262 218036269 675590373 633543979 798475003 260332922 931029193 254124129 986578471 53741525 383639725 185129230 668597297 337707605 815065130 188217268 234514946 297312713 954261573 784570275 959012459 632608134 641654694 397774203 430286178 621048553 984412552 574690919 869978098 132394676 887927378 172313753 408550531 464058716 938736837 445564788 941245156 410898552 714819461 135496937 321586341 520078093 632227138 191143928 396420042 325967393 624516124 452583359 552181888 45093416 539909556 183864299 665130711 264700814 537415575 597286020 783125173 155175842 650944712 213885345 933812570 926125690 945640919 122642561 711027963 457447342 459057053 48756644 110605541 13872580 58944717 462145790 696178433 507661384 756371529 241561278 294544450 418132563 893335709 57924283 997808629 73027151 294920111 237093812 288224951 614502520 712044855 213844036 441479991 197395758 656856803 799967916 990839204 362176340 977733109 461674182 802024565 367552725 720734252 124225457 965708535 655969833 803248964 284893495 780815764 737968168 990038930 197082418 206123957 728509909 985955891 381143583 828170203 440602981 892642174 603179128 800648323 326557832 623436210 144364987 888363221 698497718 827125026 640251372 922184282 505817620 877410633 211033356 348146750 498033116 998768085 141251920 620844883 100918562 628131553 160705109 997297296 447938378 714374385 643356781 682706171 13725069 242320232 718628114 826021369 743561384 781630546 366667477 889682315 175520107 762294987 177429296 522164792 258881292 845604130 156481754 921101300 133679872 320229119 301807350 858842020 42276868 534916552 416029594 702425811 69246083 628114750 234552856 690009377 3088917 278664812 329665976 875385020 239055554 345476709 657013784 788102333 154703159 232442238 82045205 547670902 263468998 705512268 432521942 804594718 400057391 569520980 11801366 136561346 161153276 638443425 492403115 900553838 125680332 178497782 674713469 936020601 452302353 648800775 256903255 963964515 695332365 998001907 228344922 748908958 150379331 539145931 740597319 743465983 114549233 142405265 50324328 405458948 424673666 480328382 252474471 398096830 754200037 891239009 2193419 97578313 222094069 222852019 507872868 544550996 304805488 341674899 162618508 911919263 55260419 581822325 15741298 983616740 446281178 877292106 113465756 730994251 415365903 980974602 485268343 747497176 625279519 639498931 135929037 873596453 51567239 265915560 20610839 443560658 34030669 854845084 539837466 861566231 455040976 726754752 837000728 953407823 328512828 697467842 501462869 597640874 197880469 558238140 198107027 817085291 65991811 942689757 53603525 535543659 215975603 738405639 181915207 344268184 767626956 854371145 649186180 774844812 607851153 896665788 463142952 767024906 303017325 666290797 500433199 995089970 406962294 647519311 531249695 916755703 365020352 400706660 399481670 596642587 91912026 378179001 323716801 367446241 256250397 549301766 901033892 931417374 727144010 963362582 268697144 857870768 323705718 935644485 169139180 816619462 406459907 953399307 115835696 214457278 376702798 841904188 152313243 758238775 264016360 955724239 53377315 80152465 446438127 464243191 214797863 380585497 255545473 665197484 421377925 546492334 519637819 519656098 112278511 121807264 601814107 621629727 240243783 592027410 23699748 357261328 465201813 619161141 464451674 673007749 624267611 812254899 259064824 556627569 97266594 883628244 562234643 826850499 309871511 925514140 754683365 802525901 591781056 830799565 444976498 960700318 165935013 902588665 35829898 705243507 174001791 460960262 235496375 604284866 258539164 430669445 979174525 986511730 386069169 538911640 499630994 817504670 198534153 938592633 442312564 755994483 81887373 240670382 264940601 996548696 445508440 807028265 196438700 457443918 899686666 912472367 241786006 897338007 90178923 651360619 54669978 271471194 859938326 982986623 73773319 765803974 221104286 791859603 259323704 816398886 290398629 404333175 520318680 876676507 635189833 654435825 49814443 852071880 321482351 986194340 192973082 525073983 363577852 857432723 394546938 588897586 159908470 954729404 5393140 96686334 672682751 711846859 440785438 747222292 691978418 709430270 541671988 875054770 183758562 700571288 25172083 583586684 28571355 637228892 443323996 738490810 616064314 737366507 510286209 867625726 269675198 370104878 296573776 963378766 491315874 621302444 432336159 877936537 612292283 925172398 387074707 956610621 322268808 432964834 327338272 771891719 168548732 443551815 539716072 926254411 58158268 651532077 374829384 643506892 84100636 904596587 498436556 773889983 425711913 884790796 71003997 368581916 585162307 682374003 414827197 835259412 75321885 366314127 332524165 637045387 399486542 781671296 499284285 868490234 205199224 985609774 12070630 989998173 43860199 540270043 186268619 397214555 232623400 936708938 410058146 594629784 315777231 659853357 302562966 914163114 68454032 463107272 186355244 997135271 391443132 535221159 198469905 418743631 386254541 925892301 13073680 180110994 559121123 732362862 45452516 260381619 304030292 580825113 423492393 486159566 709532984 944756833 62151366 82496872 821635331 906501887 491801920 994601876 479807448 926188464 48543136 237517318 141839763 179040493 63042759 494313013 788284241 880431505 69210860 423086800 245130361 740706958 143020720 419608112 342278326 827290411 490715503 971591920 640395838 886130802 702092401 923531071 409896933 590455382 793386943 899465211 364268917 855428116 135968293 493155373 286335333 905483957 496295099 704114291 217736011 645322831 705308964 758440766 113252473 827006121 171820667 855229402 420034281 541175547 537656563 865220165 308378638 613821281 836271929 850469576 489550687 899727871 426787902 555121314 572235011 707333523 825968030 826605981 107065767 647220818 226967237 314631773 311406875 737786246 614162581 928979377 337908679 541056979 751292241 996163879 275016088 378524029 836233445 878259381 228771644 714178023 421607097 992803938 193550132 391125688 388942549 451701271 113540875 584662111 206398815 966826649 127006444 347899824 623386324 936366413 735138689 868511423 539475568 605429060 71865667 81038284 127036815 910430416 164075201 287522988 606177080 990751861 372654852 624866724 714047250 757646827 516307257 544754295 498131318 751565699 83109079 260202096 370891024 873358207 76312987 400209445 280584584 843283934 390257572 468701847 398154282 453800882 933863784 992575976 3871384 655779810 499718180 595673902 285452010 963898367 82926597 721001470 199975602 473506239 367474072 699206199 503374314 772385795 406286806 662681255 71783395 789410656 704567305 865079142 26535085 904803757 726148634 989593401 360091783 817380116 19681084 641298983 22601143 25342502 25273415 687112143 56576675 762775359 289869140 993666567 391013420 835852583 493280348 992623602 100621840 101594403 115585662 671351289 69489540 644623957 166257280 324150266 746508031 907509095 32778823 568290829 153694281 314366839 253099020 527039237 177658694 413726657 448055427 595028868 324262224 546744898 508245766 850112128 53056611 508045818 462353894 519023411 4378335 932834864 266102926 730315439 394248142 997837975 634835153 693336512 145617144 856394554 327096569 918173085 288035691 617689962 14291827 238155381 66916340 729449017 538699325 795487663 193296374 402784805 510476285 627588630 266841659 270089775 295071040 902887756 396257797 582016598 527877105 949674125 302180489 343998722 124319837 307623778 461244966 719590991 259940551 521951045 210069734 779275138 600625518 821535318 415700823 563853223 932397525 951103557 224536167 801793710 578959072 657608179 387396024 661993356 118710240 332510106 15737165 595841676 229246938 679227457 199313440 644406828 617433840 983863433 249168772 832601268 53048612 663672225 659026753 828719764 76182102 736195716 73798165 97786326 558010654 904202194 802727571 981902016 116640692 187367205 277217977 913612076 48005983 850866518 113735404 289687049 242417849 683752818 173338417 395987996 161226510 501739028 113547223 429077705 80065208 783810882 267209632 572309734 146771757 555716626 233540467 817697664 775068334 898289723 506459611 554325584 58875194 723133395 12156550 397947324 210730686 795722073 17577751 399104245 298958478 715437556 152651389 165606687 298428411 430118426 581708242 603925091 793080758 926494426 24596825 596994157 247923083 662413924 78833833 408621884 376052383 494831998 285597009 354615022 82807791 614203963 196708284 917269724 723867989 806182836 778011289 948455843 89303734 791592204 466187667 639826795 224412612 338528617 230672553 666201858 76688580 221816421 26136427 896405143 54212745 641894093 146007769 367317848 247014676 918130233 210649476 806321729 101921965 460498851 427103857 498615738 194281375 267749103 623096991 661554178 695565418 997567852 139823997 309606453 169895188 791042744 125620877 250245019 218880799 253922947 241803222 441694138 152166165 297226818 30117073 931830099 147964501 377805328 384038398 656319055 464941816 500946182 318068887 970238207 539188831 767595110 133622598 968152032 40692821 495301551 189869422 679489098 556090500 791294431 461271232 908721234 25202617 787298921 138053483 974170001 10803400 843066893 328490831 769586286 90398261 103208026 74661661 370767597 160008650 187858145 140409800 632198853 681296150 734213857 395349030 512067234 471678717 940029809 208503865 391212902 442767561 514638258 162384956 657625871 418785910 978862376 105597226 600662946 371646276 792728947 70519603 225243573 42497229 721855205 331907529 488711383 47877997 474687829 249150680 324127311 834115875 960871926 56140097 463815197 568204463 843051126 306569717 932298453 36753559 206116773 646290354 659799638 374683379 656710384 15489131 536248417 43494784 344589562 109794885 855267085 644850685 784625021 453409898 760494323 271156107 838018976 204094329 246488880 27402713 646146564 662374536 772397151 253913924 433720155 586391143 742410445 473660767 823712793 412135040 649312397 214014077 493784224 878071991 975065625 230419836 999014066 249298239 494278250 369857715 382644531 288741635 582774799 367150635 574974000 12920493 183053085 422328592 828548385 392742796 890918590 280017731 498457744 304344071 935616182 352421593 589604180 100220940 650605168 651309381 713558429 244228555 519428407 502917203 810303919 360825301 719825552 286691904 672784651 338429791 672970739 411605224 812890090 163048980 329621098 267554327 336644402 7252278 897849451 176633892 429515662 287508236 788216549 36064801 297936498 742613995 965824556 493556859 861007416 231365425 904384629 202901967 858725251 260274872 696366430 102355577 592125283 28749803 292155728 480616520 509469409 251723760 603445066 612018764 706306530 319473992 920643260 114676232 357749806 387089563 787790261 605166990 820018449 658954957 719812419 133858100 915900632 476550829 946273209 99018210 849536831 316231706 350484746 617778194 852544677 295577851 955091650 68428250 458161599 245332208 527357647 578021851 668658142 564585799 588763526 315843329 605734888 377944174 800883112 162150089 968555591 521358133 567937556 376876054 944086482 16122543 601291367 428424637 797475442 154559893 862409094 16556982 190351023 293804082 664826163 216964498 479852399 542888317 709335527 801522413 838863165 252384542 799004484 100741246 162867821 353716893 894032097 100191939 179545906 738281191 782591034 80417453 289949980 33871118 926024940 595129847 645172358 291854915 445171503 149935210 539122306 48963239 119650044 229542925 266661222 718536791 877693569 22126550 760431693 170403171 175278872 240659306 248452372 137185106 831731266 279942310 621008394 808204054 827133862 94453306 149592069 199749640 884154257 355948417 649290446 200060328 298307116 399416739 830295466 305172168 852396749 473120807 625173517 181609432 771497369 14288673 879978007 296540687 966825952 382816393 720029569 401154392 800472348 108292906 680284765 283915459 535577345 251146028 780345290 387051645 532218744 87582884 410850326 695559704 973219282 284619501 643114406 506647287 543343953 748917304 867600658 351205984 428953999 91203131 113286073 73951761 347124196 737992592 805722901 114118964 660784100 119837721 136329870 330735022 770788623 93419845 380035823 557216011 855381593 91922181 796612265 543442512 618402381 412036639 950434359 153981300 634064659 391096811 655642266 204897014 847082958 415046923 611032664 105957759 933213553 115646447 889618992 27058743 468108901 63950746 477377296 69302204 838478088 473107109 805273413 370246733 404988539 183464690 390115458 176399744 980636002 554043332 703496451 372455941 513483804 166626789 715154972 145064738 781149372 287379503 456446949 315888904 515824048 334295268 394018211 153929316 639972004 626538010 709836938 424618404 482922805 933987386 943228925 22787715 338750176 3518741 235668653 686098717 810746598 120255118 400128426 364647460 629874827 121964326 453997325 3434117 70763885 398687701 824603350 276540460 712955957 279750622 851920724 139260135 197563055 170432140 428983579 346764193 422103813 579239965 624799061 304135153 375071273 22744508 967220352 411380231 673846110 170302457 563310119 604363269 917312474 97248132 165686764 835081364 884222632 304801899 898015605 309329592 996342472 228647474 532317972 204038885 544314777 8021532 167958962 492012371 584879994 500652264 789959371 492463276 752127376 128447384 467002595 188115068 301643093 436062443 436719805 289401499 553215135 615347747 988995794 82947822 722819294 145422553 879042355 117006338 880802036 364932196 923403611 454030725 870834357 86759202 781279646 108591729 840562230 192299248 443929831 371147160 697778740 110759528 572307763 367039904 929847448 420727571 848261786 297031 139426085 26020615 969702501 195817807 223448066 84023632 192847071 38258042 484199360 24854156 925440625 202734399 672407825 71987777 727426944 143327190 762470332 1404621 47449406 116206990 293733820 44521608 573769398 139806577 920782995 5975084 523809827 656925673 763426083 53158308 795827542 597315244 970798000 776646109 954111644 107606949 142554231 316659145 665445879 222062390 998147683 160572179 222482462 65748145 405956872 287507595 290265930 168172133 815227025 115075163 220983738 693515350 730090626 376125255 728533676 305511922 442614003 722073056 879995102 704730007 966046607 179024893 970342995 310551449 539220087 82700657 645541452 172155677 606777068 155505247 589389622 831282879 925329306 377506183 568153105 68601055 891889857 306703140 861809862 342056760 367768223 297209050 568153333 62423499 295932917 861355131 964866923 700714147 928123709 176139079 671296659 568693914 625940573 293850290 996979438 133610886 994608244 244089679 741458138 153451083 537378623 720901841 949415632 11231278 246831291 678571661 915259542 375226528 535801815 229264371 940045309 441523901 832551656 382280642 597363303 867323861 985722527 59492668 150886858 583952892 904994918 105109603 585373742 65620957 895989010 173677851 986472382 219490245 401960899 503919280 916163581 825952261 974535943 557089173 910015551 400488513 796685946 106607035 215075592 109104731 994758225 225550392 871362465 128435796 328595837 223297065 654426602 658911069 760189446 577204996 693487170 274407975 895444919 174757468 419339128 526507775 824781438 43199543 882411958 333669911 453305877 79058165 101206340 156954715 515142824 404286194 704760617 124858374 645651767 177622978 587260324 22924796 880150708 682426580 932932287 67344843 174894590 78796438 679631847 102306804 717672200 532667656 881009546 606775286 762212301 400193019 852149913 385297513 420112042 603581981 984599725 254517610 908687850 123056363 460464849 272434830 526563662 511828792 659183408 485943686 754141786 146724659 708139722 200861096 807390540 140313143 626807001 536473140 806610122 316790122 839695596 113187075 196052653 208809363 347695946 114614591 259345474 828320684 841397267 47402841 383484615 687399718 848187964 442249678 544257188 661791085 839482043 61337888 154495720 509226649 514077715 775049493 953655550 297426045 904897788 195483785 936894301 79348175 540933231 412144231 795618936 147659287 999345785 61076990 141489138 210706730 436136683 495255585 770095206 400011870 628782056 445230910 942251477 422930267 497369673 16245933 761209927 342828156 728838639 63260613 825139249 79227747 895765874 213758331 428371406 42989182 952201289 524307235 963356372 124533798 460764392 478263135 763575679 825628893 888576316 556040232 865308673 348478296 787457235 279269674 442746652 22902179 789547382 484360311 749073382 496361150 713280193 374445676 705187295 357584373 625105794 885638193 895749095 246990854 350663375 143441303 373793111 769215867 938421599 244022420 895036162 100692333 841208835 811426872 887312433 127718493 699941765 19134400 281520399 260726252 560672035 72276668 542416243 165699005 231485291 985289621 999313626 172289837 315839415 600974538 854917405 422604107 987715311 67202284 150131696 653350399 703158426 466994203 848776282 778706056 997064216 746720307 823417090 22965423 674131110 190205302 414511996 464342210 897852953 798891585 813518861 72938644 609647133 272584488 993176199 787960826 831415144 61671657 311960782 566760836 664825407 169894536 459956399 486121265 690883700 40431222 134444606 573487260 791254393 874266960 929853949 22179967 502024844 399012887 622523691 218352337 517361626 490377138 866333749 345887188 831639584 120134798 783100555 330733839 686252018 3552307 374461959 66485699 470140150 470785001 476927676 2784923 411663217 186630403 232302250 21031556 243348004 206542659 670010571 422375500 874227945 563362940 568308840 210706482 657441495 81517226 146664325 509265489 511679761 310551895 976681314 78037699 967035738 400562161 502580653 616654441 974022534 14171842 239834746 312180089 331335842 201291532 690297503 483739369 689225413 96155822 398038538 269498755 999931055 79909219 540882935 208060722 905002682 249584005 740156201 131809347 139815241 469902872 955748946 806973975 831389525 518684436 893036996 359279901 896645929 778545832 866614183 676059091 735311255 90343490 538020838 44339786 925383728 463888658 963602982 509776073 745179090 274091312 732188311 467564923 858803130 759516418 850784264 6210717 714814859 127361758 139145530 55221244 524114822 498577272 835118316 288227980 778168363 451739748 917371728 581543035 784517348 57468038 317173012 157529846 940769902 277475342 650569311 315971633 316516498 114921074 581893961 514981884 523057860 40541348 546676136 415551664 638959600 212401305 272157428 142149225 971593586 772276593 969088803 191647512 727104708 287873155 312452106 175626270 534913303 148691102 633542175 223055327 412181112 971336098 981988431 538578297 704567378 109874636 541326253 135878642 428461560 475175758 893319256 214687232 517057042 140881095 268511470 765152077 995327509 93742717 700725974 22466299 308548600 575457808 920310143 480598213 704506053 615722461 789670776 121330291 683194465 160472540 357613958 283645055 444273568 71966987 526739127 581163404 997776644 288067241 787063831 483600484 761822839 781641512 831458879 428761785 942831554 307045085 682755734 689865586 697933562 908135854 982321949 36239593 82113656 368312063 418821500 41314092 692122192 458588991 727204844 20524661 765904656 134987397 291691664 75128707 223189541 3939260 366843330 20668004 418466624 732373641 889471782 112666697 355736640 40579728 120986847 251254939 697925460 147441873 749341732 311922833 977743390 637962721 934133382 215205689 486154716 431648808 553539745 428374132 553970733 361511272 573549337 454734286 836418922 133903428 914770688 550955470 967388689 899180412 966301721 407031763 971633441 257815253 375118562 686439505 945987985 97552819 986393211 244132447 277412862 302480928 762437005 313257441 986098999 479266864 780081764 221003131 687351428 398792822 498456946 544340773 787596485 282494970 895673804 234460826 882171715 70625578 873809974 374410852 947026771 217197365 909923649 120454248 513547788 93229333 474777395 441496182 580479330 107046404 419478544 115547911 891104942 236978451 903065079 6283567 618411372 232857682 545186164 62647662 154920609 202317508 880916611 648078336 843660360 633681517 968975612 67815445 683138382 138048459 751589135 80205231 602761328 261068922 392823833 428048548 904469868 172033537 536326353 49670713 147858720 446142991 494530434 232399800 338157103 229345667 305511160 854876223 994997222 155156311 921562387 413588318 810006999 4106320 924785671 17216292 642765189 306183288 584100707 872440558 977160910 500718706 758392493 122919286 652167825 234373900 558994766 179812234 500325425 14397747 956190609 334432670 935460792 638526718 678066711 744278361 878893962 422415736 953753594 196164727 409109039 69505654 694225530 863416050 885582446 555868006 975004963 73462909 359127425 68801815 609974389 293672033 560459382 123397960 280351834 259280258 925793501 43298082 902346010 37388982 192744109 459326686 840476851 189173851 854326373 266561662 655001233 204649831 772435761 176381535 475680510 88092232 437926600 61081349 478366405 347622575 679889874 258928128 974011723 679154608 849717640 414349810 890730234 72216912 899968851 917213818 958228312 1167996 372392858 453941604 865299270 283232731 433017630 718742631 722014270 143880015 482900277 20413925 774534667 595104904 640609903 349891733 417705753 563121618 871887999 231015231 990140968 599590823 680618210 32875653 653947272 399409504 520272869 583611994 691833873 194460207 791914210 143153390 758867505 82692999 220348055 13251288 948330297 804896036 871586121 722077498 736009272 187309815 977388191 204813947 938754990 228830887 344937289 658517201 693965569 206600468 516792903 869291248 978786631 734402072 798510414 65056924 701894054 355281380 837592369 594113207 753038273 541993056 731796913 67041164 188438379 327260945 975997012 15362696 870761565 887879847 953045257 263699803 839517710 418213990 752571516 477520237 812049083 254377117 731424470 468134064 679093900 260545110 585023173 118004681 777212128 256549069 261031484 39521579 806563883 307057444 478150774 268783475 597751826 395683970 583216402 90712464 410678078 516206591 934530270 156665880 583904122 606562717 937326354 207428560 927136807 68936269 927868686 490094418 952865036 312665692 957037332 294064957 617851422 784136995 943969122 25340695 550954007 474570094 977786356 563903259 739612576 119091039 421155939 563272948 789877516 657765705 948623423 635059947 877742375 656660314 851365401 341308600 477094355 345005012 952369545 269981032 522933544 332380797 646759282 460314072 595419491 464369794 771835221 335739647 788048543 309310974 430644360 213873817 245561757 423586724 699227837 416158862 829817172 788539917 943485554 49193656 744332196 293898926 965561647 364504442 471346872 633616168 772083442 206065992 427160310 66106099 877420726 460976316 690384868 93548189 474833138 173782442 627242373 157413384 442529936 193345783 603486336 190638578 300107292 247192186 817922487 6434527 369580822 55923901 565172604 320545619 847902060 72253212 608836585 33941849 755025708 119181780 545071307 447601869 489907444 917894708 973122793 446135520 590526626 222689717 364759525 268551828 933384343 85113902 644811388 511143894 636174285 442982983 535318029 131879175 310908168 759064025 836552119 859221357 901407395 77253440 273939953 279252315 928472088 190525483 550862913 637376379 731913203 238037480 526873313 30986564 679295507 270467 366983955 593627786 612837456 110737979 228994226 243842088 833854860 729167607 998313764 809466241 890520422 776047836 828848331 438276723 528403716 12481114 18052198 235293777 635830351 474381507 759428983 260762700 263629631 183786196 710201903 123071779 547448679 91444616 937802903 56341997 557864417 36085470 800684349 117229650 879386958 203024437 205816275 417592343 474566657 92195815 858588684 777271029 795619168 416274119 719143447 357774213 439181234 110353607 394295148 327889456 609452903 62638997 227482415 73273257 525532238 470253295 737457226 100882322 730151989 341951155 842463072 265400194 700439698 155507050 878567344 326719906 542082593 246986637 771062479 500161563 696952109 116806519 316464427 312365165 338564465 608207504 772023514 310512857 664252775 135013366 330052196 362588762 661546633 327918547 626170988 433793053 658620810 75995383 125751943 128202726 168699184 463191368 488017611 420649248 950551546 150318834 381014546 50187811 995654417 388945449 864007472 196484145 562632194 99200858 223255359 719079220 763435580 498660859 997550272 88144704 212987456 258938110 783227557 200629458 230194083 720957881 887979617 508539235 703642151 167271681 277233473 172061086 739472073 611699552 709772336 247264894 396736851 217075773 883318284 73396604 283541607 339369458 554826365 5259743 40227820 821973210 832967020 127665245 474467999 383972317 735713892 372389296 390756920 616394994 687674254 169952886 559346631 276036344 830366415 13465668 240379982 179630481 988353635 352242915 922593479 81050707 465681831 208804594 419014709 177401445 527326963 52194923 837863765 887870 542019280 435253721 765895973 125330438 703966227 420207248 610735073 406470256 914433787 346905464 709812464 182655667 784040109 97663804 214181102 780697245 859157015 112203656 180262949 99202231 992663630 334205146 593370612 443179673 730300969 463149127 697481157 540682044 835079015 266584406 675920740 154103291 269050027 361690136 915405989 472382831 914503446 254684278 603818827 639719081 770433794 112881703 146202057 132225359 966880610 147394635 519183331 27265959 517913259 271194582 566825462 865791970 878133764 45095021 950113624 450364780 563690474 39847317 390332381 438130720 973856888 327875995 474063656 436602218 742921533 373293876 684327109 489658018 651937620 167004854 308984868 86518870 707003929 352710659 616361837 565868727 923842607 26343228 730296060 474290576 787340417 287104905 447552599 308803665 467348659 469411589 979971961 455772973 734254585 44597789 861217834 716311719 733852417 712508759 806811250 799296906 914880758 11890695 125724057 34619571 642416172 153181109 395192825 518683370 729993790 13665907 615252837 586190771 710991035 305136609 462530134 279979431 956125114 435234163 572163428 944899496 946285354 319896199 861349473 345781579 596124761 102269771 467329586 372662746 412011114 400759517 668782817 609557304 686178411 862558877 974717958 146220882 680453725 430308069 697052486 224358221 670423546 63058871 121052768 89659995 799229790 692571194 988327394 150792204 420571558 58563473 722178577 105974800 886324655 328948844 414742664 341088531 550176556 386470593 547311937 405581503 662341658 356370049 404352015 266429462 584093544 666597639 693346027 513857616 808420997 31127070 462508068 554902484 722774118 13004892 734295746 101831286 660006592 649650215 793393072 222722160 631455748 453450807 934908153 77677457 423102122 200700131 870169519 57731758 624270776 27922004 339033716 490763131 940604000 219464830 791644082 194507274 212936056 731440860 827364768 72833621 606015084 117006430 806881670 25462867 479160094 4675150 185514383 446175862 642482913 196718058 203820910 348324556 562936907 256354687 570850036 713259059 999815299 721262350 844062373 118039988 599692247 363935986 587442123 655184835 762630131 299466528 975159662 244813128 780997591 153939247 323216900 755923147 799125275 569282245 799844409 22457949 793344513 502462498 821468962 39196873 256747457 597678078 868232337 626035977 942059009 61007760 898185930 175362558 794210209 393601076 402222609 443038892 567095408 155697902 225269732 496095730 681354475 215834345 764682929 361551212 383545433 412067965 659692168 165927619 701119470 566240863 577785124 255716107 480172389 120934460 859566087 632723392 673466752 755513376 969594188 554431152 949367567 39982914 780268178 109183597 621882618 455026590 966549147 280619628 598362654 788572550 836839024 246132683 612081139 105250765 615884662 144881613 317138199 428311698 517288530 519085517 998275013 190943210 913866104 301925127 876702736 464210437 739463621 252709902 428597211 601846812 714056131 515673054 988786373 99921701 780934317 48133967 308963632 211376787 958217451 167910545 891109043 706280795 954918848 282727632 396835835 44199362 251475898 628085656 697705555 543140937 584788853 241391706 585637025 313317472 388813354 921680751 943401555 78985507 882843558 271769979 312698745 167264825 764176286 119243541 658755093 392384314 899109386 613206191 975798950 914496091 983401898 483546255 643167277 416851508 822873340 266531555 631496592 156841582 744352707 402156390 861875942 105348566 111162030 507726247 578476980 114190286 738809631 310274341 746716862 394178118 402562537 32695504 424157700 408675008 541624966 78376924 526725349 387421904 752408650 485943653 791245557 33235327 736552512 468556226 563247775 177975626 619837914 269502954 353639739 322425817 695754619 188695406 784864776 28228294 957415263 288121819 871833414 76951419 227389183 46662199 292396721 607649550 676927456 53854434 957212435 54837240 333723682 361324830 502133691 616520476 675581736 188016776 255290230 262680968 943210259 289729113 510021962 149814740 739160596 243352793 908101753 927081616 964790341 593648390 854778322 100036366 955320965 65357800 92462807 44747439 670711920 270927271 611310235 780962596 884123344 200984956 588526925 427368987 975932970 20011688 482524217 296018042 944636216 6633426 275623135 333803387 867307276 193057500 960294678 40129195 829009346 524642674 683443704 728986966 805226831 62540796 98876391 385681163 795488946 840616112 930616819 241762332 441332915 41753077 377144171 559029888 910902194 786418490 890416775 305494941 877345303 192858336 880831339 574151977 866849578 551599529 620305721 90356578 754103316 650166833 989139084 114090343 872417338 313712591 525565454 308605300 618069310 345241554 850770485 844383766 854416764 276897646 603824592 10748623 18190506 208922123 494806441 436398047 515818169 436066247 895751044 477230746 679900096 135932750 316830519 174821363 722886438 99747805 395603238 50649811 204900996 809202228 834190657 419922959 489051750 819484005 909513141 609223770 939612818 408112957 813330295 324120204 645371257 758002151 918898457 53632195 805105227 432109022 597181647 565001538 612614356 105596439 130853825 68886718 670038376 8134343 442522170 340327251 675855776 788645762 823851520 35293739 472531439 103126678 524845300 367317870 850585195 565248548 741388143 114288728 308825325 516737334 763359268 895699362 961146464 639911071 667604409 94953069 301409549 61666602 437846160 176823736 756152292 43937626 927330942 68145744 786885815 208882199 418317590 119312631 398493657 311076401 599087775 91925010 643070876 541502001 662472763 536341624 947663429 679469938 728060484 290532668 329760879 582929521 937643256 306316577 685783897 160246102 307620962 387104384 492668467 183831112 682504708 370766950 554767795 222992312 346799107 75731866 521706837 171643309 424321229 2358465 288465632 46733118 954872351 283939300 864774689 473356257 904531881 921377966 958503266 233423544 344167228 18979218 655929982 394307594 691246662 221005159 501480696 23629718 444057592 105938650 285889482 146845071 720905797 275269102 810052753 509680560 948170817 149815359 759110541 53602836 483542084 383518661 470956688 184482662 696582707 451593986 537092619 22934890 670215917 154741645 728324407 445118816 679023454 526401582 528621109 284869848 651403432 330960532 622754829 396420260 840538024 121893267 164843948 41981163 839744725 88357264 383243821 324537437 476776076 590305566 882416754 658134995 943137380 755787468 906412818 13700821 260719391 165396273 998060935 108315707 939744772 35459900 520255116 206771916 957942710 327405349 377215853 163409319 807830723 492413574 525692327 363705452 886181364 643310928 896227109 315296486 445013659 640134401 780670401 542264182 756358047 552546960 741330329 701053716 780138099 147373198 907048094 73954925 486642801 97910518 111031805 316605953 733677747 142632420 828913703 129634120 141623401 481372941 523239299 129862579 175886025 648940905 898676365 299161166 542227950 47679086 616221637 186330119 526352000 52215721 355176662 233903089 959202034 347285040 545208664 540235837 744428922 159442946 425763114 615918435 987923812 246729370 329050392 139815231 155953640 843269719 883947559 677171996 771062174 803127999 886212494 191648144 309121943 356681378 529500745 6091001 31118164 571067070 623354287 797870444 955201749 69120113 229736819 284982842 362981002 123558297 611900420 460542066 577940423 264971201 386176272 24615424 62532638 92297145 259224361 470210245 726936129 21537875 162428349 368246332 593848275 61680718 453185384 61589057 850975130 153645593 549549539 295355774 408231816 111336890 994133333 37591002 558350407 368865441 960972096 613196470 940196466 213515587 821888276 261763482 922522337 107447399 320311970 144425223 931072589 54804184 449859996 534500755 560520239 154622069 394172223 424571310 915763312 677373383 683670263 100659801 907082159 588409494 730181506 641581297 934774246 318178103 639530709 230164893 447322617 171678247 548048702 592489422 879172273 935410880 957412073 198537297 953365406 128200046 856217432 17789574 787012179 363880141 419376010 192537187 424153192 613942788 857898578 71811805 960611964 124694563 760128817 106726235 677497282 90313954 664530766 379788950 937208214 625034884 670800591 129180838 494030185 163758030 503061396 801025104 870541034 307958111 983881760 408889786 848398409 399738889 638503148 774723099 890119427 809594059 821534129 309942858 521844551 266893748 352751924 182169730 230749101 76809925 752397986 156241962 585028706 678621637 685130607 615061377 727713273 2245034 772446505 215507325 920690561 226731881 373231454 240347505 256306261 830504717 948511934 435644375 548209744 13884389 91132069 569549030 847737259 22149289 991530027 269250251 399374008 260353528 679671395 65621065 877421766 265363956 525423860 92982349 902825847 122834446 308099078 227657401 733687414 76182765 585993616 773044906 980407079 613792926 786788838 536824525 975162313 21162286 22431568 180126173 666507760 192045856 521109329 816937622 849348876 346795626 590160611 42922192 159800131 180547111 894793079 412102930 963349848 117983225 467005390 346685160 785606476 49828462 508802386 275917638 574355060 97581764 874649982 67142980 971737269 8881713 561593175 283536996 487609781 381503834 945795115 206642612 365325488 128300902 854906935 47918663 305128572 70394498 774644566 89794879 840581489 369587399 915544281 338429922 593095374 280442652 570734297 706759343 728148126 713932644 907016132 476877916 529530672 806199124 900565179 545059366 705203391 146905424 601360244 240099615 773889439 140832551 300255661 109663044 362361368 737312639 898762622 35755265 303520610 13747119 670291638 392762625 765059528 40780615 589799947 468349167 661256034 181815228 339406756 351084542 693637761 181946474 439382737 31637142 756516991 624732816 659918664 466500998 509300866 720037457 753310422 265057253 682098961 525265661 880347483 218163828 327799728 31904078 809502258 796005479 923508874 160435154 653067539 336836350 897645777 381710312 996887484 761203254 787065223 430303706 478411807 485777601 547819129 429831822 688421468 658047882 841331003 96593988 411425093 269275995 821873011 159953444 252262272 49932448 582715538 15140132 207275229 191008000 778160430 542339656 748850640 325565788 895801218 241406449 599093588 421319710 432939284 38348260 721597858 338785457 853026994 525363627 599544325 290738286 706491008 27863032 977445678 181188460 795873696 425688053 781672736 155450414 608242811 93737615 347839641 81286313 371979574 110608357 174501852 98439568 543376216 21818155 181371528 302493259 824682576 348292892 863672923 112417097 262662938 587234692 775661668 55886908 201359736 318687750 988504686 81323592 466975939 141937358 969036815 640170303 734944026 435477099 603107839 144524930 458409608 346651465 792743770 50709600 164856592 419431816 514238463 75259112 743494363 318854535 825089467 647968603 665433403 354827865 785207570 310792553 558389606 189749903 770795307 280477921 777667135 428912476 904221914 118597906 752792558 31935430 507827514 17711312 584113230 495145838 656200203 731933935 955009136 321419449 507700302 918744254 986347414 527703278 865340500 678034334 804272273 345277709 864516264 110941452 200469044 251928371 400963551 100966027 513057630 46632030 652423053 117173238 233638434 119584207 381608728 670180169 673379573 781667 72808732 448968462 856735419 55257282 389232497 313379821 602798893 544773427 623334416 443080395 658246192 341887634 549012562 175185803 520546321 57028580 705752600 430381003 735820094 171404849 219561514 462289670 495998489 431558278 956542694 257263437 519835069 20700812 136492009 641743349 863865921 177145714 339827416 73954664 957859684 295968699 560068811 665074592 730918920 230324176 633255542 289536069 915626895 673395849 678626258 328160392 448613105 672092883 771052084 412630625 800003584 393845403 510874266 228745572 611511935 753604771 998998154 28645696 356381991 658752185 793704985 677781400 956817598 629445006 650871235 137994582 810695999 511030479 829578645 230771146 728183474 477617646 823818515 102955026 108515135 637384470 730441346 400773246 649911482 211119141 927596448 277681682 532376997 591384027 948479414 235736108 806874488 15905547 281492243 817771801 819171717 873011693 928483838 82661543 202977128 333026271 516606628 1606823 956728558 76873076 476683846 344651706 418947915 358263124 363883792 99526788 519261020 30228422 53868228 922972914 944724821 142282568 846798816 28410642 368536683 405510288 424693966 388893157 499716075 598957641 990626535 832301196 888504726 281398276 526900143 94133995 628896742 70422670 863895108 30744586 861651506 241313047 576005476 186597459 562263136 364712907 744496532 388844149 759518589 300514699 631524248 9661685 591849251 605441170 841565068 369883824 829058417 214108458 381826405 483683009 844907289 96354803 713108829 232609509 691336825 369063026 721444263 206876075 361890913 178133866 929698242 623241004 832180174 476379983 900173127 464915634 777847875 414258632 582455578 80578450 300662885 424543756 885777733 439512788 469266246 125065287 451194194 854603911 987348877 129322239 640546833 488282703 508902114 261550553 432468887 42796943 454969656 250021616 960403484 260283393 895914798 571925728 632688547 161947228 977674211 605491139 859553335 651872079 669810669 164538634 454478546 437928490 440599092 177764082 760995349 276344204 810278959 358394158 905333593 747408543 913688359 818494472 932562636 574487055 793306422 90076101 192206013 113832945 431545562 569843495 808078167 556737278 854940334 119715179 879083097 123804254 542106652 637752194 908517143 121221396 666259429 540194780 632673122 277042351 662347499 787254755 973296205 729395609 844964565 543886281 979619856 566458625 935238823 110879015 154017954 453756069 767852257 467835382 595191164 192451442 298200679 117949117 465610144 704663119 803650210 598735373 747819477 732918439 830913397 384062763 977323830 333844199 573009587 716672492 971880974 268782727 490305936 486999689 837584951 420689974 784364397 29661108 534676682 14724019 455206516 143577820 266371332 933976397 981578262 644518601 782493802 374778747 914944743 431470429 962154302 205361358 813338530 325380326 769496806 62909125 727189712 674527196 935704423 169817824 364178865 854053518 959889517 776538924 852373275 60438043 347876492 550319504 733665591 1259141 389670627 500857022 631367415 85965896 852400321 545713115 995041395 276475762 775204161 4424034 720944500 779003564 911947897 29996422 358998545 204195084 618372965 102174358 427296960 177533149 790136915 237578482 650060889 296882310 388539055 611425747 782845640 859594131 975911489 464257888 495033325 639428709 992802081 597189163 779107992 431833498 533866394 760034580 972218530 335454115 952873791 237362885 657513184 983644058 993665620 241225174 706294273 69484200 682651163 612333216 614406445 229592629 788949472 217784777 467571058 59118202 502213918 333253482 373285399 262958319 860791110 53249593 322173547 532155649 948430534 375531967 684039169 776058031 906393506 97912716 337859454 286635193 322632697 36181609 49597654 802903273 841741820 89712154 422755462 264908752 871178209 536755309 866084605 52639694 354000919 366686952 865361639 309937045 901686652 23917390 41248284 455521613 786761328 501947121 706810186 46727552 746077597 253122119 653552340 238706953 973872455 335780376 545584546 107276136 446886315 318932750 875367685 40413005 165901485 176400858 698129800 537940299 878271199 341020784 687359535 224181036 361210211 598299613 633419420 261470410 639414729 668749285 992223970 658344273 976431882 20595048 608697371 716398029 966728873 710662207 774985479 540574890 566094454 291931440 630884873 467605407 626671955 329934550 586286524 548869935 912192493 420058782 749638382 431145300 542148555 287493615 744000492 698915815 735307803 488042448 609720535 719151838 962984495 160156108 578204217 61537016 400145157 633193524 893399992 417420158 541035333 22660168 34629223 201778722 920473233 235558713 549889466 155592127 677454211 683669398 778510230 767828662 933863303 431614626 652163566 125789364 671947468 900913587 983513563 11808141 931120803 294702443 458529376 478928596 779250331 708892348 945506011 227017899 629236205 88006089 109871901 485106715 664971993 63040437 383064594 360385027 455373556 56123552 526599100 307700530 889094079 9205660 822194870 318098315 831509440 783996554 894416723 346152499 766063626 699441028 768784547 732080681 956141279 658872062 850950741 227541472 730091720 446757330 785450009 110521409 940351957 297500767 775389570 301500933 580033012 903894161 951524460 191649899 497824627 72790040 612714184 310807841 813924816 492145566 899089108 190887414 862026818 212646031 821650515 90211758 280272024 317147309 933651307 48962530 518961815 15822139 966447477 332937519 406731387 773684878 945185509 402463250 583882330 619062988 789965696 425652120 705228074 186932579 314675040 154480589 304294793 670088919 843621658 3073715 628369277 229877685 645203016 151943742 432120500 596273816 837029495 276299436 601224671 453514848 900549998 76660095 636866292 396139444 630789021 464544661 956404685 458158914 907285851 312101667 435748963 225200528 833521162 137205361 331628494 381146357 534067858 251344482 351917294 41290368 199752832 610623760 835804303 810867301 882849534 117864126 148038315 41618575 771095880 546407734 828665029 146788390 184413079 32695647 798464906 842575534 912323066 407409407 508021189 784706718 877866301 11643263 405376473 431125428 466715011 481892865 907056991 355596424 403427123 125865544 411888499 46733722 793009120 762672992 908988622 18985236 94513152 732593543 914037257 645763660 717792346 586501768 848760575 562069605 618169324 263931231 617271400 11054383 945751797 466659640 786564996 325655431 765778452 205580204 692307491 8754976 709961077 789620498 934457346 89275819 415298595 520548936 971335746 129516580 753363631 307949260 919616513 175541547 945512020 132140604 631765271 337736461 575485411 173987153 929901263 784892023 873416582 87178074 502083494 195193403 423207674 185089693 274011041 214398757 807668008 537374514 571655593 288692070 876997054 190995376 806289564 152095844 316656587 6354817 927504936 72636978 671482438 434125809 737839739 367770372 987827729 790216102 830276351 7764752 597617426 248133485 606009159 190552049 481710399 121864571 609361672 248379397 966011717 198454112 893941974 854179131 926281513 604794387 803659354 89820020 442884320 232580608 896255480 144467508 804562203 475807407 541879900 827151603 945125607 330686357 540645989 647303984 827200279 806131578 863202811 791389666 938504649 935558803 957032866 155025484 375607310 308357676 471960083 113254775 115961950 216009631 899058167 113422992 576305085 216656650 897608556 840247852 920515434 296408637 520248523 425401190 543353399 1076339 198006827 365816602 599501134 475012419 582378278 48238062 850789781 345247451 942846679 401281016 995458311 290312028 371042357 923084868 993851301 491070571 961449914 16648397 82434935 220324297 740451718 379095570 874732134 317051445 732368559 609335948 664587212 797891476 912687320 377521186 968089450 185672414 512380789 49322855 293315117 245516460 891143163 249853364 944587142 58247483 861526546 101341060 853751304 470495215 702887882 135980797 717322068 150817370 547771339 368893210 489339630 301028884 330105403 526862260 785984419 58346813 809525356 347481549 747423293 109057264 721448483 138254918 418009922 728086972 776658014 140868214 453021270 162385144 690037421 779522538 784082930 448535247 779156326 517401709 812978772 891160069 905873815 362967711 507182432 569491125 854196602 148428237 963205315 3700895 678057192 665707992 772152192 1036522 83519432 44868454 242725559 541362708 691737563 373217792 849473028 142764501 810230798 84882706 514668144 74238211 566524240 97068536 581449185 402539297 693738300 599819345 947789246 157321206 506876982 352523667 899250641 418378098 877746881 148851680 635347310 836226229 920612147 88928468 325728792 333942898 634401664 163186897 727466289 707004512 768260495 173755588 531777706 174210 999026460 375447099 990736617 120006854 919375579 247591515 800904518 674312072 956260905 846392195 951286627 310370948 923335635 305357889 793769648 90044647 321518394 324374315 977213574 874599112 978425239 209545911 596726733 604450829 787027788 173290884 405011875 205555898 582238024 452525122 865824758 90545709 618660110 314610240 940955363 253387710 767510209 570903144 590310715 419406655 762194662 402079044 932856177 511405559 742182679 362561296 431852547 590122805 707041460 93632923 323828621 208400459 503716244 598693981 856402992 182867391 285423893 331313224 455101622 82166106 690984383 834483923 841475581 125251616 190764169 159355367 210709768 300627499 585547698 152225040 348495168 638992421 662832000 231642725 773666441 11500330 443394072 300091498 496191443 129665672 560518899 368738103 647143406 194737394 208124517 696268361 787422001 108270658 944162835 119386000 887236453 86672735 908714694 94336612 816539971 144527738 634075232 272539417 300339423 16564843 832404544 524393819 866842813 436354179 552975265 147856933 327944922 381852590 613230643 889423029 996457512 827015006 976716136 405941728 420574518 318889848 959329343 582034441 707222449 163521169 438094651 391852227 540033978 588105205 923553822 161920558 898459391 227608183 386221637 473893553 973315325 92976680 241410480 532131098 595609682 121573377 279712655 523948698 807982016 42304001 452416986 356745306 702945035 82993628 957967327 843067981 891034656 420518144 437310702 23490168 320599877 592020353 867419561 184183996 514624585 455553910 906001504 59864359 712157355 169850933 459581708 752403258 806869574 55450442 103279883 90005243 694744511 49890706 175280712 452453057 498534316 481964777 838524218 549910977 872344194 287518898 563528088 112121981 605020186 433641936 660538653 818820254 909933397 5930291 568481578 713318881 817333791 115501936 355050733 483158896 564371606 321701008 544196807 577392262 857211482 52055570 484588801 60457491 737016416 239102963 598300415 372650819 590503270 51884416 622718502 19614546 80360087 380768895 689808868 691203462 996016001 519433165 993990615 123410248 360020355 447916417 905988053 106134897 421644649 616874124 927135244 535605986 869533526 622186654 924389456 12308056 345455331 379071588 462230684 282855303 615375744 702249422 915545338 259114808 477793607 701874265 742053627 867261776 869447540 120711663 946263559 662898099 770935673 162811454 739620037 454254639 591398535 44218314 367942716 419351266 954372132 572530694 782891889 815982709 856984677 330788944 383808424 511072934 721456479 548390371 629332778 429024122 460178796 659056734 835507438 660726687 819999677 561900619 826143187 195538576 815083191 21958569 520833354 393195227 924405146 24529358 253917228 156981674 747911802 596704592 853468938 203017686 947558428 133648839 331851298 233577397 941392037 604426606 897043702 576725077 584867926 231319711 978132362 691849024 993977664 323829334 588224536 532171828 625003135 326691523 777578545 82130 615303439 835813461 919916788 37240980 139513280 361965770 613163695 38832777 489721596 162850991 373993878 17620489 316444422 27545001 61060919 721536543 920910091 876544463 950524499 131756109 538027089 218570415 267713176 263365600 366231139 313591487 591147358 558401774 910408965 654758538 660855868 494566230 617831851 614276764 797524558 298944395 524218540 740523838 853525297 316798492 324315437 451709488 705395077 443155338 598630980 28958562 897414631 106855647 643936473 88619388 281431974 26349951 641658831 301232574 647990165 291671615 663382628 457864991 590909740 12102581 131847894 409869928 783042589 173425993 919780816 351967392 388157733 184522922 578078438 27344562 926749980 169847450 696510790 380577307 836546689 363657742 499240846 174082070 776878081 469762968 482580188 102680591 776755012 29205347 519951560 287855455 543704545 443549651 518556218 408450982 620166976 238348913 671424380 956213028 970699770 23763684 55267764 272397617 438547608 244271862 398201559 496837175 913074766 479465549 492727148 202752049 422033591 382891771 385596145 361096844 516614573 288185248 896044593 80391222 766247536 101999891 732638609 231835069 569102911 139518773 438411197 642605417 644473974 36276862 145189641 261375486 897132423 476796148 479030009 65409950 161833290 410894180 510733051 275860792 980752971 52724218 949619531 386112589 644611645 834717300 895777721 769538957 801846546 662405469 759980254 465293383 646222020 762131786 987337953 103725056 889940600 313281938 523192880 421000003 691957732 18508132 472632167 185966670 814235736 709039889 929661048 509579314 863185118 75069949 80097977 470949018 734276383 653882697 949972396 202707748 947954766 706458031 953586719 494817368 728703969 150006584 809825517 422912530 463635552 137111635 488356315 220363096 285082189 2315762 660196603 105619572 680811063 60037558 250151281 103455840 588930836 367080979 659782089 284559104 844119346 46160251 258146503 684468860 737235356 168089933 180402666 64310283 162989445 8669050 46560967 273510479 707276711 336468580 336622489 594615065 744797618 530079496 659336983 308494412 655250468 73008006 915218781 543005624 676377767 61897488 215115516 409914487 692692583 376881492 377550338 607633809 844823212 602217023 602380339 275719721 303085924 232804961 778578972 66330040 839552284 823957517 947965159 39912744 415242656 467429197 476462824 279908515 390089571 399573742 614502013 664987432 871672996 142073656 950177499 272204161 993044142 791739947 905588414 214202164 371734175 8245478 161167233 937858187 938685080 427821929 727629134 74621423 196226844 166079372 724198313 681457962 827442180 60224864 114353144 686110875 754910466 108932526 745676172 41463800 893804058 168516463 806528022 472662534 645975201 338428282 508314484 356694370 567129772 345191044 794099372 485831055 856552373 456294071 463807687 9276814 157870404 685482204 806619046 415077355 926858133 512902138 864846805 564514268 966831793 333704443 548529634 900202505 969739613 608386449 788198383 2771583 333609058 564070099 595526921 133610979 749879824 92396468 499417137 462178255 782092827 22600662 944471673 27328065 608448992 218393517 373932895 460135356 695464320 378659696 557263313 778051834 975689956 683138118 738686071 303147226 376601608 918279271 940201101 307603554 503787697 264097533 624321143 387174694 952643899 111822227 438069325 330571825 462013549 167200792 684953934 131837218 163930258 578156923 693645373 182756370 974792520 190161825 338095585 276142565 670069866 249968465 425638165 817359268 830142832 83360742 789164168 454082509 915721809 374151649 684771114 404148572 819431991 308199930 338812301 89073397 578509199 47405164 978019477 98020180 265292358 100476978 936542640 362473662 638791838 53452698 787088191 113517589 828739017 266416297 772278437 111901919 119340829 146205136 918219151 693522332 956643957 44553108 66528701 958039132 960443859 180955077 298646221 519121159 541956818 561818256 974845336 236877027 731178581 132366017 251834349 562384660 581040834 150897544 549774401 47218488 581727642 175582310 507804862 52031535 477216368 530121235 677457615 8710608 635029092 307200552 708959092 617099569 657806485 136508677 201725139 679540951 831069231 104114722 214186201 10950903 696360410 52320514 474520775 314568810 733603331 309214551 972765441 366028041 809713976 202339435 343510304 444558552 937458478 49308472 536016078 344942091 645836929 419557401 718054034 6051392 919877285 37243336 444145351 139476685 773484630 398125633 715655216 114444196 448345326 224993492 698362592 791500337 941127484 52263473 921826471 840854184 920992109 120802363 721626932 110411656 162492483 340979204 556895636 323666405 495359747 523674036 901659967 417899558 607266414 14126737 289744012 19035204 495191484 6175575 242302544 237895280 944716968 334160561 486591708 179439170 327416963 736048615 762650184 277430492 609856450 670815800 997949327 631390516 901018347 361876313 689636363 388789145 606599629 367413029 605119291 176208552 659413184 505791318 791722497 267938401 439661384 253124711 627400254 671828511 716924757 143883197 955722391 80009554 369688387 358534589 412699615 688103356 876835794 660993211 861350174 540006449 859244321 475901314 634455426 201828725 410976518 163479873 611021924 994416591 996166706 540449228 560252549 100063592 600742413 64232200 289526173 254003329 694278712 594884391 878771340 812531840 852034738 320650788 811498465 476132972 747135517 402267714 994730700 462587286 587641159 395100271 400458167 766003540 866653479 762964622 902171250 333224685 915874348 635123911 960337116 89981269 689758518 475457217 558878494 115007086 860264595 380139483 469249137 543011062 580931006 576612182 644077923 730685116 851174510 155411839 313994413 599098133 715748561 152409928 396147979 243227719 678486618 281575360 438112451 365886961 929237270 450823522 661920969 135597549 291564539 283257788 473123601 499366350 661693992 12383830 441004833 364706818 440292857 219457025 450592186 709094052 974707177 573508435 764017362 413126022 958222279 99001607 807069488 627080806 939364149 507650883 676246167 563450447 761199740 297940327 661995258 8007376 250194198 770298094 910402567 395107143 610972562 53953738 487707595 610936847 721541409 478740980 713489303 189914599 569831531 848548191 909779716 810369 357842863 177367971 304965829 12505176 79710001 362543576 971235775 34511237 684955409 757980706 833738227 114455486 547191694 678059819 734250501 653312186 915477840 391879814 720456008 687122810 839447138 776508796 998685933 145047251 483052119 643422791 673623618 153139718 154201585 303833195 862836041 912233959 926652842 612278818 768691665 476813433 518011222 233550855 961072564 429434926 970590620 292291409 784333857 363035428 536141038 575069897 823673239 435402871 441104875 29367013 838221888 111094075 789780390 467405143 569426019 280446617 894868540 504565710 915264787 865053693 944813277 155765600 732886974 434500929 966820187 284817252 963960784 62959325 560885554 412639639 477166718 632298451 720517716 737026263 956111756 644837416 841522406 143799859 469069613 209088271 300110542 721953854 976704302 63953574 628190002 261783060 408505317 541364494 567251473 953313686 972494703 675783031 928350580 55929989 206151052 689246090 939931577 536453732 845930039 100394607 689301962 345217520 976172579 930502475 960320336 99925050 144991516 213099955 381989500 37421703 131819290 17142501 134112904 8517034 754114407 154052265 725021192 53643180 123954408 271455770 511012062 240922373 736340574 108605446 516477459 156222389 312284232 448424704 932460919 378246081 751510745 639348403 862913418 112842056 401249759 576270041 898006845 442368503 521821892 351071704 474292111 72944155 327520889 244067220 406539884 778873067 854055322 16943204 535821048 332481990 798289205 346298913 632685874 86407045 702355176 295552899 733128915 241695170 515076751 822651525 929139873 89831627 634718933 129940922 432440913 183202458 334860837 97714369 382343369 903629426 983768723 433313221 866911455 742241072 774627959 234891075 418254148 381971562 766189518 465370842 664989934 115349257 127420312 589430577 983780843 281765910 840757884 443538795 473232933 171450083 538471325 475538273 993374944 83969091 244347866 181118881 282018289 47503676 422089489 665821409 700634373 665952525 919220116 162993865 998252303 60753703 399990051 543058388 577895966 255609867 911897744 398085528 656898127 379857326 909240132 6016323 705226755 571242834 894851822 77100915 222780485 374305580 644024010 727211737 777190367 588837703 652622649 465380924 867475079 337956525 727676562 315969770 775859504 451431322 666780261 358974129 676886080 673349192 812465576 230123081 644530408 1903043 129792601 32003193 330543918 783396275 973587886 514747088 938983407 622069881 829626225 89284420 574470523 424068184 873257933 257005882 458482753 21135194 931889633 60637109 357488089 302346034 726980052 413735018 983140011 5584292 100235245 24082444 709494740 1404300 480967801 24489965 250515271 67263595 742888128 604217542 693345331 555577744 743169997 413322945 874829239 509189056 676764224 512135813 602993678 539783945 872200053 360331441 822320328 100754967 715947172 219057267 884154736 470924698 759167352 420602860 949957083 479456564 865275025 72866665 213696812 284854872 313978787 95392184 657970995 74091250 784941384 207305222 782187462 890439643 957454457 635997284 951480573 33135561 672100134 420188895 779889734 279007560 654650662 113708110 827483478 215944691 217847169 520253866 940708360 600501739 737978599 437124780 881324151 489640394 493153090 251674895 414480369 611257774 737844117 57235203 534417985 131024889 851470270 416168642 537107792 194695961 841163425 566158781 916717741 127022476 146711454 315860077 887581688 82363545 547976912 15442066 573574745 25655163 179918423 160428989 745705262 292695317 601606307 482577412 628306449 43733687 296499487 187865546 704028487 68441730 697260233 646992370 994406210 68879672 252545243 159523512 251055362 597377835 767870929 321051896 615512460 236370138 702149702 51584890 599258312 112621459 631415112 196190689 912543324 467436431 680346297 366171354 802389668 145588662 703352701 138784012 282761349 226605760 977620947 704450137 969088607 350763527 701493630 607554651 749378378 936097782 986082760 439007693 469884647 511194368 977221259 870025622 888486150 11403464 762880120 289494797 666912674 821278491 990061852 324231285 852346390 146039732 169342353 444491445 713013925 20203435 390629127 698389226 813005209 99463782 397360973 276785804 742443864 436269604 695243067 307654070 657343958 433165782 501683026 266334316 491167876 357756879 679695112 356213759 415644069 449022925 648711214 242296407 470608192 280586749 649583855 2954149 473969952 100079301 109222003 59183209 195919880 320359975 810169216 87373000 820190485 586682849 611267013 520920158 735971880 522483906 560714632 818413148 830574970 5184248 365398474 230232631 567576614 219052587 687420453 455541121 727615756 511571010 927017343 196028909 205388034 375470034 633889430 431816371 874946344 146798336 957182354 520861036 754968389 303355911 441254777 336832706 829759438 478893386 488735634 127627127 309053208 515495881 615785452 544951716 853466575 486429707 889131758 294751812 704388264 29711893 275990864 551066354 903124308 695849411 753548096 6382773 384069103 80712090 536434309 193101928 549136469 453035618 502606178 7118101 62996215 371490345 939779461 782568738 793623656 625016234 775367194 480324286 544466735 140941089 824860657 164647134 354020471 888893246 946202371 31088256 818869261 26367015 869038945 81334783 574343615 609728557 630317058 114437913 904727950 354897794 609209340 712575883 874286800 67691419 733608865 364901969 805613086 66559201 907320511 458907598 636279790 717108934 917839882 561590857 732348488 143433502 288702642 63170461 470615758 308001774 780533016 172145766 359319242 60888291 877749060 153575856 987969590 250259057 338380612 483780053 870257428 351259168 586717142 133068517 626352319 272991142 705137093 476263179 783105219 106874308 378198789 279012541 864579418 554971901 856346480 905811547 997717008 642419451 807639651 376361928 406817245 452415752 761952947 145942467 948796674 512314577 782184418 610340494 979097888 53842294 509344401 615869638 923581073 304573145 435144222 635680573 755230796 277222123 702745046 42341268 378680961 722679742 786716375 247316108 280269052 167929062 307564073 42277183 158148140 206355216 461132318 530299890 783660544 568864914 917839931 530875645 626064447 715117690 949740066 37018597 666429985 451549937 992146594 15555829 594610926 163165154 392823823 586132828 826102175 701089756 773404113 695707434 980500493 38449984 974571830 640683182 855939156 443034544 466332019 320701245 853934659 63348453 458808265 215716726 383274189 445439514 726886550 183090942 188163975 463276132 638119150 224268717 981886000 272653151 459616620 238361044 333652138 217116843 508219817 35866846 615181322 226812384 479131330 670855085 690276213 491971765 723370792 1751693 399038183 657158395 677577758 229883037 962563583 661057027 779850573 217500284 676521229 574470326 978950427 13883309 552978658 3857196 944896793 20765828 522226081 705241363 839464715 206281559 631700416 22407569 341400575 930860558 944037427 33838628 675610600 489154739 799256853 76574913 469114231 69840238 341520992 268918257 327972722 89187591 276364198 24729745 850881008 9292167 325175082 118364201 810890872 145255859 529552281 48355269 841174815 914409704 948691172 518155988 877192999 330982649 961563301 268186471 923042221 368276017 842650565 471160829 814263392 631103202 852441653 54816533 279478244 252428864 497562815 444151795 692562557 736089860 908277409 19031423 263648309 64333226 890802436 467383751 502795208 171809523 350248886 133107617 214585600 173611179 953046809 690459394 963218384 379999175 937963066 156194790 661000811 65112378 950179261 124191784 275387870 254835940 578577948 617052905 860938404 37353391 978140233 481706284 985591171 941608917 998904733 440596059 579028989 229686348 362155043 670857727 965819150 106441313 901528633 154080168 832063298 562430993 947260138 760805390 970647816 320316531 323314624 347440675 759308436 358070850 683396594 212983407 721921798 3830291 774964577 360269195 560136668 792062932 979001301 427838958 478065316 788310923 923076218 686328296 778186229 691970598 891617470 210090162 581824216 552574130 894030425 163820226 366017135 834789954 856032800 90604465 381183362 460250437 714759391 35486568 184325710 731285792 914871676 182319836 777804863 8447329 558009599 634974422 791557408 92035879 985059291 103212387 433706788 112713738 200137540 661602918 725404493 61732258 680889178 674793243 866887258 1820583 931590728 213225430 589841166 263936643 860395110 104809300 152428616 692725053 833283716 94105677 713869937 535089044 963898253 493907442 733401973 252759375 624117352 436662763 596391615 3393768 695772171 243546225 450001550 335607707 814829985 6913371 762628077 115302647 348420274 16606350 182354610 349686880 799040213 156795854 372672935 542384038 595520986 483549791 670224993 574086276 925509241 747994122 779835189 164334256 584617473 699589700 928707208 363851844 441277220 448774271 622336115 455493157 756783688 181065108 987007703 104547132 151385734 265079231 329100881 420902643 991758053 443457503 980471674 168301604 506730665 459478210 821102480 390854637 401996073 61813460 599045178 388020316 855842155 498770238 921535851 288731971 532182779 722498896 809097319 137704761 952810537 87413570 629650685 182763940 483981496 154842011 722661789 211964346 329553682 224903886 880797353 234080149 257181928 15370535 523063562 683648572 937309290 786299623 885978629 47023750 142236184 402412203 946312780 356715427 442944107 74459224 467976211 639482907 689567898 95873185 501478903 406536177 667425702 686218019 996299487 313817578 713427403 279059398 704846355 519226053 811476871 314661980 867929237 739038510 990991191 366205083 937471389 373298671 649333443 1658014 908169236 267601305 384546154 210910957 232169471 461105512 648653403 622911163 846613820 11958199 256438611 18484798 882468770 150753043 431601378 183782354 573332439 222763654 507162336 154438748 596668512 357216815 361073156 280787305 842817154 611613145 713089800 592295141 707799801 319849049 849560710 2420335 499052711 752641238 880597604 552887993 811513506 152553427 963026691 52810874 182684736 257345657 682451888 692908081 703976910 192628552 545772325 84252324 122794498 715544591 889851983 622131169 642930290 238109983 354281807 3057421 771306696 410041028 729670076 294498446 976982789 393077576 604310998 67279524 697367778 285740858 922291447 183427794 952593891 684514940 956767932 400272255 963283625 235692029 499904264 255779457 691673316 309057335 725891000 750195675 927411851 153910160 384860670 126239242 315825922 139698994 674954175 767708854 879331691 139510611 347833602 436883975 758006720 482553726 707268577 18650239 342277876 363236276 560308514 7874789 184685189 161414362 595283453 225819134 801969584 216579327 834986381 122199884 554331446 421771144 681976803 296409692 521918976 394435121 512972726 88015130 913818175 245392779 748006430 672130666 802809300 396879312 978922876 858095352 972419569 275868272 621899042 266208206 540050559 30154139 952017025 41984294 56613571 751273982 872684966 360191431 436572406 20680577 550324783 681272686 749972057 623959268 796118254 114749339 861888091 288233240 528193342 208931815 771228609 142558811 460575787 96065450 252302833 50146312 249919056 4401309 795381453 119165506 885589861 218278445 879882584 670875831 765135419 269425168 412598932 618641448 942004583 137316152 677267853 846528278 946832457 422063088 644988338 499990001 811084319 508836149 834872177 192119151 754871903 230109182 511192684 10425160 68879922 614471616 904022505 476459966 665274537 402018585 653915298 463827944 536874918 19579621 572035491 930097359 956929913 203445001 645851392 98295329 104527462 158424672 393325270 728281195 729498655 158380671 587346948 820431705 996259521 285719380 675849350 489781472 524844125 622402267 920585012 811822729 836714987 20314170 349321118 623202051 852971367 539311479 927395538 509557882 814726332 372543377 952474425 81355692 152459106 240016250 790337296 41179882 975011731 507335252 670177579 502261709 638845013 53136029 581388862 514808260 947666970 603194498 643410050 691497610 698419467 46812072 381473119 736181709 744232854 566221005 956321996 380327882 623182726 788195377 912969558 37631335 243164970 397317280 779619607 411986206 551456533 603695050 845028555 350389798 817955644 200252157 423893524 102703356 203405848 404862404 572801880 456421337 695666034 620964429 717983045 562992421 835048096 671330450 910690095 80442392 373525024 93944019 899190150 573333083 895035824 28265542 870941086 744299773 892497039 888891490 919176800 351319251 866845141 166447159 970408547 10673537 675963811 508310595 653969690 200348107 263918729 221050751 431969842 95795731 526895680 69845543 757051086 521253444 557079160 623461683 905030524 169334710 335593262 200966738 779562809 493069738 888937441 883383887 934265729 181520700 366204639 637654277 961361492 27507885 138930352 110430636 756466528 468212840 965273420 282738115 875117582 66761507 956963755 7539511 763563480 139942722 251098017 278781678 491200430 60463391 634790476 297158426 788606245 778106173 795173400 306794262 901326216 543276953 766423844 410553922 611540857 285582638 490154748 935087066 947019539 234987734 539076204 286719051 547353612 121083347 623268143 16669766 933058456 327012483 525759730 749083349 996815054 446913098 792356005 129673621 713956964 15544936 989047898 662560846 915564181 660709525 956147430 130303931 347228998 263488577 827106898 31753800 694395852 98110352 667003932 403145692 980869907 56289648 847448536 65154050 337040108 610281683 875773483 202241746 370645026 556767001 592287262 401182848 925930846 107484272 907834355 745587627 766849744 399259932 972535957 58942005 744665300 65933769 293674879 229921277 409662505 107260418 276320764 106171900 685618000 331935042 486792014 204060992 979654541 577964453 691783864 377879476 517374860 377780703 727875001 931924379 981178088 323895861 945471696 768533840 970274015 276733695 414745651 53741592 79192954 470158 686383770 92061930 862928951 339669570 642096744 316917555 445869639 428793024 821016364 22245318 638239758 338670267 831687691 792564975 908049673 287453909 940727965 443816396 802244592 112992763 738301636 144124553 707969905 357199663 870368416 67387660 762495484 525749774 743319357 657933251 680350442 317888982 930186304 35297247 445290430 270295335 975171180 81201266 741854207 544486026 777524932 259106318 280774156 489699489 697909660 46115281 925958670 532622838 897720704 765254200 868507291 726286741 823385295 544588164 822574919 183814946 862429540 549929722 628359134 59160178 855145003 151580584 158847382 81848862 940840271 90212028 187413041 475850619 736124534 43014977 80926519 7813858 113954867 62722899 952138556 52976542 885340488 83005734 300508878 340472292 676472183 550767467 567332235 835973748 965372932 371568625 456600180 831507862 950424194 724922509 992708993 443956018 792002535 5596220 964621431 215594894 938184846 40134391 694324359 476493942 658452287 87337944 132256552 4661554 699779324 252722615 917225964 75131994 512384088 163115737 580240077 607880617 612794470 411943569 657746946 145343298 737137576 271393015 358496576 22342125 277390217 824307729 970844427 711087332 831916491 360799054 845740334 192064076 588415173 122205769 783219065 406397792 544094576 356381615 359616970 446023147 903079841 256321000 415853021 477813779 617929084 954618040 995344301 428067134 847002949 833100649 866028210 154977145 803161647 287089121 942949841 192759441 271330558 508962930 547846142 145065136 321084575 88443653 935594246 275331262 755985538 385369375 679944971 64632197 261972907 696433757 705907956 421701017 843541125 92704823 843825456 275288514 561145772 640654197 823345195 623180639 808235080 674675496 897387734 521300085 844987440 747620406 988455440 378368938 435047851 80263608 844234435 221115989 751098516 506426499 552187468 430329662 778821720 116912464 862169043 33100118 382922096 474138813 566293824 491517355 937667368 153748459 506266380 61681554 852156077 231887067 749009901 742039352 821299507 733134502 906224133 374746645 643927995 491126754 577903489 382739298 445161044 424999403 928613314 512002966 966523351 288994991 479330697 259518196 418391056 410776950 464280491 28309115 872570119 408238164 576845972 280827901 719777952 198873112 766643919 653449755 951480791 338514695 734933574 444486626 691577309 1275725 730476871 465686442 480383343 255507783 667014962 363177438 583139269 111491938 784598803 17107394 381825801 116616003 310092402 489807610 615870848 156696823 662152090 748790967 854136477 317401259 639477977 201912619 665000255 118484968 882806717 705998626 909258581 166337266 226345901 123377300 979794942 168545700 937028739 299034088 405402759 532752359 837934353 80124744 745388741 358360376 844060173 114035612 472163670 64570883 570396340 308055492 630448931 125885608 248809276 188899016 395275106 9869815 871037258 152803546 550547537 652247230 745652452 485539234 558066715 594985669 784830824 109794660 110695026 764488741 817236913 514938400 551504292 162332775 190666728 95161371 243529671 335417897 765801059 188449966 527493925 141244509 309227090 453894 639161399 116965340 191937965 114567797 216721284 591747542 696604601 324468019 518834845 495902650 594576276 61541451 837808490 353772081 435713336 100104868 138930134 234784831 608276432 2841871 712767479 11094737 731509022 140151683 960957584 461008927 608582810 233905216 817599263 279056981 449449142 55516699 634348112 151318450 667694656 282259323 404154160 34034048 591108189 123610205 538375404 251075396 899317717 191948216 667899031 608465902 843353556 275399760 869981469 49312174 983349140 231381783 243398416 451183576 644510065 497492133 789198059 715453527 831633382 728527769 988639723 306069945 445256067 215781687 947141161 420296923 446596275 670312471 949103134 322671478 358714408 874100230 925862528 267510703 711109060 584145871 955289517 189122776 940772303 168348417 567587488 336952520 736551194 445874471 859984878 112990466 713836745 141464565 570730835 119311952 435404088 529608706 969494578 259970530 843500752 653739449 785575251 219241495 891474101 263448702 838640133 398278407 932762935 249956530 995224004 733139361 747802922 598576442 832440303 440038851 968682951 528992072 882656955 504723511 800226340 274396657 512597455 283668441 698320653 11581045 116131256 325245918 888043308 335040666 514676930 188368825 475671844 449057833 648773177 338819286 817708359 447059161 697788080 296214071 781239033 194830418 264067512 294237774 534339909 696487720 828590114 91644081 865861416 214088125 908563913 116455508 703108812 12242104 675597155 201795111 227519459 354210297 980647732 530423962 950316697 106714402 847468493 346783079 919000517 654207407 933896864 435568198 728014251 160148033 359226099 463203636 587909294 234379857 939403233 241048854 463219491 114211839 509182412 343080834 987167619 202746406 303633139 750778585 768740295 694870665 865974153 201629354 645219837 678875898 856034368 256398824 668878475 514017385 801651826 95316624 896534657 517892679 871495037 306856107 372131854 113919375 241624037 802339878 964287903 773430250 865330165 117891453 959325617 71524125 157220738 172072287 304175903 319616352 684048972 848416046 947618844 395221994 904889262 127997876 341796472 282185396 831397518 207934337 413545912 722604512 954379058 343847257 358455457 134587756 395754052 177464239 542927668 444432589 981580653 109006884 267213350 379271356 661138244 474335233 641261282 312097420 467684136 310935661 359536966 62909942 202781753 658125013 859502778 481563927 811369860 261453451 397936512 161618616 359404414 55477803 543713228 82777780 714879695 49956992 998180056 456325570 809597251 339617473 890484766 504113282 715742965 241664053 789321385 195390599 831600893 312403481 637466541 77398577 826454218 260934743 839637439 1699492 605776109 63236839 121066745 124991247 746963454 694815414 739206396 85666500 358461505 580972849 764916203 175246752 649135741 260516327 386822325 251123403 669744614 568003937 711713725 204077259 675466830 747762455 988245981 626325979 790196608 361228357 536092162 384091066 949209259 387665746 836639172 59109112 666418635 549784464 630258459 523591424 735299036 382869437 891065046 299522033 327236784 208284928 881549335 700776607 791308850 72858568 99656555 173011418 646660044 182662368 529704753 521962481 761503009 276531877 406327638 427778921 516640014 390141893 862854419 8288113 62133871 256723867 621949576 189687510 378880992 12921762 100254399 127313970 902530502 519174952 683434740 619362959 857679210 153111410 432636135 746888792 791437624 550725185 815696975 291368461 618914501 401156131 541932547 564760474 832407477 322761237 689121102 297622639 630526808 11447656 906136703 50208711 344436119 31712965 152973287 47153899 737324909 725487419 870101559 306543421 395501335 608797311 910618431 360391961 980373220 541472073 718505993 304736115 686916820 239709865 662172538 157229519 313670999 133963677 985219634 358119280 870738515 521709798 894545845 566424528 902170730 292062453 640590065 270580346 371338322 146030072 802248234 276545382 447025972 615517174 787351127 447099924 910010312 46546762 312557471 542635960 730280421 230776805 447890061 50640024 392474705 131625939 676406150 8048160 739917169 274309845 386636966 96399131 961025859 813210893 973073415 657549767 837609722 204171891 225631953 700582332 895050849 565808963 906775730 408012504 691645331 122266890 850137178 108173180 761295111 256119804 557475089 275604470 394608082 746634054 806525666 653572341 874254448 149067105 485138499 241567969 345498660 94370643 213958213 382181953 975179980 34872229 454036634 482000208 648760573 164734598 561373673 703742123 737974932 669557060 826952273 774094592 885374909 64133581 128041304 426130488 780486144 611487580 644406333 11583994 231349621 334122876 459415402 605338120 691932066 563114418 918056643 602664250 849726776 533887253 902911876 310187830 926614668 463373956 550888710 56751051 122572289 605866849 679736954 146477002 733797978 402223818 436266408 64682707 69291948 508287416 659214410 114906095 303142140 483684787 566456908 7902969 560189577 549093859 660548408 198009559 793249491 93351688 528508466 717583988 873275985 385502570 913455491 129133987 454200010 105320880 856679094 898119727 921061888 590388499 806982370 134587838 372562684 369817130 885446610 603135271 970932601 278633702 284232579 33233432 265497715 905300894 956938767 12987287 387951962 814055094 865973888 775626398 804170933 468735544 660083501 523909456 922523552 612407039 996821509 193958703 743946192 33825854 809971205 709789102 850109624 891518138 914279540 509914561 839624497 144244053 346231885 663354395 991818743 35456150 656926773 296073981 797583372 247608687 672687782 559887515 566311952 442265163 890030942 769481904 793152999 200502619 214805768 307019614 867302533 228200962 977416523 84778199 676773519 129269098 138247463 325583546 444514470 43542999 635587615 119430858 692136434 235461819 582925851 150717412 911594975 74119256 476556608 669981010 988570883 114928721 882402900 244981972 292560078 739192280 844466442 112120913 935360786 96980005 333707650 634557675 811572644 7927126 302823140 102555984 717519939 21025224 849239287 696277712 804612928 388513259 808677073 839148338 926902487 530923131 753003659 47214576 324617909 626757682 673776397 319451327 334473120 96890533 775469609 666470648 747348429 585906010 844564472 399032032 815836875 644704029 835850115 231783577 644300616 53966376 703506961 379364443 982065436 248138503 561202999 239054783 940533667 410492384 871462930 45772048 782271927 353550669 437017175 2967923 78613554 105596300 408989862 257589997 681141290 42301876 997103180 446974944 963822884 194899908 549413285 492981240 934187363 91478003 249444555 376629080 423030132 362774258 862558409 545399287 559155976 643812623 787802480 26827345 913182199 484680704 837271558 330016218 815844620 186671765 814041992 76081554 244246052 439751442 515038158 16537322 637587331 459862652 908520751 114988288 763597390 260038470 458084945 416845668 517038850 99091898 583498167 137098064 736756464 177679599 882973249 689073074 764588652 175470377 960253384 403442510 798777444 67992677 693836036 250226825 433215950 354609094 870527006 185316724 548993619 300360024 335330912 837003305 970774567 467713032 545735991 193858441 243241227 480728197 790244295 400085524 700084391 98597311 990033512 126521859 914554664 255650200 460154223 735629827 798989503 78209001 570952473 315674494 942837011 590245766 915432197 414455807 523264780 122022542 202699226 355762753 832670854 101281450 870014082 298591880 511524906 257602527 779992140 485590239 523260135 171428744 342975598 104799117 708227771 18700648 267772139 761298888 894839989 90948060 378234839 192282073 531267844 42662714 264823019 152224299 449181607 659959789 707939311 36352682 294058566 215895656 996065969 126556450 241061510 107857427 573141911 143818042 737240647 769044053 810785675 431373635 715243153 6412377 818825904 569164895 781775522 243109183 614134823 154253465 262065806 44183556 986269084 339658678 995061415 40501030 890752675 703433173 831218836 104771747 708256041 94803788 274278572 188934538 713322972 329269054 989631514 87672735 369911812 252606222 395443104 178283836 306894483 206231748 229307626 459585279 483888371 426654658 844517649 742640216 746802291 771145911 935150947 340033560 361774376 663361233 859088994 54309804 393377714 4468791 408758027 50378429 774447118 372114871 666335834 334893938 786337614 119085323 389262269 21316069 281444258 85915556 754366598 712317055 935438567 778297521 982989715 42935170 251237280 905913952 976455503 510638989 824324713 259576301 626859607 641009336 943308876 431871823 747527168 208789623 807773149 202323323 271092181 654285975 992460977 251080753 700907771 94809011 670803686 779579848 981134113 798747304 917588254 552092557 882943573 170560215 737039167 249742806 436083887 80497642 378690847 11885733 247897824 38274881 999165205 265942678 777704448 37744758 399395044 235896006 616323035 145238206 414316892 12981177 182347209 229064975 392757926 433713623 972919650 646668581 939763000 282549283 829492870 580824854 823335865 70940068 916761638 106994220 348491555 284113323 756256695 93741016 172290111 461886042 928357867 238917575 494935955 64668828 988498275 79367344 129885699 205124106 737128206 224311371 712062935 684715335 911620479 694945757 840728739 838966256 903068215 84645457 717595436 317042649 808406815 190231517 298794807 752731696 994652062 10413462 264153323 953671518 983204974 13168778 51727411 741815 581567016 123404176 642568932 271918047 974338962 318876542 753441281 206944880 539131446 656220848 772530474 93089311 291258865 105189621 848011045 124574853 263059299 151767980 260936640 101286925 821712572 387183335 569220636 17477735 290446714 434540983 540721508 483300288 575076081 287034007 841873617 536344580 920323135 481986450 524571520 109556027 700000928 11797873 955245246 419012102 683263284 768674786 800438481 830879701 857257081 71226886 893062382 357973449 587307170 81061368 152752030 729673347 988772484 202936191 415905167 269762505 469422120 140716415 915704591 385681512 475246746 204574493 214950766 82487512 242525832 21349923 449461379 741997888 944829676 211161607 997637929 922545954 999803809 230115418 592813506 20273275 710777843 56326204 431601472 217692258 500520765 529964931 822393835 331623689 591776671 878087948 921856663 90232969 308003686 603024508 990255568 63505711 737831041 465651998 504340342 128733340 157586571 365191381 999949257 536036278 907434400 400046797 938567207 276998144 517291827 214894348 317641340 381493524 503566415 544047616 772582434 46700282 143532155 448873339 783207655 389268789 943662945 419437415 849371596 49433395 612261528 394727997 675080580 536295132 768659660 238305253 992359439 360291890 363882326 404840206 933608797 115932772 247675363 415438538 902427426 122471904 207492760 127100974 910102069 109700124 496229887 53397406 770156474 217184824 315913125 439402806 595018414 212418391 442996335 442447718 468744904 291842472 606310349 121948334 123017648 479753637 919768120 118921899 456948848 341326402 565944881 558657657 693345028 649734878 720049427 217975680 560439558 345327825 347709362 96520391 586663257 580545035 855231870 558243259 937833937 505286147 995356357 302880260 972346207 171326641 417082484 31072518 396896253 135024350 347123199 88944909 867726985 745930035 980163594 53805345 394318681 86803043 720976245 476213905 719957170 47635895 60663690 143477418 670470281 476578734 755791253 216003144 523103717 771272771 779834454 135343791 372789378 114415432 493847260 122540748 238137217 500517996 974064439 454544272 639629460 309045106 903349889 590223253 625516864 742021915 763925407 204965886 345525376 654491762 977680693 781834720 927027535 552455064 577667474 170898011 559190536 366593162 450216992 550372282 682149954 315283692 799640401 277356025 686105786 241935736 940948073 37397112 988802974 286129843 522793344 87529619 420172141 362881754 772061645 376503600 787589726 580089104 778192434 276793617 471019657 576309742 634648545 150453485 771978691 390634226 963474345 344290693 828552450 82798809 580741582 82839744 434054715 657952303 947030839 393453147 491608617 336767696 749492000 604904942 919969853 222368490 917876951 308299618 577847716 125635120 229194424 41547371 449735365 34444825 36985262 13707361 384242652 811057259 957842903 625111616 927422709 370532211 810798865 719707917 768148736 468970185 857341537 356913374 382162365 546390736 949925938 728257818 805360122 548646 962269980 220555750 367694358 340875162 428153766 469753151 804915817 58121180 713432268 82307395 832735719 262137761 730959765 248652513 577359350 291136695 965528120 371947105 925197262 4239096 854289629 248258044 957681513 193675939 984064383 155562575 697377790 232710370 633464095 846334 847954644 65583634 543231667 713301281 763918810 78170351 668444335 12711695 57856325 100541686 819938016 65783934 318329456 268730736 779029778 381584895 515287000 408887896 709637997 118028599 585099224 458188535 651625094 288932263 779041114 626804398 683299538 500885510 771014009 392412728 961750814 324590801 984776032 505012014 715456573 89636470 486597153 617859584 642230733 246601917 629899454 324489068 500895988 275941489 697291641 266206760 565288050 114326542 798567328 646410112 867771702 498396973 577976853 533232868 657065353 509948464 904275232 672655874 813166899 98627778 155231966 297335704 920270422 203574468 861201625 142243285 265838157 163378642 368540781 501946869 550825158 202670811 753198258 375819561 423297809 604991974 770541994 169931531 397076834 230546986 595334818 526002423 626232505 140315368 755441491 419166301 734707513 356821380 724366141 365068982 593536633 351532468 447125104 57258954 313326831 567932170 883428479 894541548 919575023 286706646 648819599 693242213 785799668 235234857 705167569 28187582 641769363 597484047 699708223 50159076 785700617 352227334 813606811 114017285 498658462 36143576 415841681 279175853 858957112 407300965 964405856 274507926 601405129 141279395 664580566 113103633 977005976 890883128 900462635 82715844 734334146 50625122 702623509 195268391 580690288 17223723 753255431 32573123 916991699 557318025 975043852 258059311 677341914 223489282 887302556 63548813 538947572 389644427 700161969 743190120 829358565 111751938 363370955 48055914 494827338 154178910 568742064 15070949 716353479 833225285 948575832 654178205 775544949 205958775 800564591 330784432 830438582 382591936 953997284 211937296 946031848 211839189 563051519 155909019 787486230 367129309 963363667 345401391 944641546 632945102 882466901 428595091 889083434 114340556 300187514 50818171 204186533 117482634 305215947 42781986 943909522 497049457 819097396 644139183 872354754 149147967 498334947 454012871 880406252 135334865 135754224 122544203 374133534 480603483 557575714 132401086 207581205 102640021 860613941 212966287 714458411 228856434 512717342 290618831 650717014 106657846 826891885 672320706 930844623 508730029 567245327 731568192 891343470 324829026 900045195 319766552 723939450 845903960 947044675 400634244 406553069 674435894 680435652 269567908 651916083 502240643 632970363 693366780 740143206 638834376 859167762 413393706 683697100 786968270 837778467 34501277 645120727 245540789 882849950 215039496 397045489 802986453 825533663 138986008 341706870 906398381 906815797 126362894 266882390 110880580 806581373 104848660 116269946 621222466 680762235 792535017 799047498 307146601 404038752 245259094 277063415 225853269 637298045 790957577 843996882 127450475 473756493 268143708 507607360 690138540 762470426 522915264 922628998 165281769 418072003 222321729 317192704 414360854 922213089 776220947 993978565 116973705 293718394 643840860 935859104 552904819 718457864 445632693 734084025 225466994 649861082 211920812 434197720 136315812 714983292 583944397 891683725 501290626 567959760 515808979 634428344 381935633 552184154 813292593 822312760 901077332 936212419 829544916 950311651 344526382 498125676 177431030 476540136 238043825 652316450 364965454 569437530 2651204 566392672 263392734 819217560 746343385 841267999 48115654 948490289 469381148 518218265 753317281 762657731 672229718 708526812 182100939 701364072 370628077 907538375 508624804 930383790 973984699 994017446 167675942 190734011 216629404 551015585 684752063 816052392 246519900 310646339 177419337 913246525 389526031 648850840 201191340 674994064 346812153 937837637 609530284 808648169 219734874 510759207 161155980 556662874 310744086 848516273 321242486 438312203 805725691 931824404 109992593 673978464 134162281 460910484 35747379 759657853 415919667 832318747 419698128 714963345 77058066 886075846 335003830 644749517 164751754 203566957 399106119 671787112 489172871 941708549 245461866 939596006 27107627 802944329 622552215 756606268 99332357 906109307 512150796 914229340 682219774 868745455 527407790 688596360 558321955 892499765 438095665 703705825 343343355 856333636 289092118 986495654 243883306 363579844 230639569 266505919 679194408 818011864 408921703 618000986 226938960 484449794 152634023 174615151 160922769 940434924 503985161 803489041 271893043 279418012 410555781 730715474 643161048 795657958 285387478 967113275 126590302 609198728 269385033 952738736 658054530 892747005 367254856 948603938 127289485 760145092 232463377 255769995 112827648 991560244 8227786 780937624 175695140 369500894 821718819 925471158 105062733 179941313 746901291 896371327 398002727 749082875 153250671 737213007 563011985 990849633 100437279 283088978 314144673 865643891 398330033 655739554 48894013 790878783 341800093 887591100 19647779 98707790 137087554 949371223 152551928 499141388 97921920 562112254 158397011 954764983 646832043 892455132 526898035 566622499 116480560 868989764 12849025 75168617 189014657 423312523 234564807 463954738 578062710 860603857 635988339 836435424 383287652 427758253 161585119 653397706 763404846 962230861 510922218 696617428 502569485 711445352 532031963 807281155 269761601 842299849 524005239 637335909 22950449 702492896 386680422 973915423 193360076 559435677 125509398 312616065 461210085 529824206 84899777 801500545 501026638 919904054 353521077 397186142 450552940 778215863 21118159 452657831 424694592 993280894 479109511 646071072 735400467 757973519 138428230 474778861 26074585 673462298 207296119 557078639 187750620 423300747 382340636 783907374 442321278 619668729 533574135 871576226 36975680 614258273 957451767 958434887 325718931 362428291 623212521 933756123 431038916 593870517 817370484 947912156 768833843 809234656 430209912 868372773 357212434 928425852 69052321 522957010 458567708 608469518 88267068 369189213 359863460 479801300 198256851 544714371 315847726 800164193 505700948 931076365 615417195 630581084 325173649 683822029 353858355 647197627 891274140 987223353 351352754 452981840 971254327 996663411 520339571 888337399 171672983 730384762 780706361 889399665 343620180 612289722 466597161 832497014 855634871 895324590 173565762 780968948 210348637 642095292 178885803 847988982 139242014 810830143 301935873 634866196 177814455 834603865 3142560 7563868 940471481 940531967 554275335 801934249 211404914 743423872 513283393 827212914 286779311 691972034 478504217 556195149 309151943 780219309 55891920 247378802 659502853 967411637 327280461 709752130 242931412 450510639 425724701 622473600 29637151 57358814 104117637 298992374 214141941 694767568 165673690 724992342 444512154 938991425 85314207 211380178 768071095 846043107 409513107 634181962 758614173 849606289 41475484 953997846 55517363 528439905 95558960 436164306 623613241 632672975 406314839 655868445 53046340 246814784 337554054 453956076 397457046 833825309 148385508 605972740 467918150 748093096 53784682 497649423 454329018 947655413 209038051 757584468 310878531 469343949 199115185 760946985 58121451 198576845 621092443 665356323 100561035 605983956 101036581 315608748 605852317 898971682 489107419 976399611 452147298 857173161 329291947 385130088 707267425 902294924 195046131 264866140 140101242 715988351 411595753 778819040 340856472 671369484 494922583 921483672 710261901 756087095 402233314 596178614 203026632 341892535 156913620 618094053 487421721 603258029 715090990 835303792 275862615 632864248 139818229 850326702 55535602 835795480 201416353 869024715 268242483 662757865 121967122 209407114 63939186 151823844 145151487 460411663 314837004 955559967 916831492 996325769 28279294 568835883 39534234 851696751 367224286 475075860 252473979 885250010 563274287 805527688 143828988 405444700 289612390 398811585 496918029 905171134 216168284 990182035 280359702 876121433 228468372 991484188 250752048 894273425 121537434 959535581 4187920 367478314 48984279 338188250 114309506 156077436 552946683 841442992 606673055 656097660 113298504 211352635 100316646 730842458 109322361 521791530 590013537 962177679 10531696 530584648 214675725 853248564 723501832 790005283 600875347 981851065 98904739 406106743 280625106 517305565 126154449 823362297 623873882 825218785 192413223 630778498 549575929 702922297 311072718 887073519 269064196 461420475 86310084 364762589 181220734 852638189 746077960 839284466 621128611 986670003 546798751 626810836 562187063 688050363 25676126 318445777 46694048 571443603 359890552 942460239 99627794 710637890 120738711 872164393 439781670 638683356 243350678 734239468 246528914 610957961 55270029 72559425 20908251 784711435 710216069 754371382 33554009 939525485 86925352 960114436 302664048 482621451 107007865 569859660 217078751 608560111 608329891 650507973 354182032 914833988 11392938 970191232 214178949 298815259 559815804 830870350 152735931 702880708 442099865 592108050 313677171 320736564 384407797 778080600 277985960 548715990 237445671 413598747 654892786 720053840 29907477 470356628 18000864 490949484 47552392 280585114 462171458 824876164 665609639 957189027 338187144 367154263 49721975 829881403 436495825 560925621 383358128 718826918 14644834 653786943 559498625 574746133 53031681 891086535 675887517 870710030 582176612 886585363 692645548 977553914 56965453 452452735 870255443 897010574 409838955 975950161 330150308 733522514 117499679 119519147 316718186 868720600 300744848 970851252 709156746 776759365 184434856 778836555 168530073 591900988 155549795 214511864 18351761 707943712 870027699 882254521 99006072 300399840 476713924 668228863 84434429 766763355 336362894 565650889 630536556 680414422 191164659 333508807 119060563 168623969 751534567 866293219 74205513 243117943 417649380 542688270 77511121 401318943 56091421 853613499 178283921 714112806 76231828 123662085 397783257 807587220 278145315 401049697 257984081 378351220 143520236 235032676 221114054 456873727 828983191 839140411 421407063 969024489 191096692 437547201 28294031 399923260 149806341 494891698 829990709 837964288 409303034 962661857 860357124 972884610 123997366 893252974 326717303 987742709 500801680 502468541 151512210 193622696 839565048 862463240 97459088 364336592 382916982 817857178 200414877 983859907 227165362 613773434 417417681 446950519 400653058 780942620 664412778 948456767 722544288 839362783 356904452 738029070 367731827 595531898 309096763 570668486 416268390 843972450 562991404 930444087 384522778 453650253 247415860 373201748 61100448 438168368 183290621 281195676 130753762 294628110 100071898 348486590 399366005 915171553 326585388 882016671 89108557 220079384 782768461 867445621 844378336 933144883 632291165 960975976 221084940 432713997 36608210 811252735 125904174 259283847 559815535 826509471 177449860 790631763 326035367 714911008 274680418 420838530 256658948 408064479 659416443 944328809 48705353 746733203 339983341 573860436 741616642 771422263 155665564 311143775 30788324 419035551 17220213 790665709 792725676 994176531 887027958 996979289 448302543 781271447 474722540 820602093 330117558 441623845 50696061 899400465 144476052 691819219 373998950 466962885 610874603 759104959 78921554 355388551 647862823 891052406 233308061 586171965 751305639 966373467 29292112 963360638 350969919 374705694 796376560 907160942 109608494 319056706 494016777 907653495 446154426 747886966 261827787 792501594 36149091 88301528 301216638 664961787 113044536 523633567 362119942 499325330 180971173 565307836 504724082 603906894 545106700 683994432 191208538 734204858 67934783 684257623 238243761 558100253 426545330 998199054 16519910 48774416 504552374 857041554 367421890 876613591 95274115 941171228 548563441 680316568 51960624 90367087 564730834 764231865 257176564 275817108 592592399 825543687 527398014 634518776 400747801 752669295 592042971 951831420 486268883 593499660 776387758 997964470 436071177 444954596 244128985 490347331 924429220 970479477 599514803 919794436 319985454 837316447 16011687 585763451 603128197 860485231 50209683 954521825 568210932 687566015 147561402 762932784 516128102 940197684 467740962 474442552 620189683 747417392 305784770 696659052 463608782 975305818 118767381 323139272 29309820 623872670 574226216 648342456 112089928 945105008 509946158 969101055 75335668 191232854 128555616 798988746 259926194 356008614 157259158 282139799 55435918 977630291 20508889 238571668 451652946 867090367 308559860 454088585 99869605 326826714 36392700 978209608 779540341 781659245 500718580 689841022 581246860 615357112 363801988 691557883 151954608 975539731 300685613 306626797 62153477 538552508 68903892 787469908 106045085 652402438 581638208 667592441 452794238 723831174 484727609 854960968 576778028 989583168 76146361 294330006 464198190 573426528 232580624 424643829 323121135 497579020 870621363 908776926 24422816 964296125 30515059 401929202 58879829 437390293 813534004 826746041 166364084 979470383 204589740 436046045 437442160 726272343 683299481 804000111 977165807 989170462 143805634 633503189 229687827 607732104 67678385 202896783 868758025 971539509 762725373 904601063 360067173 824665856 183879921 376143034 79573405 878873014 123909510 211927678 880648416 979512061 777510363 920374844 218351860 478226090 551808133 859162428 260431698 344170848 894653793 956572585 482378458 644606995 669199809 951426395 878402655 902276910 564812866 860457086 526841442 822134814 215752935 452450153 204292368 638561278 89050992 197478336 108765944 634208543 369143854 374782110 285899220 563004407 396913263 596531865 81456052 765119280 352576979 492611690 377015404 588965610 492674614 624774264 383831607 734305882 450490605 770843797 598236237 709188839 953935281 979293582 836381415 942929758 889304122 899764093 743731682 938507269 661256529 877354047 375757216 808079865 14001161 591792420 301350049 781141317 98317364 853168381 171292301 874289429 181956942 892714271 410046692 478897084 189216599 196787214 268380998 874906790 219858784 459227098 579544580 819696507 703245157 737348295 409355179 715647951 268434701 638625408 215632295 761483577 369197742 649069197 230472418 335242471 605652222 711323545 346851567 657364013 84967693 675346930 575274945 818476042 263125059 313924480 118572959 460495845 288926764 863141235 61101895 556753830 127196951 633069724 457908140 892462513 292972593 772711367 2388064 311038898 326908480 484063487 394844093 756512044 521946563 625061598 111607436 598443531 406901782 747107940 873410847 928905024 70101010 457392339 39673070 667118176 470961904 515338942 300894868 820606554 87810991 479911965 67211780 282048383 22459347 859534985 653937746 995998061 598235092 967643967 852876870 939935158 3772988 106145794 314148368 782291170 456057576 538923848 295820358 616166828 1408500 272234578 447541921 900239868 26458198 539641084 517065858 697347992 67594278 794153847 202420662 223921179 348927122 835482058 410957094 488584826 106388750 857510808 298808688 599790117 12773941 411228600 714876027 914755756 454832556 722059854 22243431 959107459 780061830 807985622 411252243 411420088 359860176 896052634 317040408 544266671 803966232 816765853 56021011 985050126 6848938 620844375 55077755 815144865 543014093 974530802 519543891 552205023 181018132 672985069 84031452 236218867 66879249 360688102 42995247 732691798 469544364 642193463 505954443 825641016 294918831 749503203 338862219 792055687 93974400 368101336 777526127 980581470 199137485 995525810 180001912 844687577 319253318 910103044 633055822 859610992 806254526 850418854 782245109 914820917 53134211 95193689 667308762 872246404 579649594 638324836 925874927 944794645 899542724 997882020 820766760 928698947 108955771 464327624 246895207 758434897 100959371 972938995 258096235 536761907 115011717 398449052 103386155 603654000 522552764 808178220 159996747 748694366 303113638 358656278 907272052 909325573 212823363 218439270 98184336 970359967 831250970 866131772 562775023 824842150 2788924 223337406 134697083 428474200 310991426 860471965 530241778 769617081 174475986 738096763 606732630 857600727 80616035 346636966 814773069 948079522 511794417 989217114 713423628 893520319 297617294 997703594 425538902 744773303 487105340 548971931 518950668 953199401 613710452 722004759 551470635 675567357 408072578 902930311 214068826 710637458 55076042 902040844 377556230 420345814 270352734 802746071 277542382 803131769 248793497 759446287 188229046 897472391 526652775 665302653 103794755 874949842 809109628 814073802 98818214 672375345 115436373 414254976 23227594 885913748 190367766 434235290 408311489 747739371 228946041 309190541 768662764 829641400 215173601 886498743 512783546 566901633 373704999 452394111 665410083 858918681 232891816 428927942 879230036 970929697 359196265 436515767 221724077 830333642 274403038 499104122 493382889 601897438 294760861 720820600 472670207 720870301 364696616 474929162 58777392 99389924 126636329 354597686 180578137 747667090 6824905 157138635 410268487 827583601 312973555 469263388 483392640 514579997 226079636 797383735 116583461 669857889 316411113 442730888 732034666 866630518 92180557 938918799 460338985 606331044 162742139 547873675 553017876 989597641 467659444 867177681 651971341 854756927 162047338 427408411 109071081 410833098 698753996 726169967 77247267 546666527 134973983 365104580 196599813 491453046 159940973 602160834 138293712 864999314 252454768 548184280 796764394 947447640 674824643 757739392 758252812 897649355 469732215 581857952 70318966 716674972 137183169 374101077 142784740 449955682 96624400 586069976 129845637 324242534 37439731 760003339 34764793 423509202 57923872 873420910 218235393 621650882 37159250 635188663 395213050 952855550 61100175 973475972 458260499 499927160 493381087 701210397 740038812 801906749 163526435 788998805 167199948 679097695 712433919 826820439 321842706 911928289 777064209 880241382 423740461 869893973 772673604 979904263 193800046 473399507 38714098 825189008 208060204 839551548 786237659 788463087 420777302 499487201 58961812 656256175 452293549 838520832 533852327 915843794 385660511 832818785 615186658 644883065 70516260 539395572 810997630 871746871 365887806 635107588 385429589 879101391 765150911 880546474 781790408 940244683 98948396 278600810 123529619 613343132 443599230 648455899 732402850 766343489 156984721 882340480 583971447 913135313 784496407 865170303 17397696 290063720 672318043 883161890 145740560 157496159 195863219 411712790 230515773 626248037 40263952 326513681 93332761 413985732 563828932 980067789 828974014 963118472 418405594 697379806 584626233 893658573 488499720 530964349 129330513 218163569 217492815 738892836 347279660 455864422 206408934 760643410 213844584 506852883 127750183 454748889 257052837 975287230 39657941 523333720 120395166 654172145 165281841 573786707 238000462 828334662 618962854 915542082 371215690 450373514 159189367 917564448 235870924 442102441 129044980 477222378 176216434 405720166 108300523 552939109 930253710 941324035 244049044 835658477 595558063 597657905 167768097 812225817 441981310 792358187 230956004 757700178 541931330 606701481 458419015 977436944 561188597 818967746 126773996 206059379 121656021 132853208 454464679 744988542 353935802 560218419 571292330 979656105 586964871 642036749 188700540 504632347 13213407 754309846 379442201 760597321 563958085 813803139 84662687 786462842 286827560 622570631 748094433 810468081 525379684 592668609 554827005 611479953 496329366 639234081 125082714 614538891 332651385 791740360 26569750 376444475 289517703 405714775 111768420 130836079 86136030 231426442 201789369 670472319 76848230 834875399 68556957 977446445 589821747 671848817 459300705 688337964 80535846 934471361 154144891 649588344 105145814 902617560 87552797 697092600 542635851 968304313 26609541 370011879 367044980 817244043 523231733 884611605 270659872 324167319 165860846 236188513 372667985 682278514 424430214 951387805 577373165 956433981 670809666 788831337 262355839 550179682 366607879 677892480 313125907 991479724 146530255 767197623 100619789 426879465 48147196 855104738 242687462 631216936 214947271 430778396 593908947 980587397 664053325 733350133 36827254 818657652 113301007 268079528 341402187 979195082 547545725 754110410 72718202 288018146 428920100 599948496 815289138 965145024 257467070 961832762 560730214 983821121 577955182 940145681 787741963 974677602 106894946 615226488 756965029 789388960 503164660 798088006 584614045 592878367 446613093 527338883 157799077 215631681 433197421 825088142 62509169 637107037 289735879 868760782 418241942 547903709 521723918 979564934 231969109 830340081 190502957 313051809 312220527 506925986 729496168 813711203 36764379 185831336 288035104 754057943 182239387 376781694 569593387 716915253 40677826 663495130 686470630 785526789 25450418 208273768 229239860 555316951 44976241 519921899 448600282 450087971 326988073 547803831 341964228 846000824 115593054 974700782 574056470 736365541 161851311 574323133 415182831 443467628 417341827 785932324 574504801 631769541 432210944 648620793 242604371 540173811 867677074 932993748 817449173 859203686 507278549 651339810 84084168 956899343 536012399 610632643 312956730 990780725 97260278 156907803 269882337 439659963 734255471 768784646 542135980 692113600 556297139 584154229 213335516 563874114 49955085 614806590 511591672 971287903 406062520 793122718 328499222 778329542 224073421 661184445 265720140 668520574 242152302 432947071 595300883 617030459 144333569 418074559 114038963 511331112 243340835 248839764 90618811 136802345 130129062 798311308 376825972 785303200 685670105 942711771 547890002 840871603 210504798 460960639 429669217 498950168 831376043 903345141 688278221 750221893 229899923 551586791 541885152 664486567 205546780 870342992 21093340 84640901 150443209 161643691 305352503 392307194 470092486 736506811 176888204 669870265 101843157 344797468 342470010 414065001 641262775 870960075 348821127 918213754 154397923 246875884 62257577 477951190 699884679 849059265 127481392 918122920 583549112 699457004 547411817 991597817 723270942 859004870 93313557 663348716 201566410 222517749 450186996 531371373 638018408 904512057 404928244 616892600 583200922 894097800 68711085 720549401 144367317 918983211 187417989 331181435 430109264 765262144 280963703 592616158 100376538 611446241 483376405 650563081 239069082 890823136 503089968 648587547 91806831 332590422 204683793 216623883 351906218 991638374 579279869 912226653 266118838 479918223 64013246 406708046 80645887 883952185 216254617 394248726 10782436 814253755 78003325 502855798 165955742 892871921 199333754 967180915 538248824 989613557 88543398 358639405 41500536 370168307 13875381 912682621 253753266 892067532 242218496 595477667 307560017 327771271 720233086 887328655 110980293 604717082 216635299 350094768 565997205 765785355 3833155 217333579 129352670 934873586 660819881 992427042 319271684 881972024 562473542 764171762 132695779 496874215 458835679 723144714 695531962 923032875 75184495 823797654 396440771 602872253 353437076 504775155 563893842 627013174 252752588 923004831 221985100 380960400 552731794 754627296 132559302 606617092 380568159 502318069 221750784 564566784 130310992 731985702 574286221 605500028 235220366 282713751 769510804 843332017 91322986 344318180 60793004 571345327 26348230 81432818 341555915 566758001 430936103 609196686 285639289 388221973 216375387 315415047 16806710 413900410 518643758 628271660 184980536 264834544 423865787 891310644 494256691 915209326 187482824 281497884 253724760 402378509 41402894 441484693 497758556 750795504 751225069 764893959 694496221 768271456 634893907 669156069 265994620 559269540 858857911 921772393 505011546 769236482 324388068 382350591 20478729 55953086 67188912 775775817 130704745 267916223 319560459 570630725 339879264 855133381 323218867 399158611 328981504 544814271 147032399 455427923 246291058 659236318 113754299 518893326 166906067 829547557 97618054 569558768 183256921 940328771 79045088 219768790 603080927 614886528 532172238 621295888 90344653 447954631 139909806 979968915 135324769 560271066 527634219 993446716 305881197 834744459 596403129 798822676 489452271 855234970 250734597 899419407 187457352 872722810 185472764 728398529 56986642 104607469 89151676 877735334 500942392 656010731 426781621 758579124 499468793 837858066 159696262 174375869 204375099 215301195 287908642 344726525 37633705 436539944 122536006 675269341 499765066 549160258 460611430 712144065 515319206 616121227 69212137 148263679 656600084 976429820 400448217 950520810 687685533 837576996 84382716 296466928 163411817 336735417 353904665 683974927 193152505 734516947 23371502 124321811 102049261 859532320 123109744 275386134 779004564 873760710 221900046 934128745 477823112 669101001 590702802 744448308 57852989 849286380 219133828 410425482 663677227 944228224 118917497 830999630 39601424 317897117 276916687 956917812 453722954 895435967 471615510 738333132 676779383 677509022 584127001 588779505 41547571 363003493 516796766 636847623 215992387 835020803 319496214 826984761 234771944 624012751 394629503 664199641 855499122 869371757 175225753 781498077 717088142 827697525 436546999 587064324 51913812 630286048 436955441 615275368 253823784 869288482 410844402 490484117 566684236 781702664 232888087 744385334 684371499 870231149 310274039 372988084 24292520 355657821 103638129 672281645 142676134 253792137 85574009 980223381 355049793 847585154 603003838 795991633 360265178 437147566 635565549 860980131 513795483 903268652 87309966 401376526 624141274 723151738 127667774 196262348 246892476 257253183 342560340 766042469 574986934 948657607 191456059 854253582 197402107 687193356 54367325 913214709 58484373 447774866 146424540 753019196 223194210 661808870 114906921 381010337 159818561 885384296 81951416 754151805 222340169 556097419 893923827 912331530 182532270 875314920 435440843 480158860 85640237 799133515 291270439 861942040 323532225 655150838 128160629 656093371 297690437 345643382 575674039 810324645 196779812 233266412 179373769 881350301 424655067 480559615 567929004 600489963 473982532 796433043 325730270 567912122 790837234 936211674 382362532 726968072 92946394 204214695 205421591 677898570 67011636 978642953 186416931 684369581 104190113 508162069 109349627 732878163 111278991 935580420 185685434 948460786 334999515 450288254 630404063 917417992 582212406 851533494 59457859 551615011 1844408 618420170 223231107 699445034 375683998 796462720 86969635 359054198 23436365 777201208 366454233 392039741 424990210 658083254 582205953 902254168 907834607 921103611 59252164 582618832 500406557 930044896 317567211 699419207 246864962 369617202 519015722 741590370 837149939 849554937 517063894 610925649 129305240 694756226 493423202 897475583 9376341 663827943 440444367 442786021 306021000 475273098 427943480 499998512 496315292 886710973 676045156 901640809 599505551 661509940 48384277 239458013 313874239 491064107 238409784 982123685 350865646 410259937 76635551 725292199 5236910 35011998 517145022 537154572 691500315 908482037 178510671 777591894 783877237 830492959 48990459 294916594 268348992 899424088 672379740 781449193 1195045 938811501 248252164 278617879 4183542 862977978 446864399 793639753 186229942 449774740 819144989 870771330 369294235 884678720 84495997 853649286 509984476 752960926 673422385 784153869 297355561 359328681 594358961 646923704 23906564 971236756 732777826 735827409 334838570 794966364 426300782 666888240 572661530 816705975 92477561 792376505 522783076 906146750 919574676 980884770 248365388 307494081 757623287 909662064 308888865 740083943 148016608 238484692 394844810 624812381 404510290 519336227 416914857 873861927 51806263 998853478 22680746 673493261 93779393 705874871 49228742 299254920 117355157 330082511 502452941 621691580 20301169 800130451 488714869 606632213 271665182 533309405 381848072 927569178 224346794 924088698 474662238 835930472 259337685 906939253 496638273 640869314 565681866 652252563 719397252 978389240 238576160 664298512 165245504 361824032 373658560 953651178 68423524 434359546 165380747 591455993 538038668 819559834 636412562 735625965 540837506 964977620 91208712 494261520 20024308 126870279 8152025 877301231 225512238 944985175 647460620 831469479 274527883 885475251 669306944 732685224 167161763 787818914 495852463 932292452 776969309 872021414 16602802 367297288 881939977 978344479 262323907 481872943 51965280 197606074 343723022 872115334 57485452 721395307 41847441 302266220 45452823 296521711 161983140 431020445 96026072 605451741 55094386 734989677 402195227 858765037 21790888 350864732 280831723 357613487 73933660 543832026 123982283 180404808 351713880 824395584 689577951 720449851 300787226 767822976 108669010 134583427 811640382 998990837 610733344 901261245 632037841 972920778 124640633 905301820 81423027 313531597 269685492 811363793 471292257 965454431 12091632 904325088 128763355 884822726 440529479 893144486 534768746 827054367 9791184 39874860 83452944 623365924 577643546 736383115 116779593 958731046 181864040 578323807 314890439 466018693 845846748 936541340 919154942 984128482 572946516 882721570 376583110 688311214 436913707 821045756 865712 596851093 556295276 970842268 452931879 851492490 405484189 818171919 775296807 858056662 80758108 487194325 500983073 535646557 754944556 886891021 690608720 990008336 620093876 848591276 606415598 836570592 716467120 806557831 141919420 730196481 126882330 588296864 146287825 900782398 283341006 707763323 194807356 491838753 288899877 782363641 566542118 971384317 32479446 286716786 44264103 94322648 230780738 975907807 528145946 722127180 6870091 453381371 109075805 123849470 118982693 296752107 55462910 245388206 256573315 410241801 78876495 987310290 241508744 717969770 264393782 552846090 667583905 702214651 105436797 758863484 417116788 839293199 234421627 958429548 105895898 880827478 566011581 680955973 238393727 721622972 101501603 747488056 415914286 447601165 753754169 873221659 676880858 702163564 164769597 366768021 306243740 492917577 48199925 719383305 308877848 910408308 282700987 870170684 34602638 873696259 682258046 694465675 512211137 612244967 688771744 739706957 116331845 223635089 227584568 403554109 44492019 998917629 41301354 635353189 32566508 974700190 466126732 752212396 282924245 471660447 210376179 500855359 652205616 668372355 656712218 696261929 671548717 829344971 463704876 575850999 6552603 49131387 112014441 780205076 352994439 677675635 216148922 835302250 502198470 921701859 526056785 721047414 345784233 682966280 458980393 965683975 553169538 819618079 239072381 961341819 17722653 413720555 358733396 940970345 151414976 488821414 27202297 684575206 126923698 368264694 637736040 781766989 371232714 461529169 369753702 598610912 168296948 629915896 561228402 890043659 1058999 743022946 68526026 126249504 450843428 500676552 366253105 428151742 164707524 400364590 466738549 815923215 424818106 637201082 235205754 709828327 133076371 398536923 170537858 913032770 726774621 730951341 738948534 998105831 621141146 760041720 132427419 270592182 363946922 841000259 517678983 637418593 548751863 852545439 371578618 740929746 321293154 550747312 214933617 630920076 164806474 801816993 222834544 708266843 273208244 961931634 399945051 763551668 226778717 779613151 60741323 981971989 47476328 884574503 235325832 285747268 195710807 207111698 69333810 244642654 102093822 561309038 959902839 965226974 230112262 824626825 335115982 404335248 768402815 922631956 143638207 448118921 288968960 986260989 602144199 660177656 232475004 442988563 427194782 764099353 668466802 907878860 86110919 397077597 67814015 855512617 527193478 764315050 171483066 878872408 45038163 643039905 469520216 556377475 123580817 446175011 361112918 392074015 24100480 708155151 531656631 985838887 819184498 998796367 568152019 994307269 719032635 928751891 450585567 846526528 317502956 822274653 207592499 453317553 502490305 659548863 215156489 513018554 623563105 700116312 60984602 253512929 355145031 759863844 106825609 126707744 340217891 550523090 293032306 317103942 346782597 537364429 634354179 732640610 62906701 853424138 571139978 818142114 480968180 620987509 462131749 806401824 147350217 341065964 1762827 349156500 55419322 779146538 158063984 763797985 697575591 767804850 11521978 898708443 253991959 478994639 450412733 630574983 143646779 461019852 43263296 692553096 903198199 920161692 377150264 717334366 255724547 326772729 123586549 514603059 797467110 840452123 57761759 295768981 553661254 951213989 193315582 616127714 204245802 301742357 396919976 693128986 44376805 692406553 248848675 822949422 79163516 403837402 42849159 728581017 230895195 602289281 49062446 952618471 23850030 778749719 810185521 986030002 179638045 546872449 147037780 481472682 133595693 258694103 514358006 552943650 193626168 219686818 520710005 776616864 504329705 895046809 586613270 939274608 157656665 717582657 547013570 672052955 100116817 799995224 448421776 730614554 36562334 46181572 338022681 592007414 49195365 807806449 469348310 534015716 287127649 847562701 461315285 578420296 168772115 373891920 304833010 643193521 411809738 803828393 584861827 876669228 130522126 769987728 37885235 890849754 171289100 907769615 445662847 608419435 217141624 637395288 129990058 253464489 589124946 654741049 290720164 957341313 42751919 84240649 65994925 606119390 476261935 750708590 780705623 936243869 32768607 620425391 318231854 928676184 310671268 685860610 18836143 230045808 80979526 791336763 74164999 848741823 154513046 524901852 382721100 741712220 157272344 983542434 591626670 721543133 635196235 863294202 547352503 622870546 290961180 884756285 436810633 922537280 660058094 765632491 334073321 737517322 773394971 973375962 35297493 662719066 61720334 752548181 726155904 940138066 653359593 931103284 178974344 686331034 750084976 959218207 323542324 692601618 60449279 231536218 403768369 438416272 244648951 967859849 486995178 517339519 403825238 671955668 154505035 652873877 135225170 815905665 22793379 519808746 435691452 641343819 310617346 348297229 198799435 937851727 457166779 779205760 627118047 982752129 462614260 725576606 202697841 775158257 246547129 569214333 772990309 897049655 209774766 428353976 617399183 640153247 681497795 833213620 204145180 358553087 552476086 651756685 185617060 967212502 603991729 821808253 179714427 936354746 19342143 301979990 409956272 808184459 13666614 169225107 590849766 700267861 297489693 413147751 469033557 799058566 598248233 599206333 43769361 330302561 238981263 326480220 281430667 423786675 436842601 564915703 37725638 333347414 529365418 698308791 372808852 735574060 235786061 843970557 65205310 640964914 272234707 712763232 774788797 981778296 685155114 739780802 143845573 205375192 381390411 935161885 726867859 905966423 877903230 985284681 264999287 973723734 973794939 996863555 444928770 594602142 392847677 597220698 304731984 418756301 95957880 608055089 209903665 582116707 29277409 707934829 103756087 834159983 601905457 627814695 417477514 509785584 297763044 630849071 473787717 930374451 135260340 786248956 398320114 905618572 630912003 769460294 61140429 813835469 320767973 645913451 63084365 638097911 787152510 915212045 70776136 403232709 200644450 649681962 32316393 135131388 183090368 304870889 64488310 177962578 235174578 577791681 599267424 656334233 660931267 949670636 152898606 455069069 457294089 756992195 249104846 637343162 216956319 632576061 264460429 545879871 256467677 432973620 155306163 189539174 690145468 923154927 523933774 870303120 148710580 954524359 2688464 802822357 98168436 650024027 599860556 788941434 522952715 984830443 241995666 741177871 67102154 832501094 102704455 290972430 298324145 757212792 574342340 912062773 115430624 965354768 98837727 784695667 692031698 898336927 635570067 960976509 15508075 711368958 11902828 913047570 192112269 514325591 832786435 859817663 315455876 543006121 292699811 337351917 569484089 655729430 11096646 650937374 483943680 859790854 107483359 901709912 443525924 873694485 4984599 44860072 153414612 829355553 139520490 725054259 29375781 251825851 225373479 265392626 166584074 948369450 739717177 821395621 202496994 222496854 143650911 187969230 640258936 874753469 549504508 830070297 345926315 730384964 639369187 763588172 99972729 554527272 397178919 683942699 117699536 244064669 371150445 649695326 222657114 382815489 413625668 863130582 730912406 936992055 467000521 557658203 112147753 578171986 314893058 911878124 135891056 723260791 296588671 558329943 291642493 549123032 909199682 994503429 27159348 410634002 279143308 709216617 60952761 842525368 80902533 575697934 83402627 608901552 938899056 941277341 631526478 831646019 389645515 529855600 563281949 807009165 73384737 752754432 235757772 584617699 214958668 899605074 78076169 918055255 244719183 733957726 412156882 740001836 117839751 226901390 148464819 842783761 201910718 260873959 231170727 631788606 657872829 943138609 260823224 650986308 111373229 279179464 245928868 416693860 383040754 591002495 374577778 385454963 739253032 800501976 187624000 386640640 583955019 689650323 158369120 315514549 441867698 713902575 147129251 473725436 28840850 696212956 223040740 246404598 97183011 283215884 317788460 353493315 106791413 338654811 435740187 563801117 38304727 884323611 63339845 251436268 58221880 675397234 749324204 805132099 358532757 594185755 930875432 968029047 422008006 767025112 17969400 283494524 127771872 764434372 330451418 963995856 148790808 397349931 16085826 666003379 16683040 116019298 625595696 724000845 473987856 754942361 877301525 985232194 195073891 868836115 583134062 993588235 159785572 589985139 219706276 872230804 571429120 768835363 449435319 748594562 437888840 750324102 101627784 363973991 717314761 855197403 694283824 848464989 22507113 541670427 91374848 925436039 336759916 939242531 252331494 726603163 300268518 381523716 712437141 810155827 141916247 629160600 151905516 912365671 581158430 832578506 467766979 588839022 77979525 320405698 581375818 967298359 142778962 308268555 452430460 901230712 61257555 980325696 591912357 648890645 46817834 221455607 79182744 291520872 844599567 928199736 710774932 732821844 214721188 560741728 91188860 803867521 44256190 571774608 246312377 386010998 224274995 787023002 71806831 84550105 146860673 817705100 335940534 423236655 27809523 528056649 384869167 536233156 120149307 342359588 475784885 751935978 366777119 594774506 172639090 814935647 525252811 607649741 237315809 820041029 41002315 420709274 537916166 649847647 124981023 592426853 169117584 922971882 719690511 930161255 317745680 652891612 115016062 470287080 561269074 818279557 840409904 840606763 461020951 936352072 120777958 774011667 20617924 763060457 170680683 293040067 509896562 524089078 19946758 351627118 452936020 836079700 167045776 709599726 175879077 845097162 114013953 288724094 331999523 420800900 95505709 548879781 598305922 891780880 52815004 77487011 11468680 877770814 511284434 981034968 894875918 926226326 660804929 986474769 683420555 975221194 116707746 829950686 15159435 601859755 369570152 909990752 179027060 378754410 580950864 840735856 321422007 893840341 501799852 974905732 1576983 580774669 248102222 944565893 496521941 848886224 62514756 406386759 149750712 419339624 195985273 758823329 308566549 456348448 363741915 732808060 78651102 233508390 157097271 658908341 42641937 161881755 279379458 920596357 514408303 731843787 535268857 592171423 380630831 638638589 542604649 672564253 639171668 950378255 85804945 508540886 140170191 371493833 379367593 482974864 629757643 984851597 102909284 331135029 322976901 419866620 271832926 578480284 678772143 890992254 281276110 976304534 122587532 784849323 429162013 929905795 41170250 564697824 412690865 500169032 348499425 713344735 390053503 682209268 173803792 587902914 79557823 802506177 97293959 330248274 261859865 846474784 390754868 510135209 49705444 129245492 603950660 922766515 464606322 476019899 246184900 283473019 437310660 694576660 96500679 743938947 244626382 787788340 47113019 449735653 21913281 263120913 323487985 844418245 64626488 341794990 622653512 849616538 273676191 670803053 175013888 313847000 590255581 704518557 455353658 493711077 718568 235009950 136353639 533805473 112857021 564249119 2830853 975472292 182214320 387812745 394628531 643758496 524593986 571522140 296060516 408416294 246682050 871600208 614215446 858610536 185330649 627081717 545261007 760358196 519565562 941312514 519095363 678592453 309352370 510334780 380712550 430599976 583325852 708918841 250050608 424008949 430427369 456650000 29786585 515239684 608786604 760767176 87473674 886118330 170159904 378560068 428492515 708697846 480881030 484172836 172098639 213617979 122054316 980913008 29557311 621851750 133259432 860814231 344921430 449817984 66182015 630800644 111817605 585979412 214624085 737899934 611087302 941225462 68351447 229388189 755034463 776300266 641956486 957224182 353265353 509446722 372995601 675394356 293139261 976650560 141697279 250476940 134774956 398592668 117016057 291973831 331777408 517869496 92539528 927981631 290649410 701484144 219423293 734641133 409141038 426976900 47059697 561272544 133442508 841068914 169745084 556008834 292273503 937824511 159086894 652027410 217901493 472809444 168410300 608548467 685914595 990008323 817417097 878574106 902707592 963375777 208961543 918393763 75790001 520723834 949442490 984963529 292188926 701299728 463974916 817085903 254613146 313801390 596251591 909986969 377736305 680970666 22293055 304910342 501248973 655054528 105265554 397484061 369768806 614708857 190794697 454820170 645563829 871696847 320862373 767502654 387390130 874842092 97592607 481691051 12773396 781457627 436174031 537111187 113019846 675429778 804075629 935158529 721236105 971845441 159464820 863794202 286971591 665712123 627452925 663732604 88188846 990789781 484687665 863622794 456031060 879508726 839583713 865551104 445700587 803835612 350437385 903726130 105508407 242863839 281877639 558873481 28544446 310094648 680782919 703227151 107398254 392902291 385932046 504877021 179160587 508751006 170465962 984833953 910058637 946651928 75719905 933827819 69993101 821389926 213822270 985630484 166595478 484815799 622287786 665150686 22466049 761422621 545906396 943748287 14083944 561982103 612625804 694769120 522283724 749683936 585750249 882813284 143359083 355557391 51630843 336950591 361172959 850520438 253442085 958173539 628965072 960347234 438860053 736955415 337350225 811711419 21752676 218183937 85775511 645014207 41428524 866393550 838560846 846636973 662513837 831932998 63923857 413582651 705749853 969613680 281322442 781298361 117415806 459366330 11210112 996534961 163622351 912025979 207142310 767985559 29223624 67381102 726146604 754959791 74388166 355752133 109940764 319087841 12563018 538974874 168432636 289087707 310837809 390402805 82967654 352137318 419377603 420560239 228312459 498208097 582557567 754125478 650671846 789281796 663379514 846392525 186281051 903577659 111004213 166711767 721077321 937572747 393721344 655089475 782912988 808180786 35541572 954162836 20682514 311738406 97356270 145632466 761012304 825510383 814416326 835952693 512036940 570306230 427733449 940265344 36713199 465454816 1881086 909105508 281402646 765996861 587986335 888696587 319038212 948294423 231073110 506781466 151302830 315928024 215635309 921311796 366093905 826125291 465874391 791559979 344971299 353938440 388512374 698383472 439425654 449277319 469661569 880139497 641540387 805120234 647191176 808629152 644148942 700423702 590993726 840899896 86204836 418190985 44786364 310116437 240852716 704810563 556419905 633531686 396323261 986397960 476641204 656627339 143968373 797511776 591484978 975771080 31739097 511802991 302477885 468864012 228052891 973047015 2137350 185470301 271279159 960402726 120847816 466837752 563724299 962226322 52518258 446888412 403033571 716321285 146840129 945932523 118256610 211444832 248056063 830818527 17707426 313122912 318703583 569199149 496887959 955223985 723456095 848031569 573007682 659099322 115330816 629723863 195176292 958106842 692015376 707174598 64333801 378789497 453120687 574099792 265930183 634747809 120805094 150189303 258497605 609991854 684519669 961016053 245712834 632387073 542579023 862787449 148832813 649654142 930308022 977167426 528385901 779237274 690505777 805196259 227520848 492556907 717596034 725041920 543176667 963026886 108781776 974027747 111429659 483024497 101105385 743831533 221352530 797808996 373031437 483953669 283374704 413944399 88078492 346367393 624085329 641357010 138351703 184665277 789208883 793206782 667120386 673583603 13179665 307142768 430639261 599500921 333760033 551575504 11961006 241484938 129440518 475688980 316778782 805103564 586057379 916232870 272954459 613483482 268985155 301075636 667913440 797599996 444325043 594326538 328198584 683260251 720807416 758408155 487155186 646131904 42508489 204113211 201649035 535409767 488740869 917834784 216732884 735772113 55385434 498980535 10672866 328019465 457592876 935752431 318123527 798220387 717407851 807889314 195294060 304699295 111985829 445741045 545197581 947432224 120490845 473181438 152687964 875232769 562210204 632271781 738483197 792436628 316464333 385940679 877854407 885782296 956766129 976673204 389951185 524054497 139602585 778131697 22445881 846370639 156830838 646335901 168873961 625606972 13489644 768306777 78415847 937951843 171551518 981125364 355596168 643998827 43407576 472883250 176545093 749384902 337377830 840336568 764312917 962243149 199144561 317760735 110589497 286987122 340284467 498961788 243661394 291327707 647292028 827837262 703820443 734509159 59634521 111970072 22488586 834726143 78295894 444501004 213735826 671535950 771020182 775678261 200603572 709471339 311728075 942782063 799603137 866473547 108617213 972682013 29279249 911146693 556486139 630905007 305249255 652770400 438641317 971391183 118273228 285343035 452933728 648036837 450153358 728589242 271136104 537485119 121019476 463509939 200189578 975211082 309037449 865559094 470313460 535314243 114282184 135165146 748761084 992495966 725145718 855297500 242941323 331819226 1853304 537536419 738502401 797032463 95291307 367622905 374372370 420947730 57573109 513610809 308584790 359389970 372307291 432087791 395809422 833030805 665397732 746550315 86368797 322149359 498508859 581772186 52621174 674945617 433089833 960566081 626525465 802000067 400693952 783334156 458585910 899048953 481323919 651273427 268485402 468631258 480269461 614902043 195860354 468522413 531526684 643797111 121458616 138065388 765882736 781999495 230721191 358962095 706099798 803333819 404170433 961081270 643209356 947553159 5527398 366456196 115964214 152280370 94725252 919941291 28335532 269481406 36614272 423156071 515452778 769478449 203286638 783089750 250499191 848793061 287025661 818161159 519795961 784999213 566250766 974244443 142842910 326103075 578190758 635988746 186232403 728395946 127787913 457963519 118593957 685651396 176961925 370357129 401965207 628172021 155529115 915275559 163566716 946877343 174930041 960521349 630479492 753883954 485143628 953990821 156685328 401968519 630702731 633567626 360950707 993014308 658056416 849513031 449740155 823915932 539526918 826485146 496299329 990187650 55473360 973385182 648226842 786490029 563949794 602148804 345511121 880983285 180832636 970109066 520044454 549075754 215738859 294203130 319326777 730683242 406237573 616776295 290400319 384296981 436231068 556531764 647883678 956906999 157905815 877409462 108313089 669305446 93020173 644415627 398498187 664305607 291908668 437027612 367289936 853376716 242390788 429250334 307425038 343132662 570306102 967075894 343036712 927375186 136648413 731036460 442523374 857944931 143451271 965276827 384239001 450138598 98427393 759139238 686070546 734537280 204853813 298737177 338775464 838819708 244827269 248126082 448612886 757238149 798479873 899695351 273405487 513104170 64724305 395013278 163458037 163721541 81175985 911221169 84354144 710546342 77257092 897621849 305686009 974920632 6499882 602288604 295038790 595712197 457650936 640685328 53085221 711817943 534511623 772673679 314385417 916908084 530414807 595283845 533559235 942699212 29104871 776382484 334541183 636882160 310258481 576881998 86621134 138432135 601478100 621929604 105038747 950006988 335870310 483484778 541825968 687526915 53548554 328864764 315031150 502852215 779670850 840734242 156844036 784170625 19468534 801658273 104771154 504635472 348520349 356601195 506276948 727519176 258142582 565336415 51316037 557991431 297970229 678588430 333315430 373850336 194624649 258982967 250565025 339718379 21544204 700143686 534674068 685604787 216792475 659362041 126903866 405865671 217822344 783999907 286400526 637084109 548821226 781394648 745405254 852741629 94735529 128738515 139251030 314962653 456011464 938895658 137004944 957082450 653853518 829008987 449779060 765445513 35482195 961931702 54540332 210612537 351534163 592561024 73224626 813176235 126869513 941398293 443939195 943244753 268103068 421728048 773323697 833997117 613869498 778763722 280651101 452569010 285785389 563152120 484995707 978534473 405537080 560508045 97900001 333777982 565834330 578854600 68695506 756629657 339276100 348398686 559948076 595607222 27172163 652668543 142308007 945769022 360601619 649538818 575745628 599645787 403728533 943225636 167925210 829043670 175410641 737763200 414325403 550385757 24744117 114244801 47657578 212006229 318845335 808272934 81190083 373719857 388825220 603255962 133209149 645783617 310825442 843185435 57462337 731357873 93651372 939274724 637462421 731937082 373086208 883116009 339692336 632378626 170350443 934264310 360120877 611667939 366741667 992139762 236406799 637280222 281153645 986637682 105413448 211211723 727693516 832339581 491197437 639172435 19755160 945215862 354088477 923171081 373435494 962096418 252617797 806854977 608084542 929160559 289745939 563086071 202719314 624020664 95869675 109377986 127606028 764974375 26537856 579460733 168041402 472387849 633765263 842465102 305927019 619268193 592921927 781478251 816931265 830638618 38268760 614736333 113561610 840568406 158686323 598826977 478461251 721762673 652214515 982634907 242292314 923580464 937901 540707291 28058403 847321285 253042136 500313919 374753168 478745873 381811798 469240083 327931037 535534765 814734611 930600870 514192042 959237384 220434821 423363846 880127324 925413253 22117532 160887750 694894241 761696227 575527623 795713842 638358157 648039780 847138010 941391904 341259863 993331774 364950841 951475454 54243274 599015465 213940027 258089255 462915224 589772929 220797964 734338103 242099411 452866757 77162779 551870806 80641737 987009846 544161581 944150368 215169158 552994118 183054736 498314342 673306924 759520193 311300023 519832140 63946561 949943662 858559019 925442447 406451699 692902475 382913075 761324246 884282857 929069233 329196979 691686858 323474856 642048612 408375882 480781360 425154363 894319078 151342775 674531390 354552331 634214167 614720449 621135080 435022375 841558501 323385340 955953366 236165867 299962140 200162584 258096971 227951945 440987413 757467572 924231689 209041794 513762421 201238872 460149395 324203429 619876778 492924496 882513670 554561576 744123330 627312312 850490182 63383029 212210525 626719731 909143873 803150421 816061239 436210013 824249202 334119 785708522 110988349 152422314 392912923 946454569 442886155 543544574 195096284 410260881 371462048 678240854 374791921 639114046 292220777 709130599 250125291 302239125 237433314 359867647 360875427 783017344 365023487 392848834 819124444 821553856 709363586 986475166 504755960 736010933 83238708 876266939 25152621 76347869 703755203 737258591 224941039 319202341 55445264 112579285 697739837 824773137 88122173 836718612 395606283 597815370 647728561 834208247 270455347 513797740 789389156 848669095 332646671 849148696 142473414 494032364 178691544 508118423 131913793 988852838 396840685 795012872 292650468 309861141 125904967 299967715 268615825 313056742 120340804 464272548 325702903 997570544 203404961 608045262 149321095 394690362 644107668 810701383 550568150 712925578 120208906 564661264 25301502 427013831 563686999 618872078 372211723 766354358 113127786 756941521 749479283 755926599 160774285 623642695 21390761 829372211 257298799 747811758 674849742 953950213 703097135 879085822 17961893 675070041 55815420 194824261 143120379 761570617 524345689 881892566 526857602 989771625 822565795 950429630 589583978 790890644 648696486 973610152 229041256 314351478 293639086 467726786 622165998 948257884 175367466 500318608 556950935 800628467 326114554 737895067 335046818 626849924 221242554 391786140 15249632 720614460 626465969 801538179 89750882 289308217 713928730 888604840 801252445 825952987 126956423 397708383 246650809 460237038 650122470 752988525 840982346 877119406 587436120 962791461 138977607 896591358 541449751 705425407 879509384 960840810 40010135 796275820 695975478 862417708 583245030 703716076 480233468 972175923 658616173 762058571 287688835 533014114 385398631 395523741 305437197 421031209 176812252 232364604 589512918 985912284 99905230 677656084 310579962 883236358 385740828 976702136 25577936 537899467 532273195 785720622 160873184 300666914 295165224 370443436 338912197 909130672 490038084 956035789 64174075 992565038 95595835 589531138 522078173 612221991 931596192 941130437 5753242 18693948 111332379 478040140 342760466 864629753 833293673 897210883 146037287 227618752 73501487 508230836 297541313 814605694 71448351 246099413 538790303 949977104 55839908 258391512 241229883 300691990 602166629 837688093 61196825 268104159 135322685 801648118 764302102 937931986 131751961 693606460 270540433 358278519 245709374 978263812 169795898 736125546 9026721 973371328 170333624 719103459 227975399 340452916 260315360 870848830 288316699 358670906 307802604 898544631 834616122 872262190 872423911 885432060 456593883 939363772 186214791 675560198 254557907 738772023 628484119 657140071 346740335 926049748 171954869 810800647 131497625 141326977 440960198 641256359 355473239 487579353 43931052 291522657 358773450 894035746 31804661 813996339 438471175 602677478 23754513 694989441 352126641 790274391 815746333 885687042 6829786 314846436 209518140 906163356 476616735 666057490 130795974 869180915 357500821 936256780 287143503 786578579 176974200 935023079 416420805 819547025 538787214 972028350 203302242 285729739 336965218 501903204 178195845 821067209 627329183 668278669 138275413 950852182 596018659 887015403 177037765 716337965 176515015 363446689 26052612 237694148 605256886 692189540 754937878 878712689 756141447 896957526 541728775 671230051 31847599 150397139 157460320 682786287 118329718 581879979 433200973 606680989 202845493 805901027 144128605 308685859 630574829 850857621 626422299 654431491 630140357 980408419 273418800 296467996 779251578 934547339 1763241 183210662 180101160 646429962 193527130 429009024 421750706 923756214 420600965 975898814 404723065 846055800 272573630 374858377 565808392 601036313 42009527 333923711 89696973 196329863 58366156 955815394 523280487 841324792 497132639 662538363 370512359 783178913 467077963 857795028 48179671 213306158 398592617 958026995 650961912 856454645 100069163 488751221 485265044 838387230 646612717 949330546 455481424 622432461 524972329 912743688 436643647 603426686 47273754 63242982 882286904 965096625 15609996 200129597 424131784 941800299 74319390 780724146 290181423 345641261 471238112 835709561 67343801 745038367 810824598 842554953 228778578 938611558 310869567 732201867 38586580 362895960 818621495 876002421 212537139 665161282 274474340 539804564 525786079 814502788 389877538 876137493 493664734 778583657 19332650 732359061 353967716 827601416 534504517 617942956 473354886 677217423 532114461 887539918 142232507 994387506 58708596 554560339 72073533 923351751 576098147 921525732 69927529 723050458 466575159 895045093 335800627 932945976 334514581 405550332 54884945 309092147 264427700 360725016 801210720 805127036 424982639 875162642 116128935 724696022 220990923 628225376 667297492 969621839 188839283 565659731 451122082 515449875 286030265 875552076 64320869 588678875 36998342 558910531 865004848 872657210 634868062 853707070 410172245 435759384 19294968 321666290 704953986 991025934 182577124 265160907 257896360 654352756 154577442 560488924 897468709 972189617 121247818 248743205 58653173 422571265 889449871 935584329 142251151 947111698 582179941 764416804 262044102 569960984 707511683 791808636 612115221 772264698 511373204 692805003 21942305 710051787 324812147 397855870 772303572 790056227 878789369 974439383 557531292 562776024 150075676 335089676 761769049 948930956 261661772 538786913 171021066 571038196 69872714 131012552 63486103 701992841 60751880 160247611 268762183 716822533 40268 701490124 564519204 751471744 206139924 973345921 206932281 801058336 311850721 351788216 193044785 567286776 147705403 186375907 146682416 197782565 49834229 942189561 51466400 724255610 113111592 819743405 546584727 766507796 349005517 933792919 656384402 865238030 694107046 893961340 504334545 679173162 743999487 832177479 23526846 985505241 714943520 752326859 390623192 852875338 440252164 506365133 124524705 412980980 176774040 273489396 214785578 595512836 282255003 870425508 435005585 558532951 46285089 822698678 465643472 864821404 673136767 765056575 531537642 842206123 325385742 909613578 382022988 579272208 531945820 591701531 290137480 406634194 304178936 534773020 428799974 935443410 246552550 979624867 233586048 500283436 387952029 703714921 388286101 663907549 155844833 700609323 166326295 175678372 236768686 428664308 76478507 619540616 218880840 648730568 162981223 337051653 408487450 633486586 406156704 724923709 342448240 571317804 425565684 565100135 114002403 611931164 135368855 428073716 318573866 369813127 657821915 768219396 699865573 702066842 44751692 999004225 33220560 673206133 652632764 786719562 128922953 454685406 345459623 633311303 77578385 793228473 530673740 775308361 445609363 688582514 920954805 949414202 92271926 607928943 411807877 881635718 263441009 615576106 191990957 651903581 120528833 639537015 428966836 622279912 755007662 977387063 554051640 728649145 250214440 575108786 303999969 785407830 529664969 607394702 255364474 288585748 184595098 717438400 412842331 929303335 254066111 770098206 103093107 954329999 650534723 681664575 376298662 922804020 486980805 509211412 538984606 847438089 369334332 736363220 67981248 462928020 130629661 558984972 461632833 684916430 338622458 346126785 348869404 849608356 375268891 539350277 143680586 775171769 94127796 270361216 261498365 333541284 644890338 646074023 315472325 982506177 81822491 579941896 55791036 579397756 132218303 483942378 809836000 896311025 159684489 216446621 264846703 285844488 704182088 745402867 171450447 374499078 307232207 973989641 582772635 793699955 203687655 947283596 852738369 906177148 68990159 172505590 899962412 969330231 67324456 685774293 25810824 495905634 402395525 743601138 212790063 981393509 8914952 182642675 274756554 353312813 17632011 412179555 380368274 478894307 671621473 693667754 38106442 609360362 107859033 196101831 67385328 773816997 370958038 727137130 100019782 497790182 388432562 550227788 185693179 551820094 58427447 875120878 240282608 829867440 284842826 693038118 38231401 668910327 697548359 881172089 650221486 704349916 200911487 550866774 375035752 894120534 244271225 693747216 295313155 376002585 594113472 846726596 691374490 828273192 378350824 993116303 272546559 964624833 512312233 777490470 822591608 993005081 282782620 806518616 915458805 940194081 288090316 380079921 786524218 882727632 416133412 619278529 10798469 882515573 215876413 984814863 74514737 483728017 191354279 275103742 771666597 810063320 250276909 986513608 167100280 252874381 784265402 977332813 2949518 526760538 332862005 881047283 324965197 388578191 299523462 720716243 275493883 829374915 512936970 883956739 659749837 941324854 599788359 657639957 240064688 790287111 675666401 711517154 13475860 126260443 254256590 952418944 815908566 889207792 214247879 532762778 578998844 840259988 12802048 538894050 266652472 291243741 126434528 140870169 639652195 964734759 291534933 510746095 299764361 662465917 252718727 747251210 368278771 840611016 127037885 558910297 169301733 763015756 331524640 688369417 279866558 361297659 457577006 808160840 21807317 744279188 308030135 594270722 28123549 300153845 314042120 388833263 641050853 972132818 162125749 500827260 512864414 569824109 24226735 721077236 851098680 896342054 316871046 341564659 279818362 555408936 42032129 80607488 362513580 434464556 220321010 341433470 451057728 600090189 476413550 624362909 229659150 408179143 150277066 687931683 529307811 973176087 175727291 217021050 118530537 425074006 899671867 928746630 560206214 791630409 859328556 884784958 32285148 990323292 152532205 863553991 461939799 516126929 596400616 979826983 587819149 718848654 162058111 776634375 260729034 428893458 811390006 812826824 56142934 794393379 680018103 810910518 350340884 527085990 667362446 881438463 532055121 753290954 643598176 911793466 148471146 581379291 43587804 162973866 195099217 448773810 306312225 966700051 829806523 955490305 297787316 884179322 434257680 489614172 119283053 764653807 112517060 356975186 130284049 897442607 202742684 291266090 63396756 392580885 770600198 951596538 475053374 943726258 36648875 135744017 673008177 696796537 849960660 863516427 369613210 502607439 192817535 662021808 136937654 673294642 351318717 376314387 739165504 888230927 259014333 716422780 182360183 663524459 387954453 938384022 65613247 688784127 155775275 696018688 411150631 799942378 223051467 731057714 888821868 980263391 192055883 274005574 242789313 712566305 589443634 918813400 577072843 804983222 182949197 418805214 372019691 904386260 186836933 277102861 309642689 416733601 279743191 908003868 189972718 558673690 52885603 99329192 777926481 819760155 265848129 800693978 770184760 851211484 119376420 217315069 619665802 662986503 282434843 538017265 59156569 262678489 520094185 597425745 85094566 164226712 36701636 118369189 443575047 953141412 134156025 548554555 717716240 729047110 77407572 742151606 602465434 835297828 482056033 482863940 197138796 915806154 106811476 231601839 313242000 385028371 466098231 768066980 275086568 690070985 426495233 588451739 397273994 727644672 871571621 884338998 54635519 430418450 44044266 787399277 37157197 595792461 357431262 496339846 254378007 512020742 135796753 357341917 108828994 447938226 88195114 384414912 610212372 663450107 579144780 727409672 212326903 438481848 68909269 739355848 29463200 632152570 453923046 671809482 122099774 233702555 46508349 940330787 280030627 410269512 7796110 435208152 86117254 519389687 381662660 949165840 204058155 505748603 599663704 815442359 322725354 888678575 474805867 562380768 147380182 646061071 19882256 449865837 153468658 740974132 253951588 632093297 331133787 866715875 83370248 87573426 167332412 767458005 406281911 658719617 901190842 920113921 578435863 973725423 458177483 503244409 346315442 710236735 231283387 480238373 338235694 893363887 451387127 795416744 378690986 967694732 42796728 678317041 6440806 358744713 98958607 577000681 243008168 767279949 305261516 850984383 771267148 785807835 412862752 829494272 456786682 664943321 834429394 922577054 252443949 550260858 745132016 853099759 206749362 257788796 55311390 725739678 415346888 676973312 859065590 982974718 286744821 763306279 484510819 729585129 180248223 937333372 154501458 251989445 369476088 590954355 50783350 837501436 449472717 575815582 328689173 587739619 180478196 778058925 229889851 392990144 778299925 887499171 242600368 645306510 595564335 873905611 88492349 805981165 451569035 828122035 200866144 875311401 84597773 767300448 338767422 414969470 387264826 764191029 612163010 829244335 160128205 254682332 99120315 278527016 310431845 525530766 45356615 973619776 262027181 429903972 409151194 667495538 571842050 896789929 123665283 256001486 214066623 874158597 454672811 722939760 535122402 915311057 503145903 578021535 12616254 237363547 88198322 550774072 320582427 572153409 392116431 623395114 172527849 751558195 400293203 463208827 243233578 648583173 39077579 817669363 70633005 585655143 396419522 495118225 247639326 319952336 44742448 282297303 32728982 61153128 237344750 953731727 693496499 851736545 832782763 929119368 291898402 517128942 95218976 820992165 147914676 937912734 360663120 931495243 143170980 557339283 789338377 999699225 229904619 476317094 875759325 879393200 471873404 753826078 480774716 482461380 534187100 978373783 383591121 550978433 83858941 304129818 212614831 231387281 31031528 342920811 556819227 887911949 173966012 972075398 601047614 906390017 108336951 526643850 773253453 958372348 136608342 224092435 418073002 828513576 151951968 582367271 81616965 734789022 131221233 698279074 274593424 967728563 44069195 103250398 323974459 562783972 577760436 791672778 777322748 962015833 287799655 888565239 125412808 304756309 153489456 604466029 424272089 671604334 185998069 890927907 105754364 254465783 629675328 931190754 67844342 976196564 33228768 980237475 87582775 772704891 426407079 885497416 309953797 929542150 718442962 995968812 345201449 697712697 591536856 987326156 179900048 576465949 197410061 557475609 162580617 579664761 49881992 571774477 360867642 995061650 469918400 498490633 255345673 521110656 133619615 743107634 39686209 263186875 807093573 904062638 315973146 517418447 176782986 747662484 515209062 713004003 92546059 886894554 598318839 600495121 362891567 873685449 27849049 514274781 645467365 942170165 148788215 609957327 397742539 957966540 575486889 929112343 91021951 824020931 713988610 974176249 446669303 877187569 163971776 626275736 113983826 191865078 208638185 530108302 37188896 830211951 111700339 877505402 405812043 726549506 407526075 559444295 789623829 893652696 64019176 610955257 895798775 972769205 425450833 587157257 54524929 925247763 461507693 829560996 685742297 946903068 32715664 373469097 568920709 682147152 96108674 402472781 4816980 196012702 137148593 750203037 399931762 890310210 907747818 930784765 118667789 501699737 38020080 595970383 703206873 737666070 425146693 469506138 13836507 169637999 913308215 935345272 238511690 882663730 64794082 226386894 266325459 828321661 365685150 484738453 587499027 720557558 217608361 355170726 26906917 721613884 486180665 696421411 205483027 294054120 314745951 657501641 451717976 514953224 477593913 921745528 46271029 202700348 595043972 900274394 883721577 910216700 11991052 419693479 104826982 149052377 718627861 824489080 105080889 191414923 218630151 702853841 277935272 485264460 428732332 493207581 65043314 652034962 357374025 816605000 267364074 269864428 242918528 318350621 345741604 484178375 122518298 305915181 15206919 720473818 925115665 970072830 226800169 663662404 588180683 613432716 334314280 692972197 880268814 916915082 293749038 597199763 150326283 356995342 286464375 897616271 7478000 465268029 68279007 763405935 497620395 660592437 264669907 295751904 196209732 303088630 622007624 869337454 7952031 855767889 204189293 846526788 175092645 538953724 599262628 837271855 313611968 799000779 137723806 345482999 98079348 291917900 304047977 345711950 161064972 575046875 413159367 997540584 753336063 840303211 114081449 641407746 337976081 658968869 141008338 641467953 818706023 883433348 345653341 821671893 191925198 333614031 11392341 77249530 296686790 624889152 83117664 345915044 83762545 679836877 77469284 774591652 147428124 646291163 961021138 964539203 344894364 975768468 201838332 901200738 31972253 551958998 423365652 830035322 340509700 950857343 714303984 784301126 130273574 962195837 189984388 513975371 430509936 529684175 297929264 313814012 639646883 643909257 530203789 950432487 504741883 842353511 152788469 501055395 104730057 918059362 222836132 499717801 587914626 605709667 28361527 458146126 342156408 845459900 61663885 593229784 147107714 888379703 261833268 471463047 687475935 931663729 23069946 548693763 425898572 953993335 150254280 555800048 484859612 596976681 83368400 666547135 358511721 373472124 302365184 387376816 240514442 811515076 184986026 853057315 75925127 214076528 873548564 964010622 489197574 880289177 269497172 379433549 147157494 952911824 929441192 945310812 591668278 597978285 64977489 712997083 301374193 441570091 270446913 494426146 435141816 700637383 279595862 736591218 157772352 990020217 78278438 650275742 236545273 783774293 389737018 785619149 13740769 427368818 505125082 944763164 182715682 346005634 624545631 945763155 145290146 640517370 118771500 747268435 110487849 560373028 488077881 987179410 178198741 630340197 305453611 490372209 374120715 759643520 41142406 621797383 214199476 464193048 8949372 818785736 182667971 733170009 88584052 394548980 810310924 932841184 127725006 294001236 432353720 971339899 158002584 165145456 95022159 360322522 83226209 308080189 20747616 560726299 50098353 721604251 46462713 873966609 100447263 203000502 120108668 638693278 286549194 508992389 343786884 811417996 127096884 268151657 301472854 601400402 239074907 335127561 155322396 561084052 513901298 839816594 504779979 844662385 678550676 746027903 168354202 977689540 70689134 630403937 582417629 934604932 647631197 789400513 291795671 940033959 924923282 969841386 462346535 992525555 237510793 388159734 81537506 816125584 22492502 28730860 397556568 577865098 501410802 797309557 45116966 405005163 119197903 863435966 817496251 836353524 193464231 401027995 66759626 966805345 494612885 607453166 440663099 768954544 30610023 804212809 14080097 967632934 609648948 745540303 42326573 266570830 225752929 830735914 132723292 620928905 822588919 962616747 530497195 962284046 504530585 539550028 357218237 678024129 53574638 833131967 454103273 548383634 478991760 961732726 227685975 698681384 327484517 940371654 111799343 825608412 737079760 757407651 708897028 855041807 63014763 595857517 164483003 239675763 133583694 921692822 394533439 770094617 374450524 859173840 161262429 911325891 187371110 306565604 844061569 899545061 76105047 357449212 470393849 901771929 90708119 487484217 439302053 701800103 481842940 668288824 98220552 390288298 280515831 649799136 219956315 908961720 80825504 370830797 89153559 625853453 76619588 765184693 124082241 129961081 71017253 341395756 333482429 638565190 123042637 631751099 165161119 691487642 80661375 759714674 704975819 955629336 328168840 509150854 157352718 223666290 420680601 632125304 614611810 747869037 381264461 439602176 464218924 677760587 341774650 876667125 147571721 356727106 385473391 906662349 186205184 469691901 365364825 712924456 131463696 132260164 87271816 594903560 422583345 928933049 149286991 506195622 6625031 36763734 16412518 283529419 746562023 844634919 296232075 738108838 232629835 392802310 517219255 553897355 537880127 653968624 548837283 747721710 27792953 777877083 565177259 935023473 3098740 660295323 737106944 821642029 454353762 574302113 35602591 233819314 68494584 277991277 256453236 649897309 411176860 803672149 83474875 239253486 80973098 540104887 328301609 390662106 389659310 887267195 335498895 806129306 153205341 884297678 7439041 892235329 209875616 928497488 80768182 240478291 83926547 959313102 28501665 653744930 139600613 996059420 66326554 644824992 197409831 630232439 275141110 764092413 377421406 900703793 129662319 438901880 104815461 216791432 287508173 577171500 287256274 391393141 598541327 693021025 692412494 692660493 307145588 979926909 178394613 418802520 194312741 689962061 259437104 449721908 548540103 904748268 299848256 700140540 67310977 121159355 189399669 626972427 804197597 908711151 230990685 963574730 47756137 645255407 236335551 841249122 14361292 738472629 10744064 358150555 569852362 818201535 27549909 264608473 104453567 644513297 126534352 195785675 519804546 749817414 47156173 648342713 177436024 878810103 514434331 937612937 138553323 240572508 377938577 422464623 500416155 970894129 135716159 522895466 381044188 733610131 682911073 717961740 911588158 982760654 235100565 995253120 440019899 815870247 27588431 429264583 226972527 746058399 310527810 692187274 390004130 572961241 943815361 956328310 60788666 838952875 824714526 955246861 47511091 834388759 49736985 211294195 211887866 844392808 241909406 580749671 31301587 546971079 165611855 757067122 703468428 881701757 271809177 923204876 334100765 379049935 750547679 997499554 388938484 713670949 71247306 792706821 497223996 635227327 271747129 912286257 197635311 413223704 659102194 778646477 673932841 860209806 624703953 726588097 715947073 734584768 747741929 760573249 250949138 310889785 404465946 605103347 213289932 288544543 442110375 574631059 390331712 534455768 146532598 274964458 298251959 949709741 228266587 535710008 293435793 356064806 376062127 386850139 363884714 605820698 449056574 761733396 521521927 644807413 142214497 809465637 209327625 986666764 581576301 727922076 315564088 426676408 744428735 874039682 710493021 811771586 391738295 970028302 586273748 783466240 365062260 722870959 201688353 507029054 486837389 970249085 107702368 651795394 69590715 404491602 130438724 528733382 464428203 576684840 199063962 241371377 528464710 640142990 373173932 905004900 518046364 904596727 252849870 706614572 540923515 541061073 52503982 711983463 284526157 367322346 605212920 872139928 154650435 627050999 541610208 648311448 84413154 846955328 187115189 411597812 759014938 999822147 27302181 375938855 24780369 458280928 462476746 775784968 16486947 587382093 137532433 619214674 583675421 869513369 470797272 824676354 460966385 894234927 121186499 185751932 194705121 488856220 160821649 170151726 131307146 703492491 3441051 586762628 482701609 601180835 242697065 737257810 675941015 963185752 125110458 801510720 24873176 647359621 837068159 977848771 698167013 887341409 200679583 731802844 479971225 727971275 630274267 856700194 97822916 821853926 758094893 848113118 189797101 402371742 539271260 880223601 803861295 935558516 224105079 425673807 663648225 957376280 618636419 902252873 201641400 458537976 326422045 561997412 151047746 309926661 544395179 860101281 430673311 955204522 571566092 848254656 608003028 877156278 230745571 770889715 228440505 438516517 247408938 821567936 185950600 887702470 454642283 894329282 130409255 377465006 403367263 671894396 434432526 455116168 783103003 918925614 88508421 241360012 162347918 804630214 372509471 908708544 734111046 816341271 576093265 774348567 382186714 438379752 371053342 433763325 311401779 994612641 642485557 761771123 223330673 636006875 342382595 877182644 471924234 479848259 67797457 879264971 564559646 919084722 57867355 765222203 131490877 677677158 885945991 904347130 133413280 869826114 66000806 509149039 365731358 915365066 361023868 610071573 103460182 727880058 416518029 818614393 528714909 590156233 33471072 608080539 3223464 204422649 99920057 135734524 22067915 950117331 205765257 213237085 641249313 832925170 222685549 533090682 545045172 731506326 308060460 770464070 359174552 979490306 134402716 946685500 425291194 518086562 5591906 355394902 488562844 796722121 360219085 936738413 536095903 903824223 583481443 768528739 32362592 457612793 333753434 777661920 2354851 383212269 782111773 888125576 427080146 841501251 293251981 732435950 225061154 376562572 65198922 677474313 73382354 200783899 34869066 850132431 241276321 775751559 454970884 700616134 149094676 180789213 431596548 819725220 622543471 886383259 402896997 994764435 476520501 758783407 745279089 938814915 80507908 299615119 136449776 639114967 777232507 829010891 771945147 776322181 409140598 828702408 39982458 920880793 929356629 980004855 318430319 980404569 384426593 718414173 441627056 971991560 74386365 890627878 218215109 971433851 204896422 706641493 179783668 760221071 676304620 933695430 148440755 580813537 494391165 508418202 845769299 924365801 85294848 410812437 313436634 678497869 80660218 160935026 70255806 103456486 44374287 712042774 132405349 466798705 29001845 887570455 218269313 436693745 398815545 563445619 52254841 266350458 13029273 780322728 596694279 909589838 352981522 992896289 322287 678926684 307510774 581062294 385317276 922017114 90307644 860288185 616778902 950963083 613692065 871277318 303536190 757378742 80930 749220551 295752760 774504953 700997233 830701203 35824799 976772936 172843958 222916358 333054311 333582664 31785667 820065417 320371703 619211880 316072276 339016834 262466924 364339931 604016343 695078282 829946036 964181552 224949181 832508053 397480800 912094140 43402481 409206637 106811620 949186576 173854671 874443320 159711320 198262130 95080891 835811545 447322070 892137523 108466814 406942469 38578734 703344183 10795056 433060443 277937931 304731014 946081917 992124559 555972723 873429254 174659904 908833736 195713485 642220328 728949364 837684523 424626400 867860520 125386895 624637555 186462326 729470494 293458328 531018329 285043320 530861849 377100597 993216376 293855586 755613540 837898723 974562190 702804339 828846481 522644359 745269482 298200285 472270590 337354093 492256728 527191429 619570252 235250929 514089214 169102719 981071516 627122752 865155337 680003096 920234943 56157615 165653332 433219773 871250952 385647496 599818125 612348993 842383157 451039665 620386061 24353370 187312821 1415608 164285246 699576416 937186334 565515510 851669876 217776650 676385059 147172536 707466809 417768254 870367232 307200474 868546221 43347072 476756164 294300771 638751585 560646820 987716308 191283875 883886382 902096628 929307008 599950089 808122076 177231705 219218447 60516432 942612969 371627838 927986839 134165653 392383981 192564357 311529533 41665248 581498632 242518912 354802679 67492025 514916295 315559313 651011616 107666955 786747957 433425517 854337268 28964675 566881338 114153015 303248803 124150630 422381430 512638988 519060103 385816399 751814017 133960174 218177899 710209851 869347665 185238479 543116343 142813681 166955155 659752017 940991343 427125427 728934313 184817949 348312204 433132127 525947394 862120333 880428430 433184013 745004926 260682176 552523682 68471196 78331209 208357326 902987041 250496785 825673347 369998236 626086007 195946476 546655833 200784155 285285404 124768462 453623387 74072358 836922221 300782099 701735259 695368676 958660483 498739551 845536212 32252817 812753185 55053009 530050101 132753277 873988589 573737062 606117488 202288868 736716115 112098191 157311197 515783689 546416284 301407971 651574917 190198917 711774046 690779068 857957112 347586838 645624285 388254182 392572312 697922825 771750755 104788697 765736149 244879935 802165097 852570925 912139444 215291599 306613940 56530242 823321499 197419941 774715626 829798642 846292383 178614479 548830209 526146663 822709275 288035670 810071447 29080156 929710958 662910730 852680680 124581064 652612040 495030272 996947070 318953178 553852962 476071218 700166991 125236340 553211713 184069065 366034602 183890479 752855972 486815246 975048446 700078222 850284490 335842895 873037355 919814381 967379009 118507328 229616861 53277000 799214671 343015748 587816564 28816669 565553419 264838973 486239476 430140207 991507222 781593730 831925059 168204296 502947595 20308496 21730737 691274805 961575870 807320684 937758540 69573719 803666978 166277397 670839080 331200801 761353412 331276739 404565337 16947666 544578121 658547911 723488837 378526972 805739806 571675462 857713581 342412112 470909092 442333195 972843653 392699056 403557270 22368325 564126838 367650572 934633511 135720274 561606091 324878006 432622627 271156377 279286990 299530166 509315471 367369817 787948461 284847107 349902834 2592283 87260743 879707886 886767580 252668881 535260353 350876887 594306469 761284057 790013111 310298911 833401212 108888086 331824361 321311645 323481445 123249247 249114352 113857280 784049612 909891834 961116812 120762511 707780677 308065368 596912920 163784402 422432467 46394297 324082077 171641532 387667005 485442086 962872857 750228965 946388675 95076422 545731411 6836296 257510629 95466770 997000559 319206245 996595755 153121501 274554256 343203844 748841700 216146245 734022699 714810929 728024349 182531440 871891066 707063973 762245554 400562832 770544434 207680213 786250806 197096110 599529585 283119754 547944149 21269243 113613222 146248055 509317554 56561831 211159663 126245094 395805623 780314133 932698781 317120094 973371876 198160426 648834978 144153487 928713434 248345969 550395295 274310179 560056325 12277628 474064830 423445834 491799174 171450497 984718285 465827943 671348862 139758760 551359400 169331907 424508116 275140714 477192976 426435097 766073761 243639524 760927506 161606065 681914252 86079941 566028625 626290930 816059695 539701832 827636162 58634577 914621605 753217779 864580395 18511170 614940554 663253479 676379263 262503285 274730044 862588116 935908401 443830766 662176438 361502546 655672967 265944784 834774851 270337037 729697451 214526803 316845689 117166130 890503927 256855598 273130828 258544075 790261711 544023560 583193748 106408105 574316400 227373775 429721902 600886223 811854522 475430989 678781531 158377337 558460645 36108163 717829349 316103913 825311468 537249619 605869157 347426356 902473845 648462361 957836072 132211904 457337228 18615842 700012717 829434599 863512762 393845696 442543111 352204332 489948678 103123099 903771274 214648570 497182701 88091186 635492029 200635867 308193382 105980501 905732312 640812794 946521368 218888999 238123839 547763696 649786559 2915443 434054942 53032921 838698968 79870982 174261645 165247632 514701718 521454212 935037871 809237930 935925923 398581117 850788630 840515355 959081392 221133662 792102861 20824893 247906856 280663683 943012025 183605880 461933248 271574410 465881665 292181313 409506608 210626795 825752880 215315188 404330639 465801159 783378904 174946973 952160068 313138175 735551352 385383104 535036790 344504198 896027105 132402198 324576775 604873557 802708729 169987392 754127893 691151213 988492976 23301056 781895363 318223752 977005003 122872869 142525240 145210324 476794910 344796039 721974502 846265937 960549286 262452237 626299444 428855627 649346567 398026665 839922816 50459499 455662579 372316613 926327463 10965777 858095307 312185030 617965881 76607108 452374754 98449534 481841988 610010526 731942861 466938003 805545630 212694326 651058800 366660019 757163245 690156535 852831515 223037458 635089122 225886681 727027857 31223731 297434406 773841972 992309221 190768676 340702549 811389956 912367540 410741106 565387077 30828021 854249230 133153969 634115126 647939490 704975021 259441614 839581747 689519835 774157741 76863232 633629535 293015795 990846384 226262801 392846304 208796500 902229830 37970924 581290763 63341049 512931306 396963016 783307378 211559656 537366654 215780234 379781942 26656437 949050432 346144490 495599135 518534887 708756323 305795214 461185333 12113367 672175007 28311942 576733819 159646218 450774742 490020592 557485581 161026600 167994004 92369496 980115943 101851070 847146047 215639705 379094733 275795181 459945958 29373077 868311232 91058345 251156478 613405416 831592968 23510648 146946317 17719029 358969435 586505208 814311209 39082277 485837916 34194953 619035458 269399199 421823253 39272914 736891924 233003277 742953709 16927266 311084605 435758238 596974045 323031227 429124588 730079972 928964685 920094027 964094049 811326050 929829561 97466700 863403521 489054007 504732609 117367828 470243268 388949825 928570941 748378295 991909956 132776917 617578815 444188493 818284275 16336870 321797410 387488737 718375207 187701631 790644936 212886169 419448163 241925788 983801594 390685652 956189750 408853525 460990771 346687337 710900592 490025846 746424068 29965174 400342354 492984382 734722441 735721867 798969042 7731262 512599875 205919110 378827710 482319303 530834851 358580506 852693930 466828373 978635673 724583775 922204761 264544269 934841543 519573344 856563366 597463475 682867659 618727570 803380485 256179794 806125128 195474354 798626589 647644745 888476954 772401398 823830418 139515528 386124742 468595791 702595382 34579465 740483905 406403360 428314190 655506715 938467931 606362143 822705960 640387926 905003776 165999361 684185700 187627025 852788864 34653983 832842186 260653841 786014994 185694784 476206203 124042324 896380870 287211886 515076749 538479765 591117105 209769180 616228129 123329942 811614183 426196526 903239571 361264444 717794701 144232695 848755699 179175864 970113644 105038799 858263145 523050702 886085474 227168916 447696105 294043808 627078607 35495850 891311982 395859482 652964702 319334865 562481945 697933342 790253718 245553249 962100333 87300912 560804963 9090747 943822812 500474573 630270839 826628518 997511129 817457794 935306603 230725053 490464617 349728352 890869254 232416353 248286120 167908359 420417892 416038562 678607058 67213607 904859188 44893704 65893626 182969994 954624223 366791154 720085406 207948012 596327534 208148001 247693207 305554482 592859271 653572779 788175129 242884400 298529379 439746960 943695263 598393221 857948963 134562700 282704392 140786623 783114093 360681145 465403503 131127745 169493561 116995845 408788914 198984965 925794627 31954902 805239104 47083487 189213706 389134992 983716752 438163981 842034927 388124823 708854417 279054564 826620486 120662301 837502427 16827018 661666255 23365866 41725529 688199420 704124397 226637403 994002247 29326673 549341718 720480507 817156363 438093964 796970813 49227371 597761612 678980939 879339226 16597084 427064169 55706691 66467492 765736570 916052879 838368968 968388547 357128647 494725577 855878286 868131399 247817327 741349681 370673723 819195213 496832801 763211018 445625185 847177023 654220931 746800702 69719516 875268136 595372198 728118893 712431725 961343070 38214904 805464555 34758758 423784316 430322461 815667299 59009756 148466038 831658295 996057474 132046493 163340375 647646154 848290196 335876914 766944375 645560727 813022614 242340672 646677199 71420331 329455273 572697651 973050249 308582712 438143272 339572779 485872076 369237395 904659244 166175457 232846348 405650031 677020222 43698108 562584754 269914712 513463901 180579197 234959518 734362193 926408019 235804818 686479000 345509986 782412450 925726128 982449639 27041778 62399262 219586225 452908587 453975025 975159360 260578337 330475533 2938654 531399379 443835177 785989380 36248993 813482968 18605586 212124689 316797661 444102310 297547381 626827845 181398354 652588163 121016270 834829923 373304552 718239567 10334011 177689313 381221463 609336473 475101800 820228135 126137226 934034733 67644683 948994519 690084053 826102107 683387030 722224464 256505421 942630550 745191527 835985200 52527157 443174783 34573094 367134516 793166366 941543609 44619193 558888444 697774854 793325642 547865871 848052600 89037354 509134777 151622939 943700383 505018609 647073954 467765887 565730818 535161700 740149806 411305733 885074444 419083600 657240434 8409097 532174539 412325532 618732553 152822646 674080174 416322190 821616973 257723888 838861202 225288986 577764605 445664433 775117216 261450829 418020680 390328551 397719586 264538369 676491543 26232569 61256954 825404645 943136888 361847078 930162743 641740084 824299999 478606277 741542546 385745722 635240221 525286035 978567252 201683636 597545461 256447134 854475047 465066767 705379156 172684917 570094873 436262907 642344633 601540741 941678329 312296547 937818803 482946102 729060213 60894037 444147441 123739930 207609246 517115636 533663689 714105981 949415573 354162051 795888934 703920245 956439855 544965759 562547424 195584218 583407927 291209790 513174559 846908153 925162354 241925809 524558601 601509154 611137352 585282530 630395452 225744334 282110043 263732397 676318612 774252865 928128792 569166031 935026445 171428306 218213416 246788536 722439277 802529454 995907812 230394071 534945004 647032238 787357756 135567298 524378248 10261508 969950269 264310227 934091616 705298252 747928248 322258563 768886731 83380451 840185637 122606975 182013510 152286045 254643176 261627551 744359145 483896499 568491603 235163666 967941690 32831051 924442716 594937580 984299800 368478818 562816618 626608153 776802234 429170755 774532053 395779773 462666442 212515706 943562220 462965590 934031682 807412536 818118217 560149259 868180871 78908160 511003481 26664054 178663587 897273522 922354446 275808753 672231784 413059566 508532146 873412280 953640013 49046533 205744043 316947063 830090834 77973055 155403375 570839444 808562866 215425457 547136876 398514822 674032386 331931277 389253861 309245390 862970417 204949526 723297723 226434076 462348505 135713473 431322763 400596953 471562672 664153865 885804931 392504858 775562250 72828018 469680038 456164306 525083556 253377648 509006228 6776270 157980439 209898735 462837821 552403529 825884743 177712701 184096174 71227723 868140913 369340395 442053223 183194093 678137066 298957576 868549854 756063306 765047709 163957612 326487395 363780117 627554930 423329527 802512288 619371604 943458824 147282918 800415352 213623295 839495953 5097426 203623107 187651285 671483891 131334937 880949530 12371717 587635480 611477517 868474210 785997599 935338099 221574083 533091895 123587600 457230976 250150598 598387177 84854206 991257113 141783116 985358473 462826636 590720245 518349980 532464694 294820405 377239608 82736626 255703152 112734024 730542587 369662155 708381574 429283115 657757111 502362982 526782541 405695344 491128048 27937959 424202742 387150100 449569127 593362664 902760302 77164662 996567587 563515896 621580067 176638353 924281766 176102055 544776870 107776489 389857791 45933672 68406725 261520150 883647924 325302335 340741589 380276762 557783397 88898937 742463665 260544476 633659847 438677793 514203773 441325751 774203921 175880656 835971729 323468376 459943823 600420895 791827258 497607860 715000239 384060059 491127680 351265466 391160251 365044678 590261857 154878292 456806360 112703670 445094114 639651715 914851935 87992560 959686772 420244544 462288628 267805852 803658866 88445039 748554508 328715997 739239175 797837680 904139092 13624924 432990035 337311220 907854419 116464962 634308528 249131067 800316708 627584968 856616664 317060198 354066845 282006627 760410352 98056009 162220916 599272007 692199356 37812088 92294316 54237704 505642553 215536659 628752319 52099764 764689211 588399502 970002252 482722218 876806344 49595925 702449073 105850102 305190525 389607150 622628123 852412386 978947375 93150636 398905166 68118230 534894275 114521664 735622671 188886355 334944109 162753732 587736903 24662554 127008323 366490169 548319688 358537015 589640550 28256714 631293694 167868193 547615897 741364443 958612308 137020688 804192810 495651976 663786164 634008094 887816833 358053455 696040782 532299943 665186557 383183926 452842098 382294717 470619447 610062622 870979756 91305945 210349191 624174005 740044497 163021765 519881171 517019833 984110385 697492817 827018517 118084925 815971403 466947414 966665228 404145256 450483076 377238092 833003489 113995089 457237318 252806247 310322621 9981013 461281568 421619019 557225300 600700072 752416558 75295413 221933551 292515561 976460794 766134429 790088580 38275064 428922789 251865732 722663966 527802524 792128945 382715259 800507410 763540567 817929000 110287930 781717916 374975697 928512942 189437123 993838710 555914319 665330936 698813054 961945714 308685415 658431896 620374238 662209809 291791082 463070474 237775793 782334695 338221836 750520064 104337992 642730412 205228033 575333057 97934412 318881312 477904258 600478745 407885842 570433521 605937227 639253974 148785146 478225932 306542231 840618434 342105184 618139631 558744069 927595191 66223501 713080935 333121326 475010687 512108780 990026906 109448590 454335718 19856762 725456710 569409783 797293244 286325832 898377089 455295924 851034543 260534150 564637280 789312857 988238059 399348021 407537792 126587201 491314074 355050901 453607244 314779074 388974120 234556416 551017311 139983205 540925184 79622844 427643749 509262971 923446386 770447142 780480044 98014274 562496643 305986710 388550517 379388274 952717528 331172080 364651679 160167320 890796890 244818675 580015886 20132831 964905176 204422256 978546215 488231456 623244030 208256956 842863517 77908296 508345946 521128553 863638000 627709554 645454147 467610931 748388657 467405529 611560792 401573172 432238095 339724974 701705640 728113414 935411812 83179178 507710870 736482811 902405950 179172409 384165027 148608955 432608751 720536422 964392448 266982791 558108942 8951390 869188091 243518187 573343090 532354663 837406602 443240712 644008484 205932257 468274999 271500822 737744282 61379275 836517659 513526924 800536254 476891738 881048126 693057291 854653635 20616820 985939856 439754145 612721426 246771418 380027322 473085703 526290637 132079671 806556296 693968751 904474675 139986523 618171300 132716615 834009236 261346133 979341298 266660495 516141883 5042730 664305366 462595730 706842722 681816737 905902046 131717997 796533227 236723406 995398701 690188657 864432307 26090439 462723648 318980827 499750676 719226310 759930307 307226110 362249072 489292878 629213926 120051151 366749661 782600374 820996806 291091578 767798092 205053697 611847442 460276686 985477715 268698883 981710042 190117202 526086606 56971987 169219992 367199977 444231283 51239773 523585426 34681307 910005637 243844629 252302500 1046769 632178157 336124803 528635815 102183368 348452255 99062206 968661365 606463573 661961295 571186045 662624965 587733580 923406274 162831145 633969565 706253334 896115725 83446444 690386804 214281457 299113522 68991769 424681729 2260588 780061912 185590197 915307567 20019624 125355207 247428091 395683983 210776644 226183979 254636187 976235086 422110499 748963213 269770209 915781964 147614690 827122840 125957089 684806112 487284764 514321540 495387138 596557263 240813355 361184915 99932459 158584843 266924835 892210379 125102810 372286241 239584288 518300388 77868319 454675499 42358084 448715005 15373306 175130096 587750096 673928385 110115221 679137952 633571780 732394614 865891264 967109586 471404625 629615821 528103328 874337226 223374827 629880964 624134045 872868869 163831465 214273082 36686473 847929866 277794700 445493989 592933248 660968192 604959189 738305716 740491137 799520528 19142470 95782018 34118682 843830062 12835852 787047720 334527224 753625477 583231817 657878954 11717232 174674017 460324131 917419870 68473632 152707979 141903649 806267208 451450777 813030673 425925100 659045782 116682773 148104079 287044949 961676359 6049393 468831142 403664881 857507795 481513060 511921860 553662570 581785480 486950579 764683363 190957774 493005180 292702030 667321828 34776954 440184914 232456910 585565838 593924788 627391964 485478187 818916810 187107684 304592412 138801201 562052392 238244515 772495080 107203158 782302083 4464826 46485925 804357147 835024662 190938723 216186946 14027984 946341809 135769904 183711361 125521125 710285533 474057646 529139476 47514279 713414942 558224788 708463136 253370894 711566740 399838382 443940496 106119601 875241478 122973447 158741916 321403143 914665240 456389590 732673303 105371094 524622541 142229510 883246501 103678311 578386647 384515020 598295887 125731212 560040573 24987745 70159762 660207504 823202349 153393463 594828629 235487924 518879472 131174659 451061403 243623208 922876138 698706616 820737473 255026086 543805629 267327433 552182008 831069594 898738642 92133727 333803067 618180183 868512028 564761211 651917809 12469531 488758418 139291736 270141120 236673762 916679762 587943108 982753509 886320261 908983539 365240425 913402669 220018931 811016524 333458060 515182058 502296358 759309304 107959931 622288312 85338514 869394646 61510859 597138432 28207549 723721714 791748138 791887191 324982023 534642352 482954310 668705105 82615973 260945228 456531532 806483006 473764535 834441912 665345826 967929505 610140062 970442690 305659968 855774101 467809870 499465402 314401950 337771153 118884111 896578085 220585374 290133693 137480164 669731154 236644582 410112715 689061699 953168918 322387167 389457842 205006618 889824198 13802187 437174607 525979302 975937232 125632368 511219698 601338615 601751348 68069955 861721326 131450520 523323728 165374334 949828022 806482882 883327916 333610449 356851942 79323866 388051947 99679689 721862935 119073390 783544270 741561459 899542000 72665616 155353290 769627687 774975636 234582396 551714018 117354395 276495177 16591120 261935007 305607166 761971090 41263952 352435079 147579118 684583925 274785351 536813368 812447950 892331223 334271476 426086124 357340020 815262347 444602050 840275839 686898958 910381221 194739325 542356077 26069602 332220782 137128423 314244283 28503879 335482536 558826769 798509712 251979615 275429255 266988916 406959766 126564753 877979507 35596879 960698517 280207339 688472029 509035904 616696084 906357292 938671852 135837711 602254528 494453411 914492245 892707708 906978460 397609707 728825817 209834713 874970074 243571872 460658762 156757374 648187299 152857872 282234637 628709037 797091180 24516035 339503438 166731108 851060373 57868766 366605264 114461497 473857162 469626884 994216143 715987303 968291890 324456000 592659261 311380709 875043271 159335044 666865931 659500673 871997496 593399053 957201654 192006090 772160825 70998224 258231759 540240716 727904123 185779195 738854714 254188407 905569215 534387181 814855781 883330722 989560391 826163812 947822875 215045675 433366712 222810353 539402238 708375464 878365012 312366353 499839411 396447367 495029086 127302722 694125429 131926393 962752797 441952233 663207798 730487574 813730360 14030535 110256922 714400491 754906394 279342620 758401291 43631640 965027919 114988693 721550087 299959239 565463430 897061619 929547633 623731470 663930533 486379172 813606509 433278192 555985982 148581808 356773164 551234657 739550601 519378013 931559170 138060177 170450572 2510516 804143638 242925046 632318731 877097553 993285453 691279042 908281990 50924491 270352407 523879142 897603640 170672037 642839096 147686667 962364554 333904168 383109415 419883994 589124042 284731242 995147451 473806605 509898131 650412132 867120467 761806678 921445592 299555822 936277896 935802051 975624445 155379003 772221687 668393002 700759394 359964574 768769321 318857254 604268765 523693204 669075651 16346814 370285578 639033694 713329833 112508089 968292725 271734439 849388682 370789447 925441503 29454094 415258129 841048589 968132531 12179153 402659442 533288361 662087284 126140609 735438893 40837924 569134281 521130632 568081153 376535934 951472354 605783848 729496868 282114001 308187092 104945467 424595516 361551941 764818068 780842881 924015496 253016591 305194875 24277468 295002396 253676652 663221820 628141667 955710089 364788245 697480426 248958028 522506533 771975613 795546477 467394280 548451277 630598237 945526968 256919310 374367663 397270767 440475647 176390424 736167941 388142998 957842438 36547510 448755322 226326558 841622688 582156776 612697066 274614240 284931642 28235625 495602733 472776314 872011299 222829442 362634490 176932538 225126931 403434095 548392899 296093692 514933960 4248390 609778807 242450056 324642080 72136972 939709619 7142501 100960831 205167765 637690773 229942645 609686502 61470635 246242248 78822428 165407180 49190477 198929158 528426992 966229084 154099586 547447670 125636639 768707922 565194125 830106932 344879726 629356331 470075871 587563924 638189901 912148236 432857733 767043695 677390459 988992410 138077859 332744156 373329707 838988743 72375707 651306183 204502394 696993240 151124591 330091713 202844873 941127934 143609464 914441220 240503114 438731079 133102276 146165838 464329186 654616757 413348969 758500417 446699589 575325584 258150726 422544865 589381315 999661722 490815883 499033023 84740055 414401272 27605369 758585204 673087743 994385484 129861088 809282263 667390019 764894636 641778100 736697762 639527084 968430879 767925257 771061812 765510893 856349292 496822681 828402231 16401339 180637634 392059248 801533366 61596176 604079583 264747506 414507339 591338697 636967028 246481390 385366979 577184169 833728153 510794176 822836024 326207987 932888873 298386987 622641643 227841936 765775890 56190198 524859618 718575693 987557142 502754632 820119614 657212907 659924778 121739129 780564907 23531716 64903888 275990940 958317450 313097668 529258644 214817943 844333326 580967079 804086467 369871934 666377946 104014892 303972020 304090891 570928008 82917516 897771337 490372142 977907525 252133558 540881959 478017379 723721023 413579828 837472717 19154813 477267401 243242732 785108295 126461533 636022434 51572070 630470375 86628420 188505942 897069991 905654745 808794064 875146878 167383012 732412272 187323978 498458660 611702563 838905847 37176335 285883802 592511542 872460978 400776133 597021686 158793119 495207024 114983443 879719315 118123050 443180265 161463963 321543636 769071897 926020106 339670827 411040805 15953930 550733067 523801045 791229341 189029864 321763823 464897952 547816329 22496696 176794291 536620190 843662343 412749309 518546273 74239416 292355191 227284556 620882295 28860677 929251034 471545042 537434325 621881901 624473767 261643030 686882548 553698921 957059975 375339325 781903643 240301532 543152682 51772745 250050582 184222503 314662520 412690119 857823494 617165487 822169464 391468162 488049052 851338200 870572755 339848778 753711059 474083243 921741415 313863492 376721556 3602235 731451284 104540768 770241463 135914051 811461594 633069433 811213533 3403951 398850568 283392998 452089432 307155311 976569763 237054887 591189235 251743931 957129299 433758847 919714130 150935442 285245348 51298599 471856823 182539654 975686123 84510901 253320978 280890248 877985723 242415488 567498005 194862619 923375967 114834309 812403784 196328257 613323310 615491372 938360379 421702785 581102391 280675599 755844153 500446343 747165149 902769581 955477129 287155088 591964961 381793084 581464345 584116519 772624672 20978140 566033728 85501145 752011023 649530735 948004701 110023730 888341889 215528681 495159938 866734744 875201082 602082469 943542421 25716490 101786545 41339459 300070505 5987866 597297094 422844453 605910974 167061281 383907019 123453631 585244899 229763363 627515479 457164076 495020700 42324448 172190058 327937283 976268868 707933592 867118950 80985961 657300019 49563642 901593941 813357667 931676007 80531604 277090098 361207679 614185807 107902941 642785811 271745308 309696635 688169511 704444921 136547069 651209094 148827575 470782947 247719633 335467390 354669262 753836934 138956170 903170831 407146616 960939447 249005797 676491496 182937484 914986520 55527580 640323082 257671534 626122907 262902336 820126946 579689780 647536145 422204030 684229754 13390493 343221859 520785358 786108873 745633608 985077280 441628626 726498242 556842982 741477240 166051583 189793966 765315359 767595797 527751804 603364541 160591695 827533206 839345224 956627417 213003388 399052366 366656928 648551099 445187341 928375493 411155873 766001473 165365086 856197858 394013696 888816170 112533827 507029143 684919045 835658006 191577465 969268014 441755975 532380738 627143670 793526065 304063031 565895925 119612053 794205554 365594858 586890543 228142972 760116194 314966262 989394620 177549360 543525167 129657060 316088904 748116898 919411447 362547310 656954894 17455936 471453799 126784091 217418871 241923912 574185254 425508683 708633929 57659899 843449556 757086819 958458990 424729270 808307760 984932412 985260033 55448273 67965933 162648672 349776710 391722883 804096516 842687098 940271989 706785763 851648114 272116717 310502810 67802188 957500930 401335887 616482063 632632971 781101023 429293850 457290824 172098552 607347891 341470502 931254604 295423342 511440225 120360366 349045294 435303344 569151196 418160218 835175412 241177786 260978319 77748456 177365867 7518885 484077231 360823375 790412795 483669256 919555986 132404895 603546942 301575636 629901067 195934253 639267533 452780900 667450901 243613147 458661485 238672530 770360816 617775904 753488901 540963837 698189209 891518826 891523504 425072705 900261317 82119384 456369655 91142807 697385985 380424329 532301829 420234310 942688877 786799143 900388362 59790181 561892794 357651552 821371966 392875560 479898136 522406864 806388462 496436726 620483022 306604951 572449886 139388536 317121387 613772894 970166208 108395076 478787536 35155441 244804873 67749024 706402984 217622003 563558719 694212530 948537320 422467966 494284107 311508482 989129616 645612336 855485926 614689411 887637585 622322147 988122711 538928619 947082867 94253375 608657628 155649661 831724989 238556403 913166310 72372951 112261607 716760973 761864509 399419193 910649859 699597300 721521657 104536038 201189465 845377301 895270864 389178536 454075545 176175676 207224118 306160654 452712918 448337951 583564360 345337493 411454997 363597551 416446514 265133711 860773531 455104771 864342909 719253739 802776289 114972462 691464758 794075222 997866669 191749393 704777611 145481149 971562046 77530320 832450451 493941147 718061889 380933092 839531382 971485243 993229376 265069225 455188051 108090168 629884000 97869244 245514202 34650946 433957453 532110420 975193967 302388755 560164481 719332101 846303323 226832864 994374027 342114264 804324398 723010149 782494780 158592047 379038931 477252379 581889063 273714510 757950334 552343128 954348726 3685683 718290637 886937411 988312311 288590504 816429355 176290421 297389609 13207971 983717486 527390017 767661362 77020478 447527760 172333735 193472996 418603 236291324 251684834 527137827 698435810 991572556 366036946 397650872 373808987 748631571 444644249 511797863 747249293 943391499 62209011 960386772 55569340 597786761 104413304 813226739 298944574 903390250 64728926 751716743 30078140 512181388 516207419 941355789 578259910 863322160 654563597 946024947 360834794 923938142 143201295 987819132 47938652 746588402 76380256 514248525 567276849 969467421 17355687 68142463 497670839 740749440 515491226 588728411 251148144 977645100 484041896 530271322 321006365 832241168 140204540 577965666 210061500 301437937 476499968 812414460 419809787 446578797 90095520 297700931 275458437 283050924 790918069 898823225 621029938 716388003 127294924 427769645 503867101 881131830 18295567 196053654 208979765 413327587 238271986 631910551 872701807 918924805 592484689 865725595 184918350 818280772 246129354 480426032 510719878 778732585 194324262 461021531 295984057 567328924 406082390 421424079 113912522 221928842 459131528 948724371 778416755 901099967 541798365 958067586 57159238 446743783 493209029 981622950 285784894 975079791 512361284 957600560 401006094 836460335 28215298 932780824 433958957 697240791 715718346 898937821 177034610 383094859 142617523 190868754 164734395 164793458 473839291 763739129 131156428 234368851 27053537 430893348 89651128 704044062 182684326 645203497 683921461 722351575 96995190 171690739 67879575 155303117 324895181 357977559 338202002 756137173 56895207 84536980 269382082 543197492 276077796 918060146 125618440 724656448 283395276 898963181 14153006 956620594 469152633 900681992 144313545 172603962 57643109 429479990 669998742 935959963 49070561 681384791 138170933 951774698 92656847 118811585 396746744 877210295 176918516 706383894 600055061 687999820 296106287 471058129 42984129 287332885 18623783 972736464 423498224 674901200 67927448 397435061 45561961 688776949 496947511 622045509 435473364 788301212 45800421 92590823 553052498 695518817 37086845 134349328 226526799 470481034 340988245 958120056 471617127 848126100 32174050 64243635 856591099 899695010 479197692 967418782 245218108 711864282 310615949 666382317 422248771 955879251 740617266 952218943 445089991 591780047 829360887 840559006 305284986 931141212 733683289 917205040 283610913 361590187 23834048 944017659 252163146 841623900 642032857 999668794 22439662 406600142 432203755 726870604 600234271 746237290 165263893 788315938 742304024 811682060 341531262 362366031 852428567 888978976 116057321 155631403 358653380 903522229 130488935 345912916 375910984 520449884 60351419 546941192 483198733 847169246 220790002 224404672 102706485 921548484 521197940 635240925 462523851 822048404 359560276 740201354 242887541 405440545 266397951 580669641 771337174 882593434 355401252 521900225 148888230 803123057 551109567 983029609 434905821 953948315 208971012 505445852 307783041 983049418 69180982 212735538 195442657 678795681 158347271 659183452 411231387 501206180 317557839 891826472 124979188 176711777 81937685 415860071 720502411 992539304 381986084 920344858 375115343 421003806 575297928 728174116 65971228 650711686 201284328 791382707 230216992 655789281 19832659 312288671 168141808 570021197 915861478 919846530 149984399 324496240 426438009 860426310 47108632 181802708 413369827 757032593 266969948 656667057 641783443 987873644 261828744 389449803 44929355 201435196 55655415 439896721 304316750 738379721 157900554 974116161 240128397 328302802 789816303 904080278 423341559 891934443 198354810 623612011 255917824 904798902 280679508 753713023 812496829 972722423 413903410 820408890 212568930 636514775 38212239 47598185 214864814 865740458 219115847 487850139 505910359 678586428 6067049 626809288 122881210 486158425 259724067 567019357 468948693 622334349 320197960 401539884 685951277 982156659 702372269 968796682 427192215 915670438 495487574 963755289 679110328 712330619 486210931 924004800 346192076 943122410 687462145 760913285 527149069 788684650 200292463 659421540 494071187 500075200 36395102 589884540 263226997 406027548 59733326 347170660 393407976 828781741 171531778 404654908 34118025 277512339 378316679 890337948 417299440 704191491 767360452 801549181 328792924 709733584 553174114 573490252 27614546 684392073 443479150 982065082 198959603 982766425 671585670 849101966 205732255 659120665 705419576 954330297 188064091 556151078 490300021 808356317 243631610 830046190 692284028 991705047 786506066 973927924 83327448 383675582 479963708 519673479 168482794 686407632 469089287 563542664 497349319 637417862 643723457 959211735 729862595 974400650 712827534 999085369 375479297 663596566 107058704 826031520 213224869 883950402 144026718 982552437 187085694 761402192 445505552 524026683 669036564 759198735 371667261 774230225 478186909 710323942 821431332 941329531 561208665 713498609 222029348 269996839 181930345 517430808 827715936 920922494 25804834 860545346 8701315 686672725 68017061 911693733 265142689 266798476 513734604 836553825 254689132 404540938 661282373 804606290 360866360 493867893 219714080 763857148 80775190 538647117 618012313 790520512 17828752 698749159 162477599 847137346 334427126 431610460 108608809 788970130 35955285 174022725 699887072 999706621 608581913 918814549 315255741 876067681 19545843 100874282 241716350 597068211 502410126 851290574 354010948 888476889 216417094 379931835 236058189 444269925 904774159 908247592 654782382 807021273 468929427 995980201 293339689 890690372 536421948 671881046 208579296 413437321 157220554 662385908 636354085 964741125 244307170 622056857 558959390 933900261 485979694 569601603 352546305 575218019 119431848 272306379 818934011 847163093 637715625 933081226 393200905 398088009 30641434 551578207 270982641 400493454 89375975 121704692 15203713 151143777 361282370 688521146 748385318 806554838 376511316 940358119 14443296 299567002 58104227 751563594 99164580 892841157 515790714 658487967 210201937 826711781 818777601 828554668 948121247 961473408 235468653 333427912 24288312 539047733 133484932 539602580 59361040 475764895 65250428 726677195 126843135 177068590 53814864 691286577 397040897 567884771 110014162 765354285 161159255 886836133 389887605 676404544 631897659 665307268 767977216 990194181 421810904 897286207 449190463 911798712 515529165 696027822 109242669 615779019 24790673 773161186 352721470 858394054 363525622 780063891 516834034 639021437 137531016 454244408 48459618 979178157 618310399 852225683 182025798 842155189 93178674 140627760 380094305 560335202 724342635 913954316 23108413 827778791 93768956 842238842 354323512 644467212 235586628 793913873 475629457 912159704 626657477 877903887 81183169 603361646 125867522 328380793 317475108 455661855 437415847 947379298 554485666 877117941 206693473 517622290 81466984 270440632 249598744 263172929 308995159 492496304 304263228 452524996 17064720 909766999 287180447 845996582 501346320 865621620 405892461 830265773 91506786 961623833 85202233 653584583 922017988 967791300 140529893 811897105 564345290 617138664 588252917 797772419 204607634 613192310 588985351 888412403 68948481 277091674 237214579 650737378 176178130 740827038 107860629 793086260 448219257 460084806 399218613 900741821 225515955 830232305 321425361 383894125 104649141 623052648 410757650 541087572 64130800 431019023 111263940 623788197 63032764 535085041 11218132 259521707 152817634 747241586 412913915 826988443 332950245 814086586 271549209 685046697 376627583 956006769 696624735 807826405 534126502 861474932 600395051 820781763 389975358 404908377 197760312 319738870 742036693 817536618 375600767 721273592 630023660 765019032 316790303 431216935 633246653 754751848 634080234 696494243 727898252 862213854 514587970 571347828 364472074 482890448 766304496 972583715 14166594 313158708 25642882 134061917 327430137 580436336 817754579 966666710 255173616 385860700 282382437 536488693 33641777 746744736 685336706 818425890 474247078 876606816 354422629 665481110 98926195 580035220 464598300 618624502 213594881 927476025 597302991 776165883 635131620 736736538 285549934 435231049 141496366 710654403 731522853 998528998 386461191 993953686 713556263 740580076 702527062 990617948 258798221 764476327 233171332 960099646 606606757 910513078 956642946 981973748 271811482 856050784 152700733 580584714 75467478 120197287 337783951 626076195 280531737 907295532 145563921 884701929 333966211 655798683 689906631 853089676 32370034 186263237 592179351 904557325 461247878 795197462 431065715 751536199 150152771 180744936 490869548 542425815 162834032 495311261 319271540 485066833 715944633 989615864 213646827 543050726 178423628 910319860 583338893 729123128 10801983 556726613 591403543 631313062 96266553 511634047 346932199 751285411 269057990 415230480 19819121 307812861 234778971 373008217 257447932 405530456 514892480 946874094 358241684 888494576 566703082 839570240 687251230 874170307 659411068 739728661 61647527 646392305 33747294 156272746 188721116 783931015 690479926 716186098 322610004 873241572 531066834 651733794 409005500 613902283 413467566 590355366 860175966 860924047 153076925 527434510 286677048 897550648 596679559 922017192 24087961 419597980 881839013 954952061 32699063 665484035 550799007 793604204 606559640 773397490 373875478 528530803 410091298 580555864 31035206 798083115 139043313 238558314 822294668 889049271 424663836 759619870 816799261 887572487 688161574 928104682 63255626 97142022 805044848 971331214 176482690 308123034 490767128 853571055 78572502 254337167 479627162 934660009 337898511 575872893 373450930 632784615 514866810 645840501 314239561 719965106 569879564 863429842 24946965 454506497 178858437 839023440 59663232 980919058 30530908 714390615 96261008 114206006 397794220 620357128 383184898 728223724 714356438 906393616 387680953 992311855 390469850 841415817 202916529 816912055 380786072 498942703 37337849 717136571 534921177 970585492 779343778 814771252 367696081 989952016 600190441 881499760 124819205 468707797 466972128 903714977 616717864 891209549 492099995 641949797 421662568 863852031 956190268 995169267 547451435 608583634 44966848 392747273 585900472 995912402 365851207 844820437 280587411 664380632 249782670 546783548 148006507 307675655 7284048 88320425 642616282 682613519 120501651 732501888 207717828 298532670 298816463 830453287 50894081 894161878 331242562 953349228 708874402 836487224 216714702 467658213 207628811 479470533 875723 909392590 379048148 605750650 588673708 648634529 677878565 969849986 655592082 734106937 229766919 447052647 99432361 571290031 271136371 293108722 68349758 944194297 473797275 995542370 248377785 564594471 192132833 706928233 520197970 768431726 436480185 782270402 295605956 777026468 30116605 514408660 100053923 861994663 327781671 642392565 116317923 690641930 204755526 665945703 641331396 743467750 27194976 175079279 389422585 717818088 642220256 702325222 511877794 680624655 55121760 696740570 642897970 890640639 554225130 588539988 328080691 643992820 49835823 659899787 603647518 888009762 48665994 746478566 280417723 423492623 363712455 525869982 507593928 572419618 418106501 468592998 175202911 717308660 587126701 968969052 209725615 827624660 375889488 929201964 217747248 631848003 432471311 650934557 453470005 497862561 21928715 293932568 92487502 323609474 419056311 651034963 113605637 487832355 339075042 430581304 1688370 645344728 51622498 475133239 115010339 629309969 432057706 603215208 381249318 743774868 367498433 428735944 419662058 760213573 211467417 271978334 310954918 908511687 602081496 786248038 278150779 536790856 127464468 302511956 356155427 803954314 505381524 803654723 164454903 400449308 251155377 659448208 579959861 955876037 270593536 279621160 326401381 333474393 645371354 949810936 383203681 559870569 794723784 963617528 55963891 451965154 333599656 926514686 91864319 518915728 170497947 535063370 17118794 446485915 718699570 952529485 315906015 901421264 602996793 667932507 242466976 517866833 127476250 152761915 677941739 895667872 622315481 924146089 185119393 527137235 303538461 753875518 579443514 766981950 247922102 926106729 278588416 687688549 506491494 774807445 831683788 872467965 49042028 386176546 377556714 545454146 60504152 223427966 251515462 714847614 221452447 253043727 60768934 387822857 553534056 789182558 178581294 936699260 296050277 843728305 924814994 988871351 654173726 814140351 133872089 782650073 27065211 338324888 898798773 972243226 144200636 371858601 166988779 298995232 181921109 640389205 33817764 180863718 711167599 773293167 283487175 309511958 486265727 784805146 116735885 314078387 22074085 566572831 707413049 886455312 98649916 826917657 107605971 222138969 137921282 140220102 34806884 175261442 389325175 500943512 179377833 803389529 221590672 291497411 32873044 369691120 598849117 761102412 860021184 992365358 177475167 556183208 495371139 564117864 159127264 628434146 176920100 762396527 337271626 775954485 365973385 938197200 281712506 584730935 571294220 876173569 262101529 313747570 52142467 976634373 354417190 901551963 222381242 232500789 54844874 485817196 354646837 918137137 232373359 399534476 112459909 418883778 191494160 418622386 65893754 947855202 36753610 940729296 32161303 971004800 587811544 735339983 419605221 912502500 63955292 370205753 183007478 221614309 35299319 892779937 438908388 770624545 795279502 898914125 530246545 853492214 640627754 811640404 28058849 271087743 518679846 845393641 465734972 959985995 613436265 664063251 145286771 963057966 602988108 707644741 422853520 933796525 168442708 961552279 124916246 721060210 348120769 597630644 465672832 745769479 274479430 897303831 613436455 613819815 120342355 149077048 354183092 547965188 728370452 729879687 65245212 605396997 536361342 651935192 163315244 990943343 694894164 991877716 69963574 264077043 65362622 942767193 81155654 937709359 275735434 609662003 141820836 695609572 622764104 762692217 791309800 879996185 381177072 733264220 58527992 169679066 184796556 936551286 163238375 754251916 172393716 991951114 657897356 680839183 503138386 887121903 361663390 781770713 796729527 957480190 254613132 411064538 450693134 834355086 143651915 874126052 727424143 847958012 403169441 911493398 951129800 966929182 828410307 853390198 453732998 574609484 567825022 883072133 489423089 815583167 27965809 917857591 108676154 380349146 6618843 36123104 216133841 357689453 708890073 934374190 249436283 440660119 258768138 277052733 32277612 657590051 383087686 427847957 38643088 189435191 240462225 940332148 453476928 916637463 95047086 550396273 15140209 819817970 401366382 421860578 166029365 760739536 880008603 946136492 234771105 816613806 62319801 186128315 560962535 830836440 325244710 955452952 194892168 213969577 476645904 693789099 510611430 837732219 117819615 815496970 126784883 423820907 8736967 564833693 106841294 655146165 722523682 854142081 356342554 457133649 220036189 751768139 297062289 974203615 407959468 511388819 957707866 969326790 136703987 366109122 26996377 896680089 256443966 271145933 688747973 994815162 99128037 851342286 220516675 417945151 12541962 685607614 675426593 745287714 155288535 377485292 408660821 585923972 60805072 235312612 300177895 970604150 6827745 58541595 94074268 939840455 242062573 702523029 581397809 935313861 470037026 494424908 342756537 810379342 114009621 471027017 175629596 577869908 205788990 647904481 429024406 930354636 518025356 593302878 231759075 322697090 508241319 927503723 241816503 883987987 103507840 810143428 659711335 691887169 96112 985064652 236216153 694042868 161120422 943449689 246639830 448915050 82082701 969774849 793195072 989420144 635500767 799845958 69172990 766600051 503621574 687280937 206062931 409066271 85801549 967731440 35870518 913073534 272850764 846853108 448616561 822434901 488065349 521608444 160998059 752403983 386985251 921735221 167608624 177534062 359896711 721916446 111439609 703835766 420138112 569121159 658862135 883910245 140069034 402790057 657476160 676522675 29984343 839761853 1587933 436394818 279177363 917188128 126004131 487581692 74660161 810688509 21785048 187902566 229880732 544798720 12361019 497319884 788765181 825740099 24955784 888222781 282933405 755235784 845763469 929219942 778609642 956200157 641669028 688575894 67633030 947153490 17244578 39271620 305379215 764068589 394670142 662333341 20224542 877940763 373622963 922194405 614446826 682513683 66387698 557890478 139936785 879267381 185059921 280714667 345940165 781769758 81562729 531277002 87760236 618891458 640200963 641003065 48369194 95999893 790967659 852830609 641715581 687956773 119784846 462446764 551802750 697183641 270027292 558938107 116108176 396317234 355009260 566321185 105044449 906648202 79545691 371286273 7125825 449421547 19515208 873420226 700473071 879721540 306340190 973993722 529790419 558983712 217266171 607120319 711243593 788784790 538640132 635878732 188002764 484128726 443933926 812179704 426908056 489058622 348077151 738500323 262374272 471249854 499144407 854901656 97585005 631098380 127972763 696115785 346959055 762130035 870925735 976240634 22640093 877436737 115275180 252064760 207424282 652814983 347292978 711231146 350611149 503650633 547284743 983132320 221834694 876742402 675185624 691646187 288168774 664579428 536816433 848605338 76515823 709583531 499168508 720063282 58865540 324571282 139285470 770374088 794700420 822394608 102891400 955987369 422001797 600179984 880141340 903688043 220213921 412295303 395996845 594458215 413303660 961058282 646249169 822751904 79836330 86557017 485500751 608044298 145137417 914541176 767713611 890086105 616227692 967975517 171862999 658696676 18219672 79433372 175865220 675122320 40160427 480647178 574583533 603086908 135340209 667007704 580037397 954323291 114208021 237012325 387942062 405626915 505270823 620359272 548603205 929509081 226338935 321792206 788016652 795931652 632955805 914224815 56978685 759127998 169527676 444286270 80805397 651400814 254949489 755966801 787346593 951040764 133242859 638418696 581878173 616665439 561569537 711574759 2338768 669746432 243301626 739142284 288379797 321479404 754450080 936126990 830643385 872608101 821305873 842622060 528598606 658316042 183200637 368623231 16369225 351987128 176078184 210185204 603333657 658806752 556545239 830875097 890770450 959031453 742996729 857280294 776162404 861556146 109918153 201872346 286258245 672902867 100311468 941682830 365265740 499495500 76816385 607520420 876064920 930626376 812309627 873835806 402069041 539093361 208027295 923250399 268757730 508146563 542873897 708622455 112539925 203200630 200765277 792147344 730610907 873213154 478400013 780806684 396071524 516453253 11718135 613681587 358633292 882197610 7923487 472743787 307710921 695831481 172541809 657017844 378303886 915852872 78102856 120732997 880676200 933850867 451390091 627936570 644166641 786929768 33457540 442191346 130865078 285749493 558591747 811213415 189714016 617451223 560358756 569324957 475846554 868172363 243807385 427456596 419951263 617057917 314051469 799111894 743870701 978459334 157696537 262684099 790602387 892667355 295964432 582598710 376004248 407531101 517032778 563525237 709532270 738845661 136399136 890245038 296584808 559945312 223040502 496697634 78131683 821007271 414490564 671123156 145748540 490820926 87227815 754243252 319367544 954051135 154668057 240005532 910946905 943635263 35979227 689797919 583401311 973230266 635728273 907212836 701277097 755647800 72850916 135959162 145754525 651164944 547021130 896379470 711246933 899891451 108127067 823293321 60274031 780470202 813579779 964249304 371591478 731859682 541378605 880640697 173099260 331329791 748710524 951993846 614950234 919561031 200790020 995806637 398661709 598889210 48339658 937070336 238294147 386873098 542354208 825567600 205759998 396947440 104486840 690207756 246260645 507488273 352894309 832715868 552521955 664513440 224647458 945667739 213141955 333039980 462007378 915792170 529869115 963031322 203644231 771245379 275568013 719702195 658642667 882112006 900780140 962818556 330708011 753804617 564606813 963866382 302245760 651960775 839452567 979146470 415984528 707853745 231141929 775912768 253499518 529656864 502931552 827002791 143015657 663489091 131757673 261719494 534919993 706792917 264250114 503711795 174234153 328758721 256850251 259925656 325511592 385200640 276080943 682854589 473691322 846167018 240508721 742994872 145694880 937852625 314924634 643814001 228712323 250439294 792768526 942928843 613643419 970834895 383954210 787893508 447110820 905827958 155325484 542620251 152857142 567168086 76527899 535572977 634244402 735682386 266209010 435756553 369126066 542117396 841867085 975579382 690592342 733738741 261231317 820007843 346621835 845787252 841284756 982812852 540221286 802865292 199268599 341839743 507129221 676552850 114936467 241428158 643209233 710819173 60036384 425110152 803637460 804133394 596071887 679838332 315326179 747296101 290541014 907901730 420670701 967387215 686054429 937793472 146799270 775450289 106305506 888879781 249767435 757739990 382577243 628824073 154436018 722863443 164431821 926123235 447904515 505076624 160714721 230092309 271056897 569630254 520675906 738757825 243007351 369050517 365861764 790270428 482152988 690728203 283319706 912181169 701991457 953411546 465820988 723672558 113811282 242595175 258022464 492794440 204194860 776955355 379737528 380523734 636775041 722603689 241987389 640176825 162799838 915709937 165529234 550279668 524693646 590519976 88730440 169192126 101677159 450474887 394108580 497443353 27759652 231897835 484246309 540317245 378634773 842331612 347028313 545209152 361583454 967688707 554742291 989167063 114662815 604067265 549725445 990816051 158598036 498057917 55898200 736333154 587589854 871533278 104046354 199925342 157762170 347099649 186074216 206053818 414409165 649907374 355567509 729589051 446130093 733012036 43044006 674756615 384953213 418118802 259226494 760368413 217081952 721108703 277730190 523374222 433817901 472632752 508735284 598852252 165293744 799874491 61566372 496093638 37469898 852739966 806133917 844947593 495932066 507483980 15101863 940527392 310560208 470910421 263595338 482937023 616477123 869780474 232798431 724680638 384645093 978772319 933308655 945267889 440020018 961229841 103509569 805709903 338410398 357781457 151274405 422561315 726583552 777327205 150316458 809805517 166445163 215160057 567678427 872746555 218926264 251247302 278453346 826851586 38125720 933090242 172787340 229534286 726063082 844084856 144477806 241598006 474916421 840434237 546993660 558882332 741431710 842569407 402493184 520827316 181486667 363666873 143135335 403636263 129516631 701060315 135564126 216473843 104957048 649544072 218912500 269325758 366538385 601357964 257036931 731116265 481052750 751761213 412393314 816551503 387983313 970386944 784402578 916185500 246333869 596072203 42407437 90537062 43248491 959747601 614545034 998564208 636127558 663755335 654868586 690278441 178557540 791786844 278616675 664098821 271173921 470330857 559562705 963304856 513595988 528075365 82105328 204862043 65976601 229793039 45144918 215636395 446476461 544377166 393486973 862328368 615293818 785579355 172125431 833412138 807388079 973423075 21304532 288278267 534939152 648619755 848682642 947440565 882411704 957896777 570683242 797551298 879213599 905058136 309652440 579637458 153956492 165891000 524538002 969583841 344930304 766308641 498335593 988480461 27004188 109855155 218686228 387778685 465886554 946809457 486697654 614445019 53829963 806068034 347438558 490420168 58596193 317029338 88367826 165580104 103550417 428056338 67041192 378149220 588420759 706187675 514566163 904399571 565377865 825923171 232522755 559796305 251238543 739005143 775469202 929849393 139413169 604822923 137757486 749583644 73545842 448652822 27374253 95683208 58359789 768934001 168686498 205047628 376100560 747589232 206064520 424487668 315146514 504587845 111661873 168068425 260575155 686738042 355519749 474144136 208831999 614637795 53518613 739945290 66328970 607111773 283749591 584686398 709504854 801909469 155843432 439869664 220142451 660408971 389242776 479499747 551416548 760471569 581507021 676549961 44530529 120062104 369617917 879567327 574955244 609793377 229841108 797365008 269318810 547136446 615499982 895176001 101320098 732427316 243667516 991594182 144750138 417081690 98828638 248962114 857925202 965330514 473180243 577625256 693418348 902259118 230437216 804103796 135507524 966674431 114306471 333961705 306999098 821960475 31466463 468793037 585772197 904153360 328915664 884622827 452679796 652625199 341716036 479484311 533894824 977041360 121245283 531799883 270880967 560789141 277501657 761377527 766858385 862461166 273224700 556786134 174561502 738500081 869104772 920981549 462079998 463418423 254198140 379768398 127163072 775418502 188431818 457739664 877748214 934023049 347633095 607979688 165429354 599710356 605534619 943732424 49828786 93781253 133450053 461708941 821360474 932166358 223726758 577612402 548607089 900186690 60393948 352083043 126733668 379185320 763408688 918912336 593369191 896171094 407366160 579201318 125497194 790604368 138841437 865982203 60342962 885787880 279213632 300280880 530035637 920744355 253950921 255217228 770822899 992465299 47480948 200153196 253558810 472298726 412232624 965690423 221956644 744446478 111825313 464213008 67301523 734333742 220118482 437555680 73661052 753733968 473955350 926289195 451731984 941581970 111211046 261154286 673526474 802836782 365247683 536169835 512953436 513488712 613481825 973687297 514523672 954558392 544467807 965423336 959084336 994912141 292799998 798649006 198600348 978102095 412315531 820374540 41101431 190611559 73148411 543538875 107763508 302923293 24461063 956518487 489620047 677204639 450077668 558948634 756826744 790494735 14625752 940725057 55726719 554536526 289181153 429805274 752452638 981886572 361624998 918855121 162165138 666457283 217351578 317794878 126919828 965243705 328122886 878488924 895717355 907003495 189409044 306475242 444002034 697289801 700004123 775314913 113914958 817026879 946739168 986641321 410164436 802689636 246867097 327323143 637521522 843766614 363829460 758319034 90485420 742111733 221443784 378199830 580070334 862318843 435839627 701629777 615362718 815343402 455513099 477551223 473069607 984956648 912471573 970300387 222041251 754411224 26972300 854902015 146810200 770463257 361837475 527118462 9219781 500739383 417883608 451321436 520647241 727741754 227761162 927298370 689325931 978465435 540291233 953391695 29491712 228581080 306515673 425574989 31849315 194891884 64542791 327245344 781244638 848198437 434626788 989505074 778789593 911149864 94463728 339433867 356522324 951718965 442064443 999147774 23776553 385447832 51770738 70647764 716050730 723848130 440562482 813835315 183450114 330953383 28233666 481528920 606750715 796751785 541699995 541970060 319237514 586845764 375250979 627841629 787293803 967282100 530196743 998490303 368638850 733114683 781586676 794360903 606392089 664484268 96876390 190237657 20691784 974845487 353686211 828242049 333015223 598623295 270109359 419770009 153342561 783420953 148083747 376568489 64650488 947318547 156127148 535592355 539125245 837817276 330747549 907952034 647472081 666074753 131350285 878834028 68300657 578285102 231513275 672112258 654499974 966926222 630951360 931342565 761867883 826625445 692635752 983349559 199915184 649133025 595834793 704004030 479945048 901249040 705504236 776030860 326632846 995976560 772638273 920762572 237009056 285867229 20600063 355537428 608038192 915340894 285846328 443709031 426836260 863436147 287135343 707154304 69163402 903836893 22372370 100381638 624645793 912694234 447476754 570501046 588187911 862712227 107055720 260449736 128077309 849541480 22990746 145138420 221165619 647210811 189736532 567577984 427696862 589328940 39877906 611102554 542462083 690891327 306109186 316194982 174919065 422077435 427769067 789151703 748818817 943487277 151704166 916901606 467044299 581732572 577540903 752759813 353020402 879593026 107901535 970203574 381228016 675346032 149363047 759672084 933011374 937102491 382222373 876847595 602622259 671721246 359753627 686311453 7546726 18533751 156881088 904473668 12902302 679115497 481246575 705625528 405570215 538213170 371974851 432397483 488149690 723930572 720132299 995372659 452005993 978207668 50751662 693581014 598916249 883110831 135326275 375171438 448550328 565985992 461847844 807415567 277930505 530090298 52116415 560370860 331895857 762291360 599172846 917342517 448281014 860666283 463447132 807336495 397254502 721285490 321885489 631210878 455701323 522217147 240803458 720457450 96983605 517209890 280992916 585037402 104737545 162022917 307039378 568148239 220225210 843872328 709569765 976636361 98693702 433303432 362681203 485474430 168818561 263412747 38699671 301491933 39784486 802468329 319634432 551258720 207111094 549191909 907430840 953029063 528601128 596658416 199012588 531781692 123183538 942201117 198123267 553274304 505939179 695046072 445908569 459578720 209378039 610321866 214166992 820657695 184963941 922924158 58883812 590506202 294708707 408780829 316342564 406587460 134454754 390929059 12578637 648310475 273080220 432679030 149215213 784058976 7779401 331292516 7783255 467242633 244923114 853516943 334012297 986228714 779725796 813800721 226922572 449618205 279982352 382020508 610397211 736365132 684078619 745034583 570396103 644205944 497032589 773206413 144370174 337880178 277480810 935236422 228345001 263886454 185615691 688443106 104774746 443842353 180195429 654015821 567488080 967484597 134168286 671310180 372137359 448397790 227496535 593422238 92448816 149062132 101241010 845052160 344691139 393488066 10151663 833872251 122581794 338221249 583140741 634848328 732623499 773365871 64977602 358083519 177122302 510947049 616294128 979117803 467251763 576597364 585549654 974626756 229431693 705474682 313805394 924510153 322925734 443715709 372224448 559245267 349261951 389952728 466213594 981203434 439119771 851906337 432727852 824536465 644583381 900655945 356164909 915063259 9421123 188764212 223489779 732942580 681850066 851608078 146804388 217213289 542696814 945161124 126953391 721387556 74299495 850431471 203406204 566172791 164418888 868638651 105011660 915808242 457300979 637046399 34673956 945439663 232955708 858065468 629475394 792351768 647755463 753602967 20466703 401166252 300042848 371386870 149364878 826161222 751809483 879791279 305714335 583297300 744541419 753149266 638708321 677910894 373310871 976163275 33432592 409480364 188130510 260066992 635343324 642162827 121670259 628256884 1021811 389937498 157668368 886342940 862625333 979097851 52156127 539288115 464903852 654574122 367605137 801821305 119891203 926250547 386878748 583694858 532160771 763970746 79403696 502403813 21358152 716460212 380747329 641161306 359839143 818086333 932140230 941862975 754318423 936891687 180928490 392282683 591797249 870020513 349553096 749710974 258737682 739804446 867818917 888101638 263777231 515713913 135217637 379965722 252994417 891692429 808261537 910251697 226434041 535547170 105289414 555372743 452380101 613285766 364424273 512945439 22183480 44714661 56074403 194613091 624677243 795806073 582411324 721198431 591128014 846260342 209891914 520186093 257462914 683523529 189880949 639530532 126111806 272517572 395109787 645438989 171830852 665977305 567713705 842533318 743084821 878477735 957496670 990193462 304872048 630879293 43950723 685159632 186178032 421661733 269594370 909746160 359342137 536895614 531280723 815932775 691169977 995548393 783972806 939212969 346565699 960368684 706899745 905855276 764966596 820027696 883590745 970236442 46174850 111545342 57984729 412750098 99588663 184637275 659449619 726563846 165335117 438474435 552413535 612915283 102908103 687704886 619314645 690990692 321965530 926222046 400894426 884782359 415028019 678511480 10057453 157054321 423909816 454859733 105186384 636503780 345726779 378242771 407802928 876691873 85776309 308653157 48341547 972761871 450083515 653575121 182385472 185899598 434670181 923231743 216541329 339840878 655087185 801744180 523380857 601474001 95835568 445956918 604111939 876376432 107129765 901412012 656208470 697457951 227166662 743915982 116032106 282142294 185691699 447481102 215684860 361115958 16715705 672715553 151235461 781946693 125234843 442303486 136836471 522427115 653412506 826996737 389843766 692225650 653152182 915577831 68569681 297529158 26311227 603354873 107308102 306791463 660546539 983188376 564151621 612091613 294917983 760098583 179193346 591276128 366057642 725232591 190737891 384328227 160039896 690247895 228282064 585232186 753070783 870014443 722643701 877090062 204911931 609590889 218559197 987180864 467334422 822084127 257851116 996021154 686966927 944248575 732033408 899081487 274863479 690295736 314975597 366618984 178425832 666012218 353739752 552100769 56225449 253318147 101535407 406884110 391801396 775022423 67754103 124022260 249258315 841543269 159869234 259044275 230056074 552877796 550762172 596943893 557571251 866096266 375160491 593225462 415863772 432221194 778672904 824940675 156203740 892325228 148472943 898498448 112191144 271879136 144882134 461183437 108768961 921967108 930354981 956107426 49972701 801271680 280893657 516919428 593772773 887501747 377335521 680206484 439564987 626341168 33337589 515530299 484483226 799322122 469508266 756072084 296980067 456891850 242418372 307059211 839717791 856947231 27954630 898562635 250858672 633352423 391690000 540238100 113734773 997186369 91347920 563036355 502062201 902956443 236618598 668120297 63283411 628626818 406637728 940347780 847429076 854028085 667591740 932935793 134917884 668778335 71166501 145500081 74445824 832627281 402474800 816534685 30232136 578627638 361930256 800630121 288505838 927440210 6025713 281068680 640107344 642169120 158099484 288555127 830666162 948806127 371917615 828600197 30809066 723032557 469459049 584853752 89464731 526903070 752040472 830610079 199554818 273983568 604690641 616289032 44978717 897543718 585593467 640742264 78992731 659812896 307958392 888434225 797810286 934942469 439864055 934897436 130330135 698655690 347227572 953471105 891121967 936852165 51374300 204011292 365539111 391751396 354487725 921351665 434838837 864796086 284368875 680891601 36211155 313138342 204825507 557729812 878809615 997391332 516617285 599594093 150986862 173472565 223521028 893067530 154747565 709031283 116598956 883554742 409590846 877391548 645655383 795132051 694439577 821547620 140385146 696391188 442421561 819671211 5302710 947864467 441520197 730987338 376711558 770452138 5108888 699954729 248728200 600902487 55793774 372144355 229461909 889443813 61163515 475737069 392946110 845285982 659507894 920203905 230519191 298771774 201761345 783291498 17813601 414580674 859979541 979658135 40804437 496153743 674878384 818841760 125892070 666799342 135400818 378939170 145690909 954620259 624680608 904492151 312478913 939581442 559771850 903661955 148389185 417569402 314201002 651581327 307126931 926810796 259414833 546748278 599583296 772876958 495347102 579105862 465684231 960806471 586091985 611535136 690924453 836320198 319701266 637749039 481748210 772415931 296511974 798063622 114879615 911668382 305260186 983619540 491932541 616223572 531138453 898313025 79189058 450303138 121638385 898338452 221526546 379587544 824081607 849804699 688031535 788639420 187986971 947733370 182529713 521919275 38261999 116126412 790919235 834106449 168268326 557847678 232287423 672290437 572438846 850025544 131906787 855805076 45065257 693397388 110793035 488762671 137523437 935956465 51967184 226723735 36868074 311192275 301036867 622414665 143567928 912093726 563333762 855153900 411432749 735261056 141965174 270571718 291255450 580109922 522260464 691102172 293737909 890491576 501034422 740047190 256888337 579033408 337532602 994435139 604746314 714549649 94046125 603110530 328074706 820565120 197546720 263975122 289241744 737725505 416999053 580552455 47576545 695098516 112618198 316483071 38007190 489304199 36534447 993941553 384185977 740878377 322019894 693294672 310255106 701956230 22541501 803920821 104562038 988043208 154462326 436389547 294733226 800397863 185284994 944357596 757217933 839199897 109864965 399028786 465967551 807092210 149614362 819336793 131505144 279598773 1899760 930208417 371126309 913790641 123196373 888160354 625260596 996065386 170446492 521290645 105941858 806031494 775025918 815657705 345744811 969245075 49031998 980184595 627093224 661860256 690994642 947193766 378865633 648612198 252787926 784721550 452587307 888923426 683061520 941778314 672661931 930576196 76461770 156585543 243011828 323238098 360672019 470023069 433180020 466084716 17389970 418459818 463497323 623438609 267403807 592618939 646862593 672859198 451070203 794246147 323038010 528801203 472559176 688172453 172256770 847729316 210391043 799107751 322655566 980683334 381774943 695587096 564573429 857245237 210940475 534900364 452250130 708311500 622247794 976682826 529940448 772015480 376414769 749409768 15559129 400442458 597066794 673051795 387557138 775661599 783723310 894677099 626166337 768996274 531333123 781371433 344178832 640348835 422667244 698789773 60110575 69503368 246209441 409074905 147490353 574060320 699767770 821085255 716300698 859288692 67391675 613771793 320843552 683791573 126865886 405988184 426318073 553904646 572246489 941902629 115283751 613692383 4805244 495503380 250923133 588107277 145197235 671010804 641702769 676684653 202295761 613729648 131387152 634290391 274542936 671508157 499586930 511604703 679733905 749191169 48521872 690663093 527083743 875482223 303214301 448792012 274441968 423049236 394163932 763094002 368546804 711934234 16021128 177017381 393576149 612101247 149718453 701007338 874958156 919222400 121354128 746793991 84668218 558351927 235544014 899832068 674443148 736226602 229641703 449581875 307840064 869897541 732247 460319263 528168775 893519723 246930085 660404414 218961633 617945619 642978213 660259564 342103373 539863056 247732348 350178713 279077429 749861152 181277811 813981618 450559325 502789808 253052212 295470617 698460591 880272843 540718478 892229787 416337990 907508362 399961004 690554097 16795873 63719310 65658732 784957217 736929627 915920399 699628139 944149927 613759329 747517715 437442064 488318760 167408717 446535183 539682020 561921612 160051132 647659590 827727419 867194575 475175306 540904014 334955174 732022603 442573845 451080376 244550151 813358805 178004364 792255811 587006501 688197030 377357388 805324401 741826977 892272859 75540099 265384290 51264795 732686221 878706542 879915911 824248709 850129966 36351262 92558169 856359231 856407725 354133807 398662558 244761881 628995623 683913240 921570695 827412014 957426502 96900859 776910814 63326425 930605826 435102055 604374974 871374309 893193389 229569395 837229677 171992398 832304613 248886310 945962092 512986571 827916616 286208985 646520845 116032883 996831103 370288455 559856860 129269660 941476510 342370402 347540675 439461396 755995042 268137824 648898159 96177073 108368915 289849511 896231013 129182780 831173082 534217184 704981090 448031918 495623732 162251821 925939995 70151746 577354593 204420149 612146094 201400525 881289847 574064764 713514557 306113506 358697986 138558269 882634897 59278257 400217689 146774159 350942698 957219059 970551912 482196591 657012844 251567668 383654045 37148733 177012893 716914859 942951889 239131389 627214745 692581458 790999132 571013616 939673717 418264446 642355003 14150597 962277505 308393711 869858875 59994714 702203522 97033760 683888475 484214499 823140613 320472461 596134335 56601995 664109231 405615009 833364862 227109103 863422018 409255445 709044856 341478726 830991465 341263992 353988999 647156681 683695304 460406336 813810595 246372394 821012092 181447883 568043678 395078152 937079332 363711225 502654910 633733937 742443152 466583461 885779200 960529463 987928233 88064016 523005407 609151631 895649609 94233206 518737790 82662743 853698540 337012260 784830147 94215891 467307052 436837834 544540611 266326856 662123355 593046865 616088352 179415366 479867959 869265583 893144560 98018219 248289370 118251773 715312861 84918350 593346184 98068299 854215433 108997537 960353670 653597176 819808237 694287589 729402334 284860091 823965710 120819983 174558833 579280111 599090912 670521185 819744469 215873870 603166409 707381892 937004215 307172015 818874779 605206402 709822166 318953654 460975256 694579409 824866160 7118753 531115746 63972262 954974694 369050030 672809416 20246948 406124425 721695359 871283870 286202379 358362720 29435644 334692753 874964184 952482175 609354837 659639007 590667979 605695995 136323824 342866333 508875910 859319877 133739096 139330308 452125941 972426676 94998400 415867621 310422756 676183148 567735120 572450641 293907070 930460373 327365052 382606144 533078795 844728919 602562588 895151978 146113859 557235453 520882186 919816232 33166379 580177934 103383262 554401834 819154325 941228683 57893232 360756847 395328853 664949868 239638425 733833727 241740662 728199784 852701252 957768847 10337879 637876554 304417205 543117937 335483583 599740636 796874075 993157242 38167666 191633348 38546330 54997367 580140821 971223708 44556026 753143724 387502117 559198577 67026439 857994546 44136695 888507579 576158054 832312215 84028310 875019513 721290678 773563705 349650414 960170362 368024302 730120348 235725370 926188908 160280181 805284490 639779409 743901059 423031871 848124596 221069380 406887893 767742582 982698809 382709257 442048039 205223851 519528239 241884594 851814188 236300180 392453155 809405381 937377065 73807018 866479148 211115898 302267433 355388578 634004653 655948612 910757234 216420276 459423684 452693170 519371547 287178726 954798906 728651858 927598876 352319319 356394478 123126600 542899251 93977609 331061061 675073668 821982375 30944752 77872079 760200331 802302454 591391866 617669114 485715515 768521479 161045496 225863268 161302752 547471502 60523430 487910659 137726562 846538969 402398549 998690873 239143940 540988548 130111915 952595659 261569745 406822663 562933897 655189809 522555048 992418851 732691087 855308623 120694647 181980828 901054943 937630820 640192325 794982313 17556735 580290656 341257637 649619066 401779387 680763843 187377453 836945715 201658083 380073993 7673397 936190510 293178230 599958342 926203 324996681 20484976 236750209 118819976 658716155 7604902 303475358 237474314 240071792 9332701 604270964 546509143 631924482 143127971 543486899 25354224 392575655 241387759 490987897 71646057 396760971 329406548 746878935 595199085 671675515 670815508 786429174 555292049 989398543 6449314 851238736 173555210 589887339 173214770 674334801 135389951 708205025 354110557 981674100 61740227 624430646 440120671 939360311 338143132 933571022 233049862 604024548 487496902 690188581 648482737 992593870 140439486 209091445 310276211 664624609 68424896 253441720 86700047 646516707 85568752 273153907 223647546 493187301 250368848 645307704 115886467 684330392 65252510 447387070 325687439 998189763 365319993 801865084 115177380 486540536 210723429 388466260 58883460 64948586 350207892 490487749 826354159 977491109 151379295 168776939 900301033 951537920 168871947 329764468 139054657 774590547 65814716 755149662 765140685 973285735 733396109 906201953 489339722 991385438 51835469 218647069 92345788 450909691 339769301 394875468 271729005 477091048 324134221 332035176 571880700 717367381 561707408 952514498 139395868 664426617 419781494 904274997 751747932 826185854 285101066 561545826 388732658 851341548 383175764 498782179 1528145 662986193 182748432 968226053 20711467 280105201 662117957 808320053 169683846 834866538 181997741 354613503 66193366 671389401 852738750 900899088 83701409 416026979 475905208 596084111 457856922 845374684 377271336 955624604 563534841 650968350 492496866 647621583 54199384 614470507 569508642 820938501 309045261 383357386 320805286 564308939 545057329 640714803 586108156 797754109 333863497 732336036 203229351 632871199 409755754 702427441 69491764 816888894 750086759 819240337 236485832 906012125 673749400 943509900 343723808 416915942 658220141 948129315 481628772 631454808 398433599 850396916 28790606 908375567 480320842 594142715 301996997 761916586 121175481 964850363 194839086 965969964 381956142 687439216 53428290 522523805 454935884 482701757 481421123 884241874 138049487 822734412 17745477 516357786 811182292 942712508 610775773 947623685 485510001 488460739 276269559 337817095 378105044 812660295 416625667 883191621 710249739 775545167 672544774 748418426 584896266 727436846 276051392 997261131 549640599 691425628 240810464 689683334 179635140 525597989 554383457 735697604 462402555 625611619 142801676 584840280 55350093 601897053 506111239 541990334 426634834 762970018 240686306 564407556 114765338 622901844 8863602 604238822 378709026 660880869 248342935 405481342 37342774 740201581 433786267 766342115 687197408 771446779 607464059 977360209 527129742 719335068 56349906 965245247 62187244 190736324 200218151 851862652 828006804 946169806 360627508 602265070 93433992 446243129 785801459 870893044 394489532 620653920 678285472 996514396 37000915 166434920 307147646 418608158 172557865 210897530 140824442 673733031 647054868 859763251 305530712 329207082 36772197 874245722 345068348 823464462 107062322 816312529 87943281 238608029 298437327 714072024 375570201 426548559 154076988 993778765 200333889 447463724 426831551 549944146 28953880 466152589 146929634 999241478 559737028 910262978 111266979 841939592 129268122 966123979 116715053 331678714 765071965 786749337 327426822 376935310 274136829 766425411 42201674 737466620 132406133 820074910 119008354 161940233 783135247 994076151 273414790 967679415 368983763 616202007 132245857 300669153 5968440 685245580 135031002 768827171 144902769 283310289 62185559 391332303 217955312 745301962 658388315 713411088 529887697 652008136 396972872 672400468 398492294 864704476 79760214 729171731 187536234 471820729 768539683 827499897 59505940 523933786 216239920 349567902 16279580 504154291 230234734 286549551 726966502 976578785 759700354 893874663 95053749 948661646 311612736 586102344 230317458 604747262 287673598 372156933 520837083 867578112 322096072 822748412 117674383 883848595 231978046 956615453 245917808 455642430 666716613 992875366 51886977 647134349 154082346 161247743 269807266 934675432 436459020 766750469 818442763 988198421 109913723 638771618 862604065 882883796 396874502 866769979 522161117 810694777 95434156 635949618 48924093 794242415 64459055 987671249 174847204 933517578 67935814 725692103 462868130 739873922 681449368 986310257 29805324 835203659 6451587 645442494 237559058 728812154 191538986 431798885 118775950 421669550 721719044 835431430 230064023 644236852 240034800 800561999 290648585 907433845 44320961 701365805 92846977 108485755 611083545 997126180 39860323 730256852 200100732 825754867 732806999 835158686 545266913 574786370 228008503 335206531 31051218 742510899 470018004 783856753 357738016 426084327 36972889 240230709 457484720 698209133 131299277 966547301 727056837 751351213 60644525 530305993 280390984 390655450 472589452 951668525 683265359 909341468 511462617 677418132 23725669 468080652 862560506 924940695 400881918 421885038 798215022 800286262 702938942 784403238 445203792 894400469 552232067 594939366 92998706 107742546 17527464 193576610 477865718 756725160 804660157 816418832 138543471 140050753 678955939 743693254 620511756 841602763 147473241 216106531 168936448 850344193 62187178 402580313 22484586 750878461 763394834 857453249 399639381 731180083 358145120 444376559 266992622 774024878 109177415 138839645 22373730 376961582 235698298 612054531 55240886 383126982 534788566 657493606 213198330 284692897 251016814 804647494 755185506 889109601 498491254 809854185 2008365 949621044 592064369 677195428 277976281 454375440 154303842 460762597 488811029 598935488 88879118 493134761 310192149 493001477 469433466 887250480 682047407 929963633 541983406 764787451 269559316 857973032 115441345 236596720 209203500 260776826 334304265 386212331 29225465 185229557 74852007 605891676 7279705 897892517 77996978 866425316 786640874 991695771