76 81 211588243 258750393 342594077 283932221 789259328 669517004 750507566 73100717 25411714 317276425 589996568 448179635 202195258 484496178 971154220 137108976 423447109 494677660 239574486 785388463 183287109 931569738 848900681 150712582 643741731 564426118 623581491 607597789 216080851 337700432 960175268 420981052 590619431 700470045 753762333 876987908 871605351 692278941 676966816 744413052 911636825 724259574 181827909 934097335 798136168 920513417 420007054 398675262 3504939 917506500 261014442 692006984 997322358 726021251 199128892 699358940 984208238 954946659 991854942 760120242 81356595 76790871 522482530 727804561 242131231 64528156 740441679 984844328 792276938 943592731 23188062 892955647 55899480 316644493 94344302 398529655 730226614 872430987 955663537 643161844 601048634 85 599876507 166265233 457524973 129469297 957715265 321807157 238183751 892274643 664872737 441918073 356760036 239818701 978710641 76099235 629054413 398278340 862327030 434998307 447181235 759641398 758544634 621413017 144785338 770250430 539718221 49621394 924573534 755602167 450236866 363408315 393661042 229624468 90423837 313500507 398906395 142496404 481150934 515920818 128415870 633413198 636997831 429908163 481342866 972250014 377653103 369561637 346932459 914853423 284388659 407169416 104814271 850628992 123392456 215263004 310082268 364122153 749832757 50365064 38020626 114976788 982843352 86891653 709145676 981365349 628274227 346968363 35166104 741047078 23660580 516597058 920441201 429193596 933472163 429638716 999293477 549348015 13640905 708793667 585056324 618142983 335498916 676729239 812422334 966390549 457923108 59 993015891 580970486 588060383 79507012 760668415 838830948 726303551 155126856 746727484 159883838 778745115 39913073 562497098 269524424 270869159 81338941 507510817 216038517 587988615 460947414 751144377 391267900 830650873 997659004 342072580 263123296 597498209 24901658 133904352 198330903 432472638 602627086 157070778 717269541 899572861 318274322 346684187 938105932 213661416 617607696 919132172 123265554 423497216 391708189 473842822 897075871 832551562 628139505 184547277 197544751 48593131 545687613 302211272 892214049 607072928 755557456 380850574 344888850 680334889 55 778145210 264598583 606946170 237196268 562588424 580443584 347570132 878607330 271073528 172643486 553594392 415737321 298441697 424051558 377051775 52600940 518770710 254133235 892584798 898146793 397547953 704962143 945482824 667236434 186692958 39356954 60542373 356331841 851960190 603644937 378592403 404170396 557469830 141464771 10061008 271216156 150310721 838324197 683563125 686945667 56849471 364250066 409174743 39114346 849330099 13136010 610742812 704242664 995717254 433151079 639236013 435825073 533411363 164180363 345346163 64 806754014 53592887 781779620 863180506 391482838 925073542 372525088 876799600 906701123 526017563 937369008 737742710 534227549 604085377 71087186 780786940 294321589 98704532 632381163 865510073 320469528 465496435 83371862 200727170 950434951 204958799 18307639 851291422 292560096 9344496 93620113 900743382 24098391 297895116 483892022 759000774 61948297 461469817 42025919 995747932 115182411 272481260 569184087 227661103 323466045 205576608 340779974 268420146 381164822 141430077 808187667 273837579 813189433 898857459 801651648 467082349 297715772 126354859 647586575 893303519 973964844 467415131 424352906 328687263 65 701287259 541636784 99580644 991605425 910715829 298637608 496850995 781062766 151170926 375998936 34837439 129300225 427226680 36102702 366500506 415462050 341270531 895043304 298611218 506953914 591952442 181444346 584351476 978889144 511614053 571343215 494796077 805530009 653623866 518882804 798280217 33708412 13636746 889376838 197259663 980055120 198021263 279096909 495143189 440974979 51203058 606578984 847092521 286030163 703832775 877595796 420172024 227957343 602794963 507467691 313624450 275707837 252852856 22436314 551378692 256901858 415165701 275503495 681008121 507615351 133036365 537436569 541650241 322766095 226326918 57 847195369 909795041 667593663 419826791 203975551 657624210 259775923 655702043 212131851 869416564 866533899 430662468 627895844 223048579 901742633 10247655 596418668 28879177 712035709 239798103 685873072 948527443 436427663 22413867 745357692 647162643 171750320 983857103 847304090 873202862 408258207 226692068 704064011 208952348 567005321 198571537 825285832 333822110 70279269 211363572 142314730 761009556 770911544 676328097 943141679 583961467 924043102 372638056 795435763 943094799 997123567 849459676 100932009 799098388 116237933 441417428 795434169 65 325723887 120939286 33413529 755432059 707775397 327237481 241206800 858034259 30295640 876148051 602526901 797267009 820801611 859999415 160047569 74746140 128963186 131772218 326221053 561688700 836550266 470718642 543386731 781168605 121590320 363729878 281721047 988032428 899770965 57643495 400283124 399039990 863967484 699294076 140169692 400850183 804809404 603385055 158435428 749025245 113668833 498328238 129767513 457889789 478707535 73675196 161736225 753912538 922699577 361344356 618075771 294071458 751951377 529898730 993934190 207391309 547494042 366282690 564796909 794108846 278670792 127295004 272476420 252241655 137465209 70 411108433 64180102 580155550 308566412 204444535 491186552 373843004 542036115 591928479 527147005 40550374 319783799 992583593 174310544 173570545 773048160 175287850 66733505 788955480 335768499 307961543 460562389 930010168 852652628 287736308 324791702 418435872 908016377 54777708 724864645 564973173 417446897 172577931 406521538 400603503 332220325 877632544 300341209 732828520 983270904 267137864 970756111 455851666 194629453 900135139 221308171 516471093 546912222 281938623 473220718 466583588 130772179 195667122 101070129 847727648 146103694 234259423 151199414 155613820 109534518 8076759 930314113 413246332 465489176 483661980 669179910 564118655 827114601 357770932 688566190 75 60818772 116871990 550339501 973987598 887502490 290470752 209398815 245126585 221525976 168682675 52630571 934227497 475417213 315639492 935453315 850601591 115666243 582122203 435382044 478100675 94710909 665409606 825688533 734165536 767629894 798058779 598540578 347524835 910645678 848438491 456904469 648805943 365703875 303785974 201402940 787315901 178913346 904726816 675795589 104761371 653593813 678147976 585809858 966416148 413154712 911177766 822055499 561047168 756203528 25278785 354914121 637970956 241449512 237228526 796096163 956753303 156478667 733120535 801026511 763079035 436413295 876453655 986399393 945758278 395759854 672174236 723846294 251882530 525593292 434093302 162957239 316236859 911647048 991523317 785288146 94 537880196 212806975 865101837 152442052 665724099 968051710 941432098 204409884 891579727 927189274 125081861 424012339 740665164 624757429 360988805 884143395 982730808 590120159 863004288 558882744 799434834 973887995 8682841 789794776 774009835 192513316 741138405 895841557 919547801 323830242 724599707 851545444 183053541 535301834 777033991 447852044 516670459 473432657 154261553 351686321 482200014 128083212 755403417 857564628 753968410 725452684 54876810 616770035 274027304 778797951 520758639 379034931 923404199 245458339 112312708 997344267 435826057 851024049 56059050 395011324 948719579 17444567 732241305 643510851 633674540 338867926 342938903 101630610 299550655 702069184 55341544 954537640 525163509 848664703 848146714 387401898 168736329 716181645 616537321 22647793 741011896 619333612 995014868 284523621 378030180 218520058 602371394 765506890 895076183 363992632 460255050 606329687 976924933 83443019 71 883849938 274216086 56334382 364594874 78951835 799730235 563804556 879381713 99369178 302111420 805079903 337903983 383978672 243320868 944441647 807128008 738683127 590750904 615752409 36594039 98575491 134435162 986901624 662104057 929347175 555203272 427351605 132537067 811716046 331306443 85229533 919143388 942285389 998407800 735962500 320013025 450745352 311678480 587064631 404495309 218806823 424949693 778489353 287698853 108831918 63678334 882958000 548187617 782364217 650998587 815741531 540807829 857685153 620911751 10413082 806645161 921051940 486578258 743453451 898079589 948598342 400476196 333816374 717368462 33087006 589506385 845216975 346113850 145501161 159658889 140403819 57 74207946 110474616 377273521 189449208 299253971 904592243 764742715 499388585 643301095 713725728 337104043 811933300 887162996 935668269 982074608 432891992 393449234 419672383 111404558 971770349 630937947 588601784 299383183 288499599 252573895 50340379 666568043 411446851 609481175 867297570 76151111 331558430 452550817 598456454 391532246 260531484 722371928 925239072 332210305 324241900 28044457 472542355 556051953 733712820 644325431 335623294 607513944 68101828 906390554 893382838 708889605 892159262 582370903 344150936 280414784 584306911 276644084 82 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 71 539459797 685382842 440441950 848133685 805302479 608228660 606794901 414635389 484522403 771118316 638011941 203069095 957951757 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 94 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 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 58 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 958505153 413625792 795264867 754613232 481444395 722749976 86402245 45272262 362976321 40614834 705855024 642416809 54 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 56 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 624524510 114048043 675402314 499648288 93469602 441383720 763255656 98796503 317684105 328263911 372638801 610080811 729928424 135757645 251262027 67172722 180413612 681185525 575930035 794890187 783256831 520387351 73013968 506675668 55 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 71 762419682 661728825 595088295 381354131 249483959 940274211 82888940 188591261 60275056 271378872 156249602 666803586 265442743 349672709 86814875 371067356 582154589 502299588 502576761 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 61 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 105516334 804603760 508434949 962670628 416087265 525004087 129968828 860467882 978934609 319124044 671120669 391944433 136575981 865680978 51 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 52 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 164293866 562238324 803144661 707722975 461084947 710215550 15493891 154695314 885703316 633260670 403801363 520592139 487145397 414419181 215367598 192986719 609666882 418962251 984906279 92 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 870429371 629613506 274618717 704324081 106985401 99685633 688871052 448119542 232030099 412550617 646827247 248163890 83 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 61 668798447 340709474 133816056 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 60 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 975344426 675256392 506049368 931623868 575416323 944724694 736761539 461557415 145265886 918428689 277028711 745560176 282151370 933557450 235672017 816403381 297771206 168396257 446207506 100 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 185654413 814298202 117392365 235435166 281176954 71985292 605135918 502421805 358054036 497795916 885378759 644169490 237869363 299201878 906360433 219847875 175154738 590266819 768063960 533939765 66 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 60 625071193 425964713 75056578 796881838 103111182 451647585 426206798 934565303 387161578 158296857 366491160 41680528 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 97 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 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 53 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 90 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 95 897858947 173735228 768054963 787987244 925579362 125188809 685653739 648990475 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 75 846643407 301490072 845803421 260865341 920277203 482265791 372491083 815411071 211832178 606788647 614138573 614428251 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 94 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 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 71 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 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 97 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 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 67 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 94 762587596 341789756 290103946 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 86 309133365 325629917 288054867 859495281 854313964 782748234 384395591 280286771 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 82 262913931 434468013 422462440 536010271 706925008 36910490 575047993 929975956 750365692 577519700 964023800 794458137 806579814 430348882 474409862 894590905 549410294 14440424 565084255 117607527 310606697 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 61 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 296456588 305481706 374999566 709899900 821480668 692254650 495423244 78020471 202687976 592320234 88928622 592569386 229684490 935137755 512732015 413947788 155691630 301812100 742861272 554578507 479828499 201806548 412136778 77 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 389396614 67 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 94 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 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 54 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 833765790 588568895 610665434 198395314 140164121 951286524 865118742 29998846 17586867 42427487 125859306 926829886 429503928 885026664 996103803 211639029 504990476 602871693 124582213 76 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 51 382822786 429783449 815507375 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 74 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 526914020 55363811 940570462 285087332 589449781 782023374 712079941 189760295 833697342 685256107 484675346 550026544 236847496 774602674 422135328 800669312 702982676 294267758 886956556 563770647 639773672 403335405 152190841 98 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 197618083 662085208 888488865 447704391 738731084 788399122 580069647 31378369 490317485 745243017 811681187 891013922 425386899 908939433 429977363 428060476 886818197 660645041 483678615 323080122 531586977 236208514 54 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 68 153371441 379089095 86930369 117140007 584495651 607232785 746710793 242104229 590804091 672993328 760932136 656994172 545150760 977530001 116856133 290742328 276223184 428467262 732083415 604852654 435500115 286287137 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 56 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 658006653 562632916 988314895 53 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 70 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 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 75 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 840014108 942574715 152234070 980237192 90 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 91 965686703 173783305 418291351 962730697 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 64 695140264 757214659 687371247 490511164 107188784 831474641 596883393 993327307 754103550 105201879 182765611 508266470 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 53 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 848705811 802598717 60560234 547798709 228497760 199161288 68 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 51 311404086 569487893 884057320 733067798 6549127 255791688 591321349 948709458 165719502 338061528 57758354 424071417 624820397 516970336 897054886 872855325 44827733 635939575 294325286 488724831 967714206 694608179 746405723 961740605 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 50 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 52 503902753 205021651 133092572 560006810 94988084 877789571 129593818 733441883 702565776 399814200 690177032 504483310 420154609 750869186 967441058 128360204 160311099 617132823 408889069 982373103 892910199 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 55 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 58 535259787 596117557 197081155 695049669 821291355 842101173 59033130 442836078 731407750 607571947 402805879 574631801 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 92 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 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 96 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 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 76 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 613452142 149581428 478461921 838575237 690706218 823427040 404234588 645262675 171567941 686487687 611344740 932003952 28920097 53 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 65 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 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 99 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 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 96 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 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 68 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