58 100 280414784 584306911 276644084 650241002 695562536 721896599 303627374 235349472 749053706 619944486 88931624 698708212 260321115 117057059 462438369 373016203 770753517 458800322 463345682 206841095 971869882 97696284 828063482 156348002 913856612 203144107 40465799 382561396 59905258 676997586 585693008 861632025 576325657 986085358 883500782 721963355 507315859 319142332 229761684 734113975 574790714 739230961 346675523 272741013 339101424 202117294 322631338 85783971 770631748 233060274 466001976 441847953 187030162 271654702 579587825 768197569 139636391 314383455 596389292 153772018 900951272 328063371 569836198 541871137 959719779 103809259 858501725 723276583 827281459 228594448 370955239 857329654 391370184 994619119 796203811 2014639 343574082 505859452 369979099 702002927 716214127 557840685 855868772 488859889 606886256 225728052 848124467 539459797 685382842 440441950 848133685 805302479 608228660 606794901 414635389 484522403 771118316 638011941 203069095 957951757 100 900898326 322661031 596313458 785623562 51612968 164520002 12240524 537772614 263365295 879436737 977017550 37277663 237446173 337700403 902454687 843224598 721013702 506981921 329449053 594543582 77636012 574024474 733721286 392432821 601142797 633631905 125791179 753698056 760787979 654793762 207353218 362186985 51060650 250968940 568583041 948647395 806750659 149334842 914554621 192139583 527596780 877636489 858969330 961426332 456476982 1743598 16082698 505086008 523092519 869899221 489717113 580745562 7188402 918982597 836846034 894922904 226554492 843182382 737693755 80021238 65885979 799516048 471193386 291253775 946673088 488019750 362183643 987241888 88632425 54183611 632761339 162088149 565129519 697568920 429226755 469789495 431266247 504450245 84547202 428433792 631434666 772201701 162417664 752987527 406674406 410928892 72330067 999819483 239217871 471581972 374098759 596725180 438658419 509086446 517954340 770174163 901788214 225596029 235767814 636162861 100 471997365 198338609 537950724 703502121 214584825 943124701 325885635 696839392 661088416 688003166 103230051 796957133 283146492 362865983 625235768 255521053 346119674 380973720 495608665 557738609 596841903 134218709 77072082 555868505 256488326 188961350 757157495 540482977 416833977 122348157 219129241 968162441 726995814 322883810 953721878 78083635 822188873 650114547 473734498 577950250 62879761 790397717 951651460 220729811 969886046 768755225 298278863 687978196 47522133 547926495 913426968 672336728 75177010 479620765 118666977 364005305 339713408 859151954 959780019 80409269 420239908 364606822 399052416 746209829 561997059 143175518 942437249 772559701 960307687 133047736 432513344 932048281 351551969 662971276 754191697 786317319 722938432 91243706 409762531 331478627 660989991 672172939 459073660 601432675 136929125 711075857 558790968 712797069 516593868 946973631 130989987 640446254 2245830 931436791 62618407 459316014 885423631 96715403 501483035 566232025 100 958505153 413625792 795264867 754613232 481444395 722749976 86402245 45272262 362976321 40614834 705855024 642416809 433198985 169503901 565221465 260294909 532006672 476494253 301172135 424218877 322284334 273935883 462510723 979557031 146564302 644531981 743111193 224756674 635192436 320479865 641237316 319248883 753394474 415271493 561951355 441375300 895361388 84030929 48783976 374218756 757219776 629214709 866368758 955119081 901627712 889831101 147714173 152203042 750372930 755287311 922390327 314846274 989093730 941989808 982666397 121970055 302109103 278510318 182066043 866468961 344401415 532706030 342740590 940182655 430515240 450661383 812164586 187166441 412436871 922501867 694078351 147381065 925998206 601331600 414796029 263404371 933655297 372097441 291922569 196931169 929306682 676291890 222355231 964004961 807684023 461410927 184649057 649810104 335573166 386386070 484704147 970377278 537321930 608249432 191053714 735176392 306807918 353979165 147618840 977797066 100 624524510 114048043 675402314 499648288 93469602 441383720 763255656 98796503 317684105 328263911 372638801 610080811 729928424 135757645 251262027 67172722 180413612 681185525 575930035 794890187 783256831 520387351 73013968 506675668 898159343 470515386 161457394 127555347 682416473 793921798 51623068 938929135 877999537 571079634 218787126 4380654 159500149 831640569 672328073 872382584 758817770 790113022 416961193 389437384 451206408 978572574 989381366 563055876 915678686 192595726 443671869 700599572 844225231 43991157 633147370 985741066 772365313 577076387 131221332 717790833 761890868 850327992 80863024 394949153 255955850 147747300 385567797 371114516 302572956 167061067 950037841 285748459 764670451 851205965 912379045 930743627 502478295 984655435 123055328 460442539 430058428 762419682 661728825 595088295 381354131 249483959 940274211 82888940 188591261 60275056 271378872 156249602 666803586 265442743 349672709 86814875 371067356 582154589 502299588 502576761 100 747463288 905454008 549866347 310667014 883445942 323689766 538513819 619376019 747026443 597606725 89679405 621040624 902582864 187711311 653334900 231031434 126509992 506562708 159801983 438403055 211982182 489674429 888280734 988353253 799172386 729658352 86789370 521003996 554549308 23225802 511169711 550529339 43854274 878924954 727139099 368362896 843333520 943711127 629434361 914608788 252753211 991240776 33029123 918359688 762619728 36305883 597473460 181547174 356757421 359078982 652900224 970259818 724134349 635345804 803308984 971033405 355376035 760028813 225116928 259523888 849161039 379002115 712467793 94164062 350068024 496532450 706799465 423181566 187641685 36082108 146929963 504355048 896938708 512397684 551997070 96757061 944052643 225443179 798580669 297130757 115672213 181294721 125140466 650668513 710783374 677736572 649684890 360186362 219383408 807729198 737400658 793283071 284435916 733016518 696504572 828504725 207897587 899554985 87329202 174902940 100 105516334 804603760 508434949 962670628 416087265 525004087 129968828 860467882 978934609 319124044 671120669 391944433 136575981 865680978 302078357 484115428 45644971 666363169 265430256 43051662 984980415 996908140 768842636 276924611 648256549 508996262 238736870 797960803 273449788 981227309 325027845 584813941 122072002 539549790 862950415 25456007 492323371 683850406 733213042 953085094 406521031 941734898 152495778 509975179 723835312 159728739 6490899 572762584 253845914 455816487 925983391 213815780 974806609 821276701 217578057 12582540 64652676 367903011 505387827 609788216 971503632 775754280 339825632 421523808 968748901 7865067 325261224 981255404 192779155 99467395 57881464 107765345 390442342 877734129 829240808 376455412 418166337 537686100 655594557 938702918 533127070 279174601 896120233 535242527 788144315 969846335 693544770 609671948 186438302 987551355 711445219 307830585 882120996 735058363 504119300 524126759 794166424 550401340 546415834 981911005 100 164293866 562238324 803144661 707722975 461084947 710215550 15493891 154695314 885703316 633260670 403801363 520592139 487145397 414419181 215367598 192986719 609666882 418962251 984906279 846206862 839902057 990336951 408602785 648936101 741877131 109747606 767015441 448880019 993772773 267467968 40618669 815916174 850946677 684547187 147834656 164908484 252797595 715894907 619780746 852800032 146536966 953326351 69249070 613394037 599066293 189905860 618990962 868019611 456048665 782519098 799360615 116436413 301877582 380976527 470869389 464984836 80090104 581425477 579277761 444945707 398487591 636397342 766890397 984684385 730316814 334110150 220561521 652801679 989991352 813467218 179156116 81598711 826855592 449883246 621425765 266750514 318991150 79037842 894604217 176582018 638743321 88066922 273750160 116907428 412872514 733534946 594110342 287135155 255415535 108156955 621198246 584529669 139678074 500732409 341651536 316289564 152892864 196390052 416164978 773225748 100 870429371 629613506 274618717 704324081 106985401 99685633 688871052 448119542 232030099 412550617 646827247 248163890 315598549 391829821 262635046 954464227 292906868 325368420 47939822 65065163 511435687 326994574 490647124 402822045 632249897 582737022 442255316 94575099 761068052 396977942 396464925 171917021 311752174 119302531 678923652 650890183 589558384 270853258 63459613 940578277 504687678 498389742 813135436 281655460 146535912 851025703 233717442 797715505 797427055 400336511 675920496 612451708 860584932 703696790 178388211 618921072 612431411 224153255 444509705 246682958 567754643 646571737 437016666 954343639 116765535 787992001 660131827 83327577 625046102 315722780 527678103 923293577 509340564 288085919 156487705 897271965 887445411 198215399 770548224 461961558 712408832 640762456 559855280 486941580 273232019 319445666 293400069 527086219 736181347 205055078 929635076 178861927 727855878 481569901 339399598 559295623 256845175 668798447 340709474 133816056 100 217685036 109169045 481545477 476438030 18001879 949057675 751089196 932334165 621667492 527669449 539601819 984403616 2405978 862444137 712325274 661143100 790682978 469036677 469124709 797221017 180023686 714987742 994864673 602662492 16806174 273942084 725330695 171726143 230236085 369621636 930326761 615606837 634063622 827050477 731490601 567996722 158783820 978136852 223028150 619449043 394739406 763265295 254074333 904293955 730563825 801089872 89998680 522533783 769158275 618134256 846515029 54563111 367140111 968587321 891919148 31976662 525575722 850102597 68567752 814018415 468235542 918941406 34883117 197185044 850489961 910901117 767057144 207091007 112366152 181625470 864164733 339014662 541868618 958590530 957019911 624919314 287431022 986853896 473985961 255956068 600855508 481030794 51138968 496340453 424598397 64677235 882037463 293072292 45778712 123595130 63209361 107665186 368195201 222502807 680333416 803520154 882523118 431604546 764827856 17454368 100 975344426 675256392 506049368 931623868 575416323 944724694 736761539 461557415 145265886 918428689 277028711 745560176 282151370 933557450 235672017 816403381 297771206 168396257 446207506 144221325 485876795 727641181 81787039 368408714 701899400 684956927 507215443 829693067 380248482 679165339 120021879 838838732 938658087 103561450 612935063 759548677 31624590 426640798 282166357 523138098 2758176 890674735 417435007 571117723 308935489 917626601 457050912 66616710 507177873 957332557 75180941 547065963 41713764 985034657 997237166 372537871 426521193 892874678 509753422 107658138 752076504 891661366 868149135 992620196 588742262 152767148 76696819 892694400 410614003 862991208 488839085 568959882 371709973 834641863 710961210 309034639 965839209 705537758 23163141 583003149 961677107 690363775 140324002 691494002 723036544 581855552 5183616 200507451 966489452 773728051 245338766 211515464 738139025 648252553 824726764 193355202 590970764 207895166 553559220 895003390 100 185654413 814298202 117392365 235435166 281176954 71985292 605135918 502421805 358054036 497795916 885378759 644169490 237869363 299201878 906360433 219847875 175154738 590266819 768063960 533939765 396432504 220258401 84412355 791871824 679769848 649577122 663594106 47936570 370763547 153222175 134656319 979969848 715979372 816656425 346610138 287210024 87855984 552611550 46612609 688677034 574700221 858134107 309857709 658985478 472569442 580510365 617000350 555114513 403842359 503029246 319164770 423321026 913390597 333122658 383623553 764032394 528177968 569116779 775855384 173263313 742363646 378194916 49488136 496819349 577393727 232653393 781731245 668375773 426725155 873996331 741986551 153131274 512535263 189099687 112195225 291861138 274638953 428462834 400818076 755240003 736002370 670642023 100986387 200617148 36180563 11792608 822972217 210560366 625071193 425964713 75056578 796881838 103111182 451647585 426206798 934565303 387161578 158296857 366491160 41680528 100 217612294 95583308 193861068 637159108 406248661 192693368 154751548 709055584 922438259 663046399 257341781 47874756 209390434 17772847 805089633 664112039 568398812 667309246 650395828 837635540 537193620 528275826 285461787 676077852 381475292 248649964 65870511 233833168 414300080 113454391 407618736 762129655 873971649 375029945 654037309 812056349 71671684 773843701 992568276 299836053 180504700 438022818 282657939 774627558 369347880 515812806 512983131 748354201 477745966 434468406 969444424 61653668 599262079 488305658 770872774 417332671 344610561 404751022 976858021 299605833 309565584 537440257 462064823 56318228 778899208 335662716 111136885 901930317 216032866 36816491 634776889 521355291 368865477 163607642 89259222 760439977 885572098 872551338 255761987 173847791 31780216 413054882 88087428 823024312 593600102 597066345 595697527 347685916 837848432 627715335 470534716 474227901 90825531 712744990 839135299 596924020 114232742 828999469 257839640 540622011 100 835835047 204556490 861364879 780299659 997727733 584123459 883693628 799232760 125343357 551133030 711473561 748412425 382155182 38524643 542816532 154734158 495223876 685139956 358615934 431546176 542106660 230992115 338570172 835823804 497456392 888279638 599650328 289165634 134933626 453613777 204460955 958812186 539501598 517159874 667396804 693828942 59801679 68742969 543066132 708496484 93395126 372418633 583435598 971119011 909081797 534174291 395040436 312424902 492522476 821545857 359578888 983819491 104451168 771335731 210857074 651459287 22267087 521540027 21057990 63117097 781919386 143363904 190122682 469683454 311516819 30048263 871114626 722961442 16416270 230066463 481105457 280293301 505371226 275630971 269761877 987123230 351208462 729181120 328742190 880729574 724509994 82007402 743776098 356528728 29062759 151797299 945669021 78232449 66984659 989217870 170799285 943070492 74687206 381554310 266676929 859628503 699271045 953081214 570461969 941210812 100 642112129 267226273 248443545 449768114 778975010 780194918 107737888 372013975 177848189 438955903 688996678 50059189 945985583 941998362 322129696 338989091 363815357 255190667 52114949 196235042 229337100 770929303 238272372 946699173 43109949 202095362 726224136 565031330 687438873 168707095 81098907 518311967 635753497 645968358 988347517 655259313 84832463 582810530 975033962 483399336 117723912 930785005 762677784 158276746 156765311 914201436 985906901 94568174 311708371 978045042 126526721 500106601 635092356 335695524 383619981 763692656 192328555 380255231 490215979 129578068 51241998 115835908 831458157 239605279 567209325 697078234 371463237 657830363 658871942 616474953 740069497 364917787 185494357 865927246 671636878 281381457 784040685 622335866 508102373 273572124 260864110 587251405 581926085 917083603 483778536 959396638 237776063 949711708 125211489 738687565 534755756 629022670 897858947 173735228 768054963 787987244 925579362 125188809 685653739 648990475 100 209296069 936541440 678794462 458167039 49585944 422852026 771978938 440060229 304824725 815508988 787265834 911732933 194736809 31816577 644811531 455608436 490834775 446869583 886938325 722051622 106643333 214155940 133492766 718830501 995674928 39258370 737748873 412043494 403904296 731958274 361448159 765917531 378675607 208874530 756645935 199016937 368117828 477954879 565110116 798722249 927692902 661293079 603684710 987496901 758362921 300695663 418810153 756256092 551229767 570005130 298615229 983902052 114373869 336622711 397895025 373622183 778128442 571826284 97345249 2412611 736375326 955026535 361604029 776025096 410461841 173574659 314376938 725902742 298262488 368688379 990369427 305840165 753671471 494598851 639481441 488869728 304114673 890069830 69946401 48392920 271892838 238640997 970427339 278042389 715753054 407133690 883765799 236929218 846643407 301490072 845803421 260865341 920277203 482265791 372491083 815411071 211832178 606788647 614138573 614428251 100 883782284 841644211 567243149 982162440 792292113 225637258 82044011 941832951 892546532 797772449 845448495 833146511 720355639 394870662 460088838 9869640 533974685 594206147 95206310 595380235 208114380 255616475 870300737 463762776 68172512 219428048 298998829 408519355 290228171 738314854 359595167 710035696 279757057 201692440 442267030 850839028 187468171 96739167 408906128 821840381 917735622 984820733 123542892 24052626 962149456 214618498 570760839 687622313 968276020 12565611 464910219 597366207 762817543 445714135 444968433 773833398 462812180 48584044 838624786 809937240 581681947 937845669 742062036 629874613 233129421 415640042 734054022 245040586 796741801 903500784 415462670 201080810 947428344 411854207 212491818 903104133 830360734 837187971 603102614 715424183 917824981 470989006 485521517 6871722 759217591 574590686 691458340 238957215 519655672 565939660 450888176 964511274 475419287 67386577 246300318 404943665 32843206 936525489 888860487 470164177 100 453046052 965588063 566378273 857148532 865274865 735119651 426670106 819482661 649990901 872774580 429845022 285670947 539625807 269172192 404341693 355743429 446820187 391815500 50690724 831402477 67124993 62131740 34297784 354068818 441833822 678645624 334100828 736558499 937175828 685193006 468267444 424185299 243171862 357470457 189020554 37249845 484612506 417741335 894693909 975480745 339591853 719468791 104355603 869700903 635932472 460430202 241135600 471103515 604582644 682198120 340996853 726318172 603724663 318389532 448001783 870685189 813020103 639446312 946318712 171275286 556720923 812511067 578544154 732906847 115129352 14797060 515628707 580111976 196069530 704174365 546815981 632186083 546675679 741515428 867548145 800335168 557083839 100625514 501025364 508130976 620325263 300817855 853665441 896286956 60018597 837736109 873641299 125920703 491232166 767999409 108555510 375248652 849350172 456326714 935859235 244001334 267418978 901582818 329353592 656102959 100 978907906 264274192 424697094 625551596 761325778 328074962 749941756 118754081 513063347 928949815 189234316 554453135 306391000 974742249 305668954 707452614 588608225 848477276 837000800 19660311 669429644 738671300 421669590 422654083 884347923 231500942 880601038 111224756 590925695 542076430 505179153 200819916 271482359 672484103 370737501 830251282 131163652 294086399 840045914 315890110 986175783 89664845 316004852 507657959 544431772 838904 644492476 163992693 48373685 757010944 602490809 167757686 227194010 900533249 996085248 239092423 634951181 425132744 967177139 584036744 29898734 417557901 722774934 986935508 374597717 426061368 385612767 258411722 210732593 483193069 199467821 494157051 959626810 457855446 416344326 905952982 181863580 142094502 592684615 372178096 586640338 378637617 235644485 379837790 816000169 345353950 160612610 165570312 508396859 980011665 979203540 513698393 28204755 928615831 938000782 167083424 878241245 966739801 285388650 684832107 100 979822984 839186767 607503555 29157311 185258787 789513905 298761698 405672470 92708395 732217874 823542249 553348931 499910129 752141779 983560032 940182948 980431662 505897022 63470884 839270644 784899229 963316967 519929829 828723639 162922413 623439378 563578144 653108792 65595903 761703000 300487047 304735077 105371685 850913139 665183692 533084789 264574607 478538960 394451336 287216838 216680986 410684672 43504026 502296134 509253144 693809660 756241481 51561561 259185164 878582808 728295341 583777337 546610225 535687890 6138514 232563702 985541892 383616556 949160252 101861671 329022248 420763468 265068994 616153954 892308883 659648657 659879123 824365226 102823720 546623673 469659914 924531841 205614508 676607776 907149749 656593134 885909205 614841184 600816590 39742477 101897874 923596050 86698233 964424187 786690989 597514182 401399981 143502387 835026095 282753780 925534821 784452354 504616498 725194369 448878543 594524143 304570127 762587596 341789756 290103946 100 359821719 946132389 932212096 475642622 484556972 781640699 98921458 71256622 53049077 200960721 448504479 244064627 716464952 492316954 448769852 355880558 262488105 562897621 55584776 397772793 169704492 149757582 156503253 967408393 569747798 379388155 524651760 335460434 891880012 903660655 88541607 566110858 535017327 211498136 135803257 293636050 599186097 754306110 300235301 858862682 196087558 567090901 74195800 480027225 23425433 961742434 620601378 837779805 659294124 22934951 147299044 263433 688794342 876008984 917737854 569078774 957702475 280872627 594006113 92726095 235103329 798519640 549112590 121425243 259318601 48704798 845255649 714833959 313080442 914748121 449820132 254277199 275568129 350963578 77780929 496658160 205790023 824573350 98906533 622631747 588005829 917808774 608903917 929388283 981061202 114881817 158390662 341014166 167584265 372317784 702809094 558129178 309133365 325629917 288054867 859495281 854313964 782748234 384395591 280286771 100 392169809 931420268 571778657 799631302 763839146 287041626 411831498 455749229 285722974 153794688 91826389 871430143 134575300 677757224 677132589 422676997 334671703 500700037 403496049 237242612 808324021 180277282 385162509 367937940 160619865 351321544 957796542 754946871 319786169 195013733 567036820 6655251 333381259 415600058 937764 999717596 865121987 852181745 481085211 877744148 485146777 577921000 146824962 211448177 558058400 930006905 22048636 376392367 654476402 230036269 888611431 962651655 236692853 611909877 238789006 403355738 540077973 175495595 454060967 334894085 527931817 1805803 252035064 659118406 894409089 338299307 346532169 963412457 97040370 304386543 700528635 285712970 466866237 65147388 802580334 724709077 26949029 347620794 447392038 262913931 434468013 422462440 536010271 706925008 36910490 575047993 929975956 750365692 577519700 964023800 794458137 806579814 430348882 474409862 894590905 549410294 14440424 565084255 117607527 310606697 100 800795627 598847992 567783328 854430429 821489126 521466452 888106962 987651888 688361195 385990856 948695449 763856941 2999007 115371949 301744335 34899387 667755618 826013210 828383437 31078604 175011093 792593195 552261612 720354382 899428465 156460965 458721462 579113504 710554991 604768774 669038542 781011901 883488235 634723673 745179197 694888472 921338228 260605808 320724394 153957441 664309732 91331382 118610067 916613553 58790098 948370684 977357204 700070658 675830664 272201092 542050590 165493750 450274375 37079457 121186107 162763286 228324884 438381336 921736292 950509603 552818239 323581061 832294452 657412562 817930731 908589345 175388871 141746942 21971478 960046211 343099065 636976303 240807938 891279726 965383911 639425777 314701306 455959288 989857887 193877386 615111021 473413239 142843996 401902188 638970451 709460363 691839940 825801723 135566309 26406621 407062331 977391729 856607131 707757457 663956189 466630103 353350488 783707502 598077146 719139498 100 296456588 305481706 374999566 709899900 821480668 692254650 495423244 78020471 202687976 592320234 88928622 592569386 229684490 935137755 512732015 413947788 155691630 301812100 742861272 554578507 479828499 201806548 412136778 22556455 152642013 655397947 194270587 15669316 905551984 877133670 161670754 155391600 362668379 609852257 197252563 802072672 522005798 698702963 99300660 428714511 322779909 717952636 211060981 562816274 944347216 904056430 545228045 445894358 804522367 893499888 101811088 77430833 542038991 491933568 327203029 282356392 645565734 867014204 276259110 755688838 263691766 609664016 954305336 882456820 232729494 807831570 903911750 226382887 804882121 698678088 223450132 129033671 251033902 39839886 853398942 812690677 745317419 587207404 80893653 390050734 992565396 57456433 77432722 81451930 850765519 51187865 479856088 812445538 252695532 166649461 669120100 132402665 711736029 567934508 249065779 330847038 30689664 869648188 713543888 133497275 100 389396614 899819264 651207054 147565223 809819884 155708737 42095209 349593190 87538266 291183659 692440875 72896228 718966794 74625016 942987525 318260019 739363387 763423493 887762207 569818219 195430622 600621832 431184881 156982135 801102164 38192920 955208695 364190894 549507588 155442243 364179954 518894744 807035989 38137127 466626790 25206776 978125673 485130005 627046405 405128213 940714962 410686145 60832448 918144092 413231327 381206640 163940463 216450856 314505004 749636559 15104722 567567102 618816584 21196013 23526143 118706668 125676428 167478466 553787711 734920742 933707257 504837553 288216802 838801076 291627312 795892127 994605136 87081083 442066617 551211733 734439648 322505437 851242644 753516715 396006080 788050056 302893160 115018108 888807026 163057669 89947742 194540550 165583205 148411087 284167986 577939570 347453963 202015701 635778231 43797659 259376207 641837343 578962880 418857289 229852811 521765085 483980385 8227414 590991277 670172083 100 407479340 635255551 904258176 739070757 954826324 787357974 575045630 161703872 990443321 116157127 971902929 896956913 953339448 11734180 421029094 640150898 59616384 926013386 806787167 451214020 514447868 260209648 264376523 685398976 877185007 25962171 758948983 66630231 591968272 53959340 881174601 650834504 859565907 30046335 384237366 884072179 136492742 977879515 576442558 66908575 4595355 481637830 985868770 524822629 401739380 415454221 382948211 701429003 421258771 845405043 737580157 917104937 201365245 299281169 904969877 660679632 207195061 148461113 420732116 543127609 478291364 750751779 293608395 271061260 325233892 142385436 760693120 480358355 792526614 235266232 153853908 681651258 187310235 729643284 555937409 338992649 515506606 789128916 901367351 975338249 152916519 886246842 88441861 656317569 841574815 463518020 708381847 478992983 277058190 172831346 896243820 545321818 945630452 130666019 752818211 962505032 559401225 881340400 85457020 772254286 100 833765790 588568895 610665434 198395314 140164121 951286524 865118742 29998846 17586867 42427487 125859306 926829886 429503928 885026664 996103803 211639029 504990476 602871693 124582213 95422459 800662654 851998760 735445095 684412575 783963152 106719736 236863022 624422343 872422868 88840845 928796260 380129473 112061343 953291901 460369047 914272231 731555282 787277883 725757369 953249325 62647916 642571566 393986116 46167223 384898996 226024236 211575333 994367669 391729485 727866313 445684075 808840447 665517152 149672450 312271941 394457052 639594159 311330136 162524070 373025041 325000457 282964699 248378497 439868107 806096033 95242632 341852889 497858675 919489154 436575515 594556785 745522214 182649313 406519254 259967573 990564737 952232064 120477862 893797589 250916058 541134257 428225071 415050362 242025434 526574645 961203668 297346846 399970289 373399393 503628846 29161493 501048233 552862829 102762219 449264151 120072651 796506075 382822786 429783449 815507375 100 298307692 682935338 6288049 465194334 843724852 250778351 122257715 69927510 701863625 722308848 750105798 781740903 262893416 267179118 530747554 127622677 270221117 91810742 325427349 801099703 519170780 982514665 327774056 505425812 764104102 441304916 560495932 894096457 283033543 462078452 828249512 224808772 141757954 345706058 175514797 567871694 866202162 405967153 659487828 894342891 274291842 420419378 983656790 312798722 250041995 507025853 620078584 311276290 669071480 108862209 664794938 239764789 440244464 379694326 507651956 177186404 630709969 879273432 14409619 530532097 779722733 553295236 661961892 281351907 318219513 732709342 266678978 49095776 546100919 637750879 423961202 908181895 894992976 708103702 688145161 572051896 116913910 856056893 430491827 55138962 722201551 512028437 473946621 12351286 739971895 865649411 830479929 259900974 597856419 996220549 393078194 466455130 259290842 502107485 250668192 779916678 918771492 272627982 273106574 998933335 100 526914020 55363811 940570462 285087332 589449781 782023374 712079941 189760295 833697342 685256107 484675346 550026544 236847496 774602674 422135328 800669312 702982676 294267758 886956556 563770647 639773672 403335405 152190841 128192537 870567295 825074535 717744887 957835165 627134983 500645912 657891437 515087328 647763686 568460698 442106710 468379185 508007593 512164250 130820286 342984462 918845811 661137792 113546002 977190024 152924290 735031959 190212127 339662533 27665467 494053406 707908333 297458355 466385664 5812363 359740176 791330014 433303546 738018640 900371138 349430512 575425264 128904513 820042909 69516311 874352342 261670892 186444606 414698873 384960355 355294470 140870478 503528358 81313816 518293707 992108285 217103845 259638698 892699247 773728118 798000947 883037217 633629848 123445556 568142917 621071147 664030210 58140047 711240422 534060139 784265325 506988654 121206079 882116282 64367942 139838522 887418050 391791339 169655771 10682460 789788266 100 197618083 662085208 888488865 447704391 738731084 788399122 580069647 31378369 490317485 745243017 811681187 891013922 425386899 908939433 429977363 428060476 886818197 660645041 483678615 323080122 531586977 236208514 906789623 779036482 78679385 420872913 843480855 857543064 933919601 47496992 251765888 141670569 486385496 787589707 45099551 672026760 989982498 187110643 3464830 710380860 86774384 44281372 690173761 569140592 924790809 210001587 123742166 359132822 542571375 760694557 421282839 254692898 987766674 793274606 411535030 945086987 658459902 946395838 540385910 657717582 704962013 177181473 241821774 948843866 928158007 90189328 34995002 744923054 470971039 444552299 782798663 643060941 921405476 105444947 942022091 437009889 437453849 364723702 153371441 379089095 86930369 117140007 584495651 607232785 746710793 242104229 590804091 672993328 760932136 656994172 545150760 977530001 116856133 290742328 276223184 428467262 732083415 604852654 435500115 286287137 100 258543445 424135292 6308998 7307292 92495252 980607351 561170483 798181037 549780129 141642118 65522766 330103778 60120750 279363552 911074928 394373892 763361373 571210699 128551540 971522265 511534580 541174327 455313774 816807651 335350466 685453164 391233058 768560210 399692055 17629003 717869578 252714701 660551011 779625414 257873137 876324191 681510574 589341453 674118528 770292188 833908505 472167553 595267223 858071996 539144234 910460545 459310812 895348025 994776955 593241633 283726953 654913335 209720255 290101737 380302010 824822372 677796650 865693625 274842640 316895182 159656334 762860623 41103557 939895434 376491679 876028276 744474912 665536218 227066497 336455206 718413924 660857691 204922724 615182835 298245356 275427178 746688615 48918035 937170785 939718599 18362688 633937993 895444474 183778337 340981298 810023664 640658043 440252384 887609280 370847187 792645311 690334513 33288967 251499815 248365064 317742343 845088660 549913212 366091939 758946360 100 658006653 562632916 988314895 355631859 159919566 967834702 103767998 833145084 714291892 706457438 761871775 790610852 478966319 542253197 231683001 23531812 773246922 222740051 943351108 443585107 724523705 688653543 34469017 342240751 499992078 22289433 439292035 112816678 66757500 553692621 900340368 166568190 185384547 986801673 180433109 632831211 349573360 284615800 89541901 586481063 988027730 514152714 675188588 134812901 615648721 520210124 429185982 409332786 78208824 430440237 514923282 375139707 621018312 907280328 841109213 974817439 338598388 764541835 698773700 79626547 646738258 317750739 855905560 427320464 648804271 343667639 425470762 107706249 260427162 353867561 880481787 47213486 996433527 213536802 947986302 450898193 966537498 104378926 339836497 495728571 633926098 586037782 746064952 471627004 62995164 223080262 264308798 778994644 853373562 131891546 532575919 569378346 968781379 874181324 241524723 76664287 702910025 396281227 806663071 248419087 100 799533993 499102638 487041814 23449321 281318987 8762348 654524422 414637564 614726613 50621269 200748073 717425066 787848837 121125742 988079436 222916112 570889351 996035883 664552359 716959610 847860889 13486253 528287107 539709346 620776570 915836503 770151126 180981374 108037823 496917524 193057788 308216446 634684877 748553608 748243114 931521135 845588189 929106470 181584086 178806677 602004511 643565192 524755764 509433578 613575510 933815009 546321085 493141617 52915180 985009028 580441387 927797410 671495192 696365566 423176486 662724977 830412346 713088634 578518656 484258199 646239324 291425626 50823428 779777041 325217328 41583462 549614708 968992356 942308439 274217951 992118409 989355320 479148971 716001117 366574218 8363667 843025554 301425164 287483461 128852235 247162981 360419769 432161702 820625055 920350536 987186295 181238862 400940089 507524665 753975815 743210701 529782073 353933632 634050295 823273650 448519147 508880009 868194670 596272335 986251025 100 840014108 942574715 152234070 980237192 522028884 384013967 139868907 597266694 398257784 543942071 113640668 55117510 128934076 520240484 162713189 298805933 190189252 455609122 629486653 274280504 480883358 969688655 729778067 32409654 46376124 931135485 257023152 778513178 333912796 797059310 605677419 744861974 911327073 286323687 347321459 178381376 344977205 332530466 60274137 258938594 60654721 788838506 621591694 929773478 329745474 29060337 713520072 624861593 957421282 152198469 258108825 941780871 869878252 15220806 894362470 519282795 662313459 388050226 434794868 685725052 79436442 99242787 994371259 511204334 900473731 872040821 787322084 459248935 326071865 772225206 797812790 430216999 107526060 31841636 402055931 412050588 273995662 5040517 107909924 944500028 755306205 884347465 693864918 974931037 714001510 959563024 209628542 701257983 246784911 575750199 620164536 728244305 644889705 100730128 221265443 229953576 965686703 173783305 418291351 962730697 100 401772645 839160918 215556400 627318348 192545352 33194116 840882401 3611383 12168518 859277432 143811145 243920222 27281810 562811525 170112648 236285965 816222023 498682670 770068860 78005290 915846216 919626255 986031782 307165163 321344958 159014024 666561021 822886088 597831294 455477904 638679160 464991868 702714422 225050338 270218388 684273040 686962510 307902074 15021634 577301225 321201422 67119020 647512946 927759992 661301746 995318007 684145159 671470783 340220610 49803316 267808703 541885997 10169468 205254172 459365747 434539082 799145721 636548643 693368373 876211863 572547023 380439584 983488536 391755300 992218624 928640570 947685644 939375933 810327316 256279010 369094553 395089501 242410453 91375226 749646735 784428098 214145855 511114911 761701147 835001891 360669778 782992759 556290419 529197165 359116531 474392536 270401039 306111360 695140264 757214659 687371247 490511164 107188784 831474641 596883393 993327307 754103550 105201879 182765611 508266470 100 785169595 941517777 940320098 409924286 890965647 334472867 373385915 78713907 266308937 712663682 849144571 352514066 757184806 808340791 260163851 428153734 165346208 542432312 300621441 676648393 512350441 373891334 258923133 873724324 963573678 223452884 698660198 26272019 366709815 408485328 136658699 11526350 278472026 16874337 212046918 328360726 690692325 436193541 758732220 252409966 708783432 726361012 782965675 850147083 890274367 753599200 958626437 197259318 19962208 475485420 68455097 353394945 287398564 561573880 588643177 197409063 264762325 731020145 640939055 76217061 311967916 401454340 900869901 555141789 181839470 847807036 730344384 18688992 332464417 801486764 48196781 741014423 967784044 518001547 123896593 922939633 84051837 991495863 375589013 690186712 283592366 600546398 646932090 556377407 681559948 682064483 762329644 282860153 761599525 547675158 771603057 942939110 748527488 934164698 740655735 397933910 440397342 931831230 93153880 934830262 100 848705811 802598717 60560234 547798709 228497760 199161288 128435041 821431658 742499407 993701990 707349723 447566044 751997872 214899069 403824642 854453360 72205403 878225203 830924100 682541061 935310799 742446628 13907828 183904883 362888691 313927143 957778288 168452297 287910622 134816346 611060018 307247731 182989799 741784626 212641016 172497684 778753676 394519325 105334431 541266718 703418010 990286378 27174149 102406116 358382159 694185042 572060325 552889741 900415784 840344048 601138877 350814118 160159574 627248900 696639865 650929904 190096820 247981576 659027908 830331402 551006989 507240433 160454894 266072730 74873137 83300481 645532189 452653835 651873421 694390738 819590081 335187325 839653581 553175293 460472612 664776038 311404086 569487893 884057320 733067798 6549127 255791688 591321349 948709458 165719502 338061528 57758354 424071417 624820397 516970336 897054886 872855325 44827733 635939575 294325286 488724831 967714206 694608179 746405723 961740605 100 598608328 408128022 417904695 134010641 397143073 795795855 667644220 285782729 422727144 284629459 522019111 541823087 497880385 31507550 313147126 848086204 890500303 736095718 886189598 994247133 844143543 347088210 598196776 232475865 28059047 590868338 853936623 651447773 387102763 212051250 656088310 560774986 654474962 627637791 861292710 60591280 752296101 350277993 594534018 786827413 719998830 320095137 149492279 403150563 263544436 797666297 123377400 818324723 86661476 86773462 562337209 388404831 872683948 563442094 121289047 799541930 260511181 800566248 798079979 727934967 543812343 425563576 801700366 754842999 351994302 462095048 498050490 372561857 996656476 259535025 915779577 102639261 292574584 323472450 507825075 990623345 867912904 236151542 588142915 503902753 205021651 133092572 560006810 94988084 877789571 129593818 733441883 702565776 399814200 690177032 504483310 420154609 750869186 967441058 128360204 160311099 617132823 408889069 982373103 892910199 100 84072230 183856957 199518201 81100748 784791789 985167186 348621087 492365281 546096320 495799891 133467010 577910959 816761189 615923086 66348969 860020336 850529447 720696808 794807596 836871744 816032753 254779607 594953482 129946346 980117985 490380054 958267268 946431198 809664842 755265088 600682417 610881231 111766000 679499920 86736414 911703332 534483097 945494470 587840534 178166378 239048636 709101438 91665628 933167176 406768549 536558436 202140258 695455295 292207387 613743037 302398828 311227639 364293227 16153518 5852417 826492664 930978351 967323959 338359819 273461501 799453394 860766056 377132380 27993569 121637544 378968171 245903194 93199388 920229172 580941504 418797629 490253169 588276143 337365350 250485333 13679186 96058618 631278984 870906629 846427373 376556678 164244406 870764087 956201349 334646009 330819212 796601257 468331072 535259787 596117557 197081155 695049669 821291355 842101173 59033130 442836078 731407750 607571947 402805879 574631801 100 503050883 809453632 351591177 209522741 452411817 501520144 316843908 932832296 971533615 967579724 789335190 267318528 512407056 195781761 709828242 275941911 628123215 619681244 592192326 58730797 458181526 466241070 747277213 671382262 18050782 752907310 118022977 891516556 936743899 489572664 447692588 503765059 51186583 868186603 471138669 632473718 823294095 983046633 570576291 775396473 220984583 570838142 875427866 450108296 476672390 81327612 28088388 554043960 783159454 999602739 250163722 993248869 481330328 249514857 721977609 768286789 965461615 180240317 871232767 262989680 744093860 93000182 17365682 579589551 548019669 385026631 627501001 936907306 839095602 792884675 449199414 703090887 366107081 215827859 554067982 40928279 33340918 946865313 453747297 848596834 109624220 256166424 510806833 860353447 653161012 450905368 109753619 378764261 693278800 702820094 41517278 758069861 846808397 490916677 369849607 139912726 16876306 847272290 257342292 790022648 100 42663349 34889134 609706801 287021702 412573271 822960044 685877806 348485411 599101310 549362559 255907280 909075280 195551209 842553598 696293428 920027987 337472658 432363289 378298833 190519778 627247984 238667224 990029735 714271433 756060360 582264307 349966980 676237972 935376558 873209456 920510100 212659373 99074057 166886038 857200509 912924067 548432172 112668763 874413939 157903670 744684661 127609112 758763425 343962547 604222840 610159805 821032157 767957344 486641735 34107485 759480208 622590446 181501808 376729009 73188078 342375173 268870324 973803247 469432305 858694350 255630735 854703210 410298325 623432092 662612885 315683257 838286776 884570777 142039791 471925000 640026049 46714895 768581152 319353454 808990618 582837837 849899386 556978705 575397705 217663835 272580859 911140192 241599426 709952626 301997174 776707253 81615658 715370305 241823501 166050355 613290322 987328071 973156516 486906901 796159177 42420875 800952392 667632747 434736923 66174011 100 324236961 835658142 692227700 436226513 464541970 280807638 940965711 148415892 220949231 754547041 378898415 598507941 954408677 674709622 998777170 286602189 427451455 819432277 769090792 919550184 871336538 964149215 865783983 786898467 839344765 368033307 943540698 407100085 322427760 743990558 722223390 505147790 100680757 478360277 822893702 364186541 734595140 297526413 663116860 905101633 196912907 783064491 666287159 589968048 995702336 664420610 648483799 56088913 945084709 112103905 467425639 433875053 671246588 360252079 281427848 812781108 931989867 563003402 784318524 309965997 833526064 706053760 313838014 698512360 300482004 391125071 443793197 752478939 470698944 498107411 239888971 177863247 397416423 520642229 379338309 924876738 746032405 541507033 917600643 926691363 413682189 88963955 340616760 801351156 457920196 972937416 406288214 80931597 765122791 119810515 353995171 316610207 723264050 152651313 972170715 767001563 589150901 14631718 638284663 604747559 100 613452142 149581428 478461921 838575237 690706218 823427040 404234588 645262675 171567941 686487687 611344740 932003952 28920097 374060324 688533595 159175650 681619329 279272782 628766909 338002775 452768228 801902544 656126741 284896587 228966466 919439558 352842709 717003450 446553165 799787109 602413088 741910478 714659307 927964559 134462430 737631814 149253470 832372356 11718904 885182389 549230046 577652446 115681370 856961735 122943970 213772512 596680295 841473126 78919594 515989875 880883900 696267369 610604957 361681511 358813994 829270778 114268997 542236632 421248073 406138190 915903513 801796651 645322061 192626915 716471315 103225936 474264195 169705240 75545228 671954781 904097666 954035100 74555325 474892345 820624997 804909374 831673387 587251596 159188034 804122298 334311356 300496216 148048948 612666763 784865642 202285593 267263809 396806549 652620304 666800150 309587524 414706435 869598161 247345492 501937880 137166081 897294789 613501317 298669683 829109241 100 529503357 200417752 755272978 717938659 68076855 58178156 3487196 177389587 155396208 191409230 739798442 124658417 306715316 14376804 837965193 818916259 935070000 598333176 831588956 475387510 305266667 276996150 744256288 87610964 727731742 893346176 976039499 869591477 119707968 322489042 253591414 410746870 469400490 130259038 395137839 858453509 939578989 7756685 8900490 314318595 2091776 408093524 689627594 470059520 505975054 813348811 821857783 144660133 144863157 478435742 88388135 893421710 338674552 22541030 163397084 35908680 540348325 948800619 451192058 616759819 417549914 89218922 541901410 221125640 407004242 429169649 886249401 651771269 538902975 322176832 376006331 206460101 593914265 566292983 725731965 250471535 511042105 837463539 761947440 136441521 260701410 338907998 413661610 299368356 111737010 658200843 377922700 514314989 226190145 833667954 244696313 438258481 936324881 453991627 645767619 907443755 156167269 789601937 300229094 947468995 100 301124691 270983714 726019626 48527112 441459622 84996283 682734642 596557726 375956391 240268457 95852990 826853935 489897647 150354020 104465721 237333954 873234801 824651008 718303908 919560037 306042729 985704008 874437836 943329024 492419658 123994117 431575227 884874498 690343593 65839566 411319664 865026688 864096561 703103937 471166743 508383394 572634637 591101055 327711604 964749254 662957254 467204173 344345878 918147319 348089541 419082442 422151714 262806127 570818330 178411928 893947262 407204165 280892508 4491659 862873581 125236813 63856219 770847262 338654997 2966070 277688241 62234498 972475776 590529734 509226463 108112981 590724144 172804490 90544523 725952641 226453859 411710048 284833617 11622161 339007802 130442929 520589817 64013343 98212697 747568462 848437754 789792859 693095958 925021446 959114061 293128603 434288153 486222386 594737539 270384872 640959729 282474631 783721957 652013140 830542986 269126901 27974792 790722776 168061857 97567951 100 748437511 514439551 258429417 732737515 910238161 803255423 779662201 295428345 449630275 500745860 510574621 990004845 629692548 123411651 883979616 110556985 389164302 749442398 557020636 364132085 878162113 688802830 65412059 830705371 880365310 861030479 901322765 769553363 519557074 970097934 845003734 533380893 439986322 851996412 202663199 974816249 672032934 867310594 744194881 729069329 393862338 3837555 352583780 444710461 73234113 760592238 922821854 514522305 299620208 671146331 772772139 114632485 940754556 74643859 216498863 382107427 470352783 758840027 707958330 440461871 100818324 394273212 373320278 350804628 144520767 186939204 27991631 526511312 197593005 635368209 656527821 890501793 365385814 605081040 271515290 647748245 279569636 506051416 507595242 297084262 735004566 711737854 185998894 146027936 158575527 796318686 941030771 322914787 400334885 364832946 587843595 248470327 877858270 755999073 142159267 437574251 8761307 464224489 808505330 489880338 100 889989360 517635540 580226043 979146577 924098960 902412816 957145147 123986923 126111752 976581563 530415644 887343738 401199143 833674653 233206506 266294740 971482131 544730625 154152773 262442663 435581665 669005927 700655984 306950239 935122498 657135892 295494600 771135593 742229031 605145911 479346325 900075682 571496917 529340901 847636121 969982282 861487254 4956589 114535061 246110656 920885077 860116855 670063555 468681842 190176590 762708261 498967917 880548421 311002071 377182522 120550111 687981935 457723396 333607172 676109677 844569610 173629750 887358903 309533370 4599176 5153521 494926575 956132207 99732694 766558219 912116076 647379532 77027637 238752037 639277077 340437642 324583002 387305440 805165728 375422621 451893991 607287060 398244176 158349608 464828158 22030302 423964364 124573049 776561468 976706505 743568963 459316704 318802931 187232184 109098616 46451603 167563613 246282870 87708548 903074099 454278198 881949983 831891232 32646446 404092914 100 974441768 650730614 127705744 66058246 981943567 670463648 217835958 340171112 363094348 713514841 863382155 451024640 940519636 448268697 270691607 751842159 942066810 855976261 665281818 450233856 664271967 843546270 758004230 424935585 333552315 700136048 993064899 558823121 991587324 520507562 217388408 439084118 8710096 793877415 24795367 249218331 338738314 33329478 450886358 742385529 739485706 231344426 362589441 395505123 301337026 421566747 500697335 444593972 865596916 583991008 760682588 620025508 586566142 714096023 466033036 393009143 657009449 561019365 799109970 174658403 495030071 356256860 754431712 162094090 70565448 977398722 50008174 405161847 720935764 957869217 783472279 342241338 783888865 418376153 876586148 749380906 968230856 236514133 332726338 676084703 86103324 115185021 139040472 682909464 553849222 441737289 17992524 477473739 741145797 692123768 962454618 795279881 314852074 244144004 224323771 871125022 50912014 984646741 367700811 611650275 100 51394380 958266254 883469796 304991555 19950357 447670623 464681669 158205990 145525168 652916019 56857166 851966782 572855751 949613218 787777593 435156114 25165079 129305351 735806021 155999845 219576432 88231455 696732752 679651264 988271807 937497802 15730133 650522447 107734999 385558310 198934789 260987119 215530690 926108875 900692450 658481616 898135015 981556866 75372200 311189113 22630027 66254140 703573393 937464658 70485054 576288629 84916861 532313732 219343896 372876603 975102709 422890437 760885361 909466184 615340918 8238600 193477709 733557040 100802680 92831667 963822009 328587731 269700839 751513514 560670142 922169894 420431099 30987781 309390627 771406631 411745531 952826918 186408470 974290794 828838361 575959387 385973438 364557955 837924502 115036749 837637916 679804114 980673901 962429761 443096394 483754262 364719403 679255074 897760038 132769737 534935936 81237337 631832347 701893353 369094373 295669311 475041159 650819382 431789814 384785683 100 850824256 438298124 906652702 138498139 226788073 343356777 379811720 383206115 881263414 57321522 710262388 743945422 378097018 603755164 761953053 86962969 929969672 305404399 162850954 158555521 35115605 796975182 418018875 533780794 969368769 460633627 813444491 441123042 450827549 979982704 626934435 358312231 163197421 653711183 899766491 388075721 678725220 637982300 303299875 934432626 498388228 277486642 321358035 547500320 233814855 825745027 612294083 188220684 574270309 510831069 361538101 242396492 169059337 424580339 146689010 828527264 777803320 451009920 538004296 832329956 546451495 886082933 404451204 694461626 408648162 359194993 199371266 522966295 896239084 464060197 825101233 293654493 641551971 631197098 928883833 525270092 54152645 585813736 650736839 95879643 130130325 22871373 653989147 981294247 950868281 264499794 310698235 884510632 334374389 522136104 939180075 938154042 343834042 623504347 383829253 503071496 447004558 179116768 541706515 126919225 100 881156553 154599547 142003676 626270872 708535111 293071824 847275597 467434884 595431009 594854109 800673021 351840991 370127607 866394056 552617772 502000614 383066336 224862822 448306509 34243601 493365916 280733477 438367666 874033332 53911469 378755262 721208194 320263654 311879345 250092204 776669751 200580398 991811346 18681128 576171837 312975409 939768121 774890822 541654989 541096448 69147307 424817664 426749103 264934752 119107352 546464038 784115523 732024330 54172438 617586885 410110156 4494343 502948046 600935948 963139802 678799195 263815437 513690350 482821085 826643140 412856304 580594264 218338090 108315145 98100252 181227950 43339542 502178392 864668329 388559175 55338898 224427829 114031424 4811956 870112465 569874740 322286200 726590147 83297546 83473610 594442034 360047371 575199675 989729346 205324983 33612347 693108359 450661390 343452285 605696361 884467464 860653522 231213673 413351435 799325146 608205394 281217636 317567640 101497895 591280492 100 238898086 789478811 671754781 653372858 953812102 606351842 747403936 179997360 45067565 683540741 236268512 838254249 109126222 879504413 937174642 929062487 209177516 51151444 700205193 282359695 628036830 81695275 983107004 69766234 539594279 700979922 821802233 534114287 559406205 369956496 508475132 728329466 678029323 228961427 917181060 59264013 249838628 720086235 973707792 93196113 657136328 346935208 962061588 102277935 992680905 849196793 129354469 764074925 731368775 236781616 247190260 271642913 360554564 736390402 445005613 360666831 752264499 765046236 863209091 674879903 180132928 950688852 350512783 157322927 863247736 150832645 889449387 473523077 923114829 435755963 982081570 554057422 491120351 564302739 12339091 471344034 778030953 595542412 336792513 892415011 288442649 116977781 600506554 308798270 882041620 403798800 369913853 159655077 804610326 905721156 358330678 385267949 677677464 877316173 207122899 371094317 519097354 63249179 853281595 709556905 100 191500388 5516352 781349469 834870013 142235445 763095169 980477394 914101824 278457611 159579938 59889306 150361882 239356117 83427528 970069313 139698523 745075742 998266577 930973548 19506844 215316275 649377199 928546924 736298270 985240391 322708715 450758488 153393638 930612991 821228006 725982415 122902361 283143956 743419946 814507917 567146612 763293470 931678418 411075515 191550473 166006298 923354213 525951741 425872196 382988004 591297279 163711104 155591423 546239094 78203096 547456102 635901723 568255120 476278050 296505105 794677719 531934596 181941528 415790331 252342631 935230972 371308826 773820595 234784730 470870331 707578099 143970584 355496027 150067802 716108072 995591831 915981709 433563172 475738726 598403755 812720865 584919941 350309476 325757829 536127920 213103721 792865008 440516801 314048901 728967840 504763888 444378436 472412404 95873140 886751285 306444350 269312637 105163887 577182936 633312850 838444467 719644240 175711968 250447291 93225218 100 377354067 294624633 716268214 619715417 317970955 90363075 306244922 379224892 255453218 807684718 6058491 783553731 991866244 826781194 811469507 767247106 528064787 56355935 138233557 696934959 491750818 629951484 756389832 98976271 138862889 300011646 610530978 708686682 336751546 853450309 747992661 483973101 451486739 25070526 523423565 369614642 728946468 549277906 2149859 946860344 510480006 472004739 486508237 201972774 546458487 72361126 23585215 791168625 421120732 395366577 851929426 150113155 738987867 206222364 903295169 852413595 14354797 774323156 461817905 878206512 228585248 580448780 336390808 387722136 419542407 957721514 385386736 309503095 563335359 844876518 326092797 514683561 240973703 418780868 180769885 755403458 473448270 282021816 334618492 300791655 820495271 74387240 56551651 716147765 352155704 762950583 497299927 131741021 467666335 828600159 372132973 815237472 524259309 747943297 750059889 453298809 624112698 288567559 692911594 985136552 100 599672105 361009399 21269827 710540070 549255116 738695759 176849803 171190454 496708402 100716123 14161004 84113040 123307336 343748349 976611316 686969739 834665342 689221121 809502043 953716041 599211665 764355359 220104706 69353838 112636456 703022607 816549624 222273770 803860633 577289923 218857174 269553778 42710581 882955145 472439476 178518444 666104145 771144196 890326867 511523974 492919773 208784624 826109764 176174855 791272815 187200204 339356881 191395054 695371831 820921055 255430670 86293623 93679994 326875254 570714172 823494790 339072232 228465484 803223129 660903472 226468214 816894286 409112980 867953949 560599318 140679657 168246918 767387255 743689711 250686714 102266059 568171313 642049042 909534556 222273478 85633064 309468315 135671943 370279912 862456059 863092352 229437511 461984230 822364535 671647608 994912783 776559275 344524847 723555460 415091444 52451746 554146102 917624372 79003195 179543939 334793608 387657883 264827549 282710130 86132264 100 416992967 332014443 890061458 312095388 942238022 963387785 213572774 935305064 770073996 130269144 788315906 719157776 967638981 354126527 542671462 566938339 448142766 44534174 188304245 42115980 126234193 563838771 286727807 525469555 939366908 623033637 205320717 742229252 591147075 178056732 605357118 962210914 560586601 10742451 551261941 684747945 974246460 847641115 603586432 802708572 761459148 594244179 309238996 487552196 858281647 203349710 303594598 891338041 156464897 133969317 123659931 341598570 886140983 294598603 763108620 533353857 719257005 398542089 906162427 140923937 882421623 284224257 534452545 496887089 44760419 703174212 560389836 215475775 889252141 355696378 23135997 523217548 100118378 37195357 29220916 789483584 677978182 872854905 510381334 249454089 392470084 458674199 541858605 476544743 893398345 86219897 549414915 597672464 130062660 374877745 482638381 307422006 36623934 271506993 437160907 121919226 310518626 314889117 165621060 95292115 100 112022864 235447824 861570009 670579759 316553492 313530621 973627063 971813802 334360539 768640934 101314276 398277634 213202 270184711 816615239 912464154 672609504 529881302 760510462 980431957 259156135 247708187 231671816 808140505 624434750 134418650 539380659 888150666 315660726 317743883 232949905 625363185 729835574 370988713 731854491 343273755 707987105 568081370 244671731 16204745 547144247 666952411 174502810 309076361 834167206 967557071 64017467 475552126 899423415 395647169 477375130 69511511 258045339 795717893 347470455 681334117 575974488 996382915 250377618 516531669 443205142 418592138 873082879 357588923 916334077 99171887 845704051 689182067 25344650 754873642 631017976 719755859 968690058 534697810 63633154 289623061 911216871 981669549 893739165 773876649 589327435 213286666 428311879 412209723 437661002 136574047 78516740 475497745 824086987 953032783 463916548 722896317 677059253 902575406 562973252 658516062 543258066 881459848 101133950 275444424 100 597444498 609995 322586158 207369419 974993801 661950033 746615518 982844498 512512184 102459533 285234451 597230458 967804103 228747737 673245421 795790049 892468557 556256884 143652567 339914689 150049414 617974844 910053070 868432249 552050192 966147873 347149318 628753875 597029675 741749168 737376758 125963045 756904522 652567134 134421894 424187074 977739456 753453537 925363852 139892802 96785839 543785675 477281993 86078869 556084778 576730299 814267380 912755789 619082628 693286814 748204335 836831034 666954874 985778598 109755774 890206358 776046334 568888548 213577294 373501337 374080694 767564568 828512613 279710490 964324880 729808417 596498708 309312214 883665902 785093063 740769089 690896990 811517213 585935470 789741324 920177675 164963471 213173562 188412294 335636811 190760470 561452951 511232950 885825665 72749744 136345024 438856095 743221849 962262902 725680534 476629708 864414525 420071392 704738305 403384880 884534059 846902247 374936342 338702525 817812256