3000
13953892 465290840 428186591 253611747 752478548 154275845 912618877 373588623 249398211 885213108 799040444 581467382 219410212 292776978 976894142 526796112 984375701 850873900 767701884 474212053 339356605 799974716 895928672 497060075 994130083 156241688 578667887 249392380 306311477 325884253 942858766 67162131 709588303 976956643 818694119 91816095 175289460 539828439 688454371 769291786 897261146 303705062 767866950 186738074 328692839 904219353 86569270 674737243 496202501 612686738 916223103 720055086 360025915 505879572 596315145 286695863 915874884 535688682 99099126 887921694 861514631 162931600 686551030 986906021 188015109 482991034 117080228 433393779 967475190 269887450 984347058 431387031 588254440 322988452 854480246 35208202 765909043 267576865 92255145 731904846 471453590 619252660 12961838 645170738 691345700 826524288 661250740 913759594 48302612 990846674 437368708 342643897 572028177 951006287 333831134 888089052 942664083 593391266 864392921 956055212 288060841 743312854 976525521 4848221 367758906 335549873 126291542 397827288 225395634 280854710 268941545 619904467 330244850 138325464 3650021 552100345 847544921 79978300 95121718 260995724 962050392 532224253 711205910 312061497 158058755 158001261 929366806 273469956 473642414 830128005 976730997 246257672 616530112 207060126 525449172 25903781 207934272 130113698 494780574 294541042 136317170 464548720 293892448 577353902 358359507 499135259 432266275 544263582 513228409 5037911 36765229 337166879 372056512 263451898 575581266 612280669 461757929 335249991 646271655 95014658 93470210 109082878 299517054 26844791 721356521 11591948 591446133 415655685 882275511 755036955 339505122 231977052 417302965 364981001 54539759 327059059 861262531 262924026 222953518 342097031 402245771 644887508 700980452 940231196 737776448 355254250 116291287 967969391 362768633 574968213 211584283 79628806 199194123 872920707 640933285 397727207 385367016 515236028 251810828 548155392 536047202 902585931 338140228 560488031 66826745 124784943 261094674 302834664 313322336 688219213 202017551 878723338 644865714 136645112 559676526 224145217 971490575 355198632 486500060 361178744 412219831 798725191 310569581 652491067 708111940 179153460 483835008 168850946 93185234 432801235 628283540 95452981 463735275 411618656 955972328 880526983 661233948 280585927 743137726 331222385 873995219 468898849 278148559 620560960 250208437 587070622 58915083 470548669 614879668 910691500 952158899 876548973 879455799 879878830 852646103 897389247 364704774 318246327 170387851 632794624 94523619 469661972 701327642 905384836 821566509 112726959 219612074 470442806 897356099 230004414 108419267 450907359 720308165 808173942 607241989 48887186 594880943 890565351 799793745 470939739 190181580 224766690 540463366 419216080 626344152 386067194 433091778 746156255 60274376 325395907 588423940 207839228 736867918 965307993 167829030 766211391 238948456 242405309 975102296 977394521 345108065 428459580 806373309 373424416 616139045 266501706 435572537 338710719 974043814 133326029 269037993 638897215 235911024 421281642 633331745 96646266 139985118 69622150 576937215 529227365 379720945 681607032 428189589 493741243 120069852 721990822 819134332 980487659 232150350 533713479 410139869 547096331 47171464 393673201 409279397 721617337 329633481 254049916 205423831 218653163 943896002 707087558 951651690 638494034 299513193 839554438 916826509 259045133 385412372 334420410 2728341 584629968 475225840 626959879 721270494 529998167 253829559 267516663 792285096 4768733 868180225 187511410 285080241 338673790 221969297 172752409 528149641 204952994 224580395 455847928 583967072 24963811 482707510 821709366 475973410 908384560 940569293 240522863 734686257 129364172 471262893 788614987 531053079 9129631 404791277 719982383 380040809 370369843 333870173 99807521 776059938 405360277 11097285 248350005 826210281 637130873 451342386 81263791 285973677 384642520 941225061 195428596 429470305 991329932 464351575 417098779 587622570 421293342 569599157 92700411 961614750 274371207 702467199 259122122 369160762 252289880 124115617 795559257 870621455 911574336 631827356 984246559 943313957 214812597 347657563 956343145 664022970 620244570 95951504 143578965 271871105 58093648 125118874 485964665 62790937 585509026 105630688 96889556 874006002 568053054 630565715 581269502 661852918 219233513 939498942 137813752 830644691 443405156 314435367 213850809 924600160 435940160 505327197 430612659 612563019 556758645 663109630 222331874 947987575 521518741 537344772 557283006 81338597 485985503 908788691 229094489 731396853 408663273 685107714 882031467 620941286 649660047 225105809 245877238 800419955 549514394 261197675 97003436 864838797 60556324 192229628 32457933 74036835 898813837 814367059 654269795 687449892 758727869 322662960 110081894 222694963 23621374 618598288 710315019 882312832 354762396 679733206 109284026 447963341 909763413 694555400 215146934 667460723 676246863 720868032 620489590 92363917 440880003 952592172 451038200 114416931 816100900 500684151 248168478 260853548 578083533 277854580 566308476 744746115 516027136 193363490 880542038 504794580 51507650 296309055 250249223 136692039 13386473 654694699 425184717 403235426 833446736 382880378 832822780 388720431 771468857 483733930 384933395 375486433 204525503 868989107 68875110 412593144 304694761 989981749 58606011 861105336 899731804 724782116 9052942 553528303 452761947 158807307 571549319 263253402 462801003 405859592 539868230 436655328 503255792 999052471 810418353 334372538 369257707 124016983 310813076 690990184 552514600 169857477 582791785 469943804 879384835 835874419 668036601 351359265 952964532 111708203 271782547 377880333 556090928 360947554 889612205 640972433 256818939 112667392 798193412 614307996 19148616 835494166 125414906 23919126 563229036 653566411 155583882 804937855 722685908 114760275 110088504 565597749 708422053 794883764 14470254 55699134 370004055 751674914 635178379 127847651 382747440 876995352 782252784 954900664 416048270 79919800 304030730 53737955 298768043 381773349 139553206 161367872 146139769 953579185 140538258 841856134 938856241 229752495 284475694 525876839 325301099 894886828 600830685 23463017 154233170 780893637 139704957 736920509 44520678 313109746 808811453 314635266 601239551 927470854 959481649 961069727 480947813 628053422 107053751 151901057 631774773 855783798 428378629 59825674 411076428 682273540 700711613 953617226 514777374 613945155 25536655 564244309 656265794 47381444 630786621 61956105 675510636 305909581 921221071 512659613 474304716 513651919 110840431 619029562 465241270 342727321 50120858 309915364 271551299 34801708 849306207 975084573 936975598 352562733 655359346 954239706 28674529 813294660 281577667 640107840 921618130 117214878 318134252 803009493 731533353 538570288 443728633 578791939 525374798 308276753 471627125 675918173 905527784 557603261 313405463 893296699 222961497 762606143 652115394 162997106 992375213 814612706 426419683 253765755 239886668 594981830 259479334 806665991 12116395 855683977 323135429 814899324 102315165 703670803 743326781 507781123 761493877 406269733 206731015 483073188 454582272 927110133 661593879 958626931 544626348 831347004 942581478 845381253 647074605 622667673 592851872 636344785 298448716 590778358 792116636 505018990 359600199 463009260 231293202 532375407 923799007 577678455 800530029 311973751 964978455 40802436 200163686 528535396 861540270 848816503 472994459 396568398 589079864 839231547 920030296 931137899 788342449 960326713 743991586 704021893 856797596 538173054 297171393 780265408 709978971 625543613 506766870 901613876 859896276 492926043 217084105 248320267 633054189 769312915 941067209 106559839 452856694 183950774 418680233 132346836 8766635 838368415 581827534 428303861 106920014 71810646 834320251 548710001 645303321 797237495 337869835 1637517 205596111 336429191 394035745 569720147 641350204 812005352 460482579 637340009 626007421 947092097 162396776 470924806 410877807 452069376 535011129 683674833 221365402 803650197 63653378 975521405 919623005 532272765 23877456 638491185 685871709 696054138 533838753 304301217 721004815 724558172 680215505 623072484 783536612 682381628 174255106 54244495 12373680 589830183 527750488 780465641 350979409 479441572 762520668 258447256 206818322 79383850 98180318 493064104 700564794 688182684 968378293 548295417 249118176 444750870 280832580 752432722 90196456 911120258 663421513 963299044 134923398 454743444 588262629 428455226 692064612 553860127 201174192 630508257 926620511 622345158 977992786 547523874 245690701 521909897 341065733 649955137 331740388 918489804 700286596 296602005 428003839 931376611 86623701 735717259 82560089 681899427 546918617 194173980 952619392 603094136 768096240 341754087 367398239 139289029 905785753 470925299 69044653 481749369 113258564 865772777 199098955 388124205 537716401 611728225 809364623 525088433 721269801 234221069 663918532 484519598 830991550 292591305 352343705 762263370 133186711 682113179 404166526 551590694 384071881 556304334 572031548 236264987 58649254 9920792 723392792 307874947 352209614 28251207 255944101 265734355 786668757 910714447 388918832 835846112 261841558 527088883 287018726 358068123 538295955 430417130 675858506 601499134 858190798 133799944 171418355 93978853 335748497 568350222 506535761 581465979 117307960 5318836 227758465 283449528 195151796 733534233 117337672 168905982 305168337 824785282 790120263 231613095 229226679 604082276 166198238 722753123 815285770 988851706 618216084 320197947 184183855 301451317 417688099 810484907 364974401 293711439 165400696 913623555 670540968 288082898 792749751 137424511 443213760 590237439 44100245 555161337 889527521 691660234 170363800 449255238 792305237 113377700 130209912 614951731 116290034 669292370 413385505 34204481 94681207 421600339 792564116 670609643 429075713 765648530 892478039 397290541 365817863 741296599 142941368 47775958 726534353 933535420 224471374 902109021 786915793 375042252 919703296 849565211 298502382 831024759 109814609 429902485 652403313 269676852 19972449 933930065 696524208 567680688 955390966 50467481 109725895 833955402 568352641 608387967 460475239 879757429 236117826 281768908 964424854 869780585 374049579 330025326 675920355 183377507 95949992 877453019 694291886 41932765 220867911 409869829 337138765 34089858 908267785 868414357 599709075 793835915 202022204 802350731 868444694 150174261 807133591 881889763 153046301 678400372 19866138 953570614 856308991 449720458 645730280 111355757 852764873 791137894 466692691 470126761 538484865 895722526 380570894 284834278 255095932 198425025 137183294 807534948 383176260 577582555 702350599 447870871 953073073 995061511 690499121 401080983 693763519 126255851 330076172 247126169 947831243 915161594 604147215 613211176 585895330 430036602 271363991 920139883 118830289 585318810 172147204 865860638 642252404 330330660 725080391 689619408 224757070 275251024 792917649 585680039 715882580 778460420 920164251 6647294 340880683 842149591 756401678 676437127 216659133 367046737 545153323 102787161 648145015 993051302 484763921 453325503 988052319 30955503 278051914 322144013 774728696 441058914 109408351 589406021 909590198 536886459 588596011 688640304 978086046 104903881 248224023 328520093 745091332 665926255 584767669 256755606 128451292 651963985 336573442 769302306 121768116 551298533 258355185 797657884 208781699 551053618 18915538 562296810 923063687 346724642 313331474 86884000 305049929 171296065 922048671 994205441 406261661 930735813 966030443 872693989 188419118 260069974 396090933 38348531 11541454 612039857 507341961 871684651 650993398 748385235 701084044 339361948 482155080 462512241 943631837 70896145 684216609 382025745 650952621 147439133 236279386 804953101 463618036 284674506 807578634 919437372 186424682 357777714 59136754 396448013 108252953 885983869 319106809 855127770 201211575 894815820 617334922 470844918 969210697 321746276 990302628 241946757 865581011 481609397 118977229 181973284 329180843 849782526 250315020 559656477 825667429 855354951 932775647 776708594 722245275 126515191 274425707 394574036 713035624 961024076 174369074 294135021 743455595 165950209 998621755 559168816 371233882 551495831 163490740 929327633 825625053 130736621 939577409 900537643 266372309 8704696 141496672 971808623 472681445 709895968 897269319 649132303 687001107 330551422 422879061 867205567 367269056 749438456 980128612 191793540 260433231 833671864 697445522 974786595 319186717 292748820 352592248 896821900 873246384 702916536 982288604 906524656 827939904 222986163 211521810 600463330 110686264 876778237 902453390 960829152 135886341 510125290 182748571 834191394 72669732 297956336 725403996 985020918 184714330 921721259 439120888 63230350 116054261 516987871 29877220 302671464 115141208 961764284 869394776 484431766 419752333 782356679 758309038 590158984 929137573 48914148 636572601 803034293 769640504 564886359 671394724 977448606 85564015 637629501 364034020 772271701 995214452 295934642 484600791 102976192 397402360 505941821 348265395 364705103 920741784 670285198 219373129 605206723 100092343 451417039 149924495 770607677 207090468 535836844 549372943 645283963 396330010 163781466 692268337 367993836 719810320 945539237 328561325 205512226 297754339 675504008 596387418 142680969 405822319 69896470 643856243 392804924 676384766 112884504 250602162 836684990 794020192 369373277 925490502 818272022 158286808 430063356 187065890 126812953 1369292 31131480 747640178 544147178 989204170 534065076 216569016 563887765 311576532 84960898 920240275 569103158 329368880 406361495 213981205 616923683 418714468 513203066 352825590 147141627 906150340 867216909 412763730 429471110 549919008 424816590 48038299 896862272 656079749 813108844 492022018 876910300 622761435 52991748 123223771 27422732 975408982 562549351 262868713 465941765 458093444 392399130 363497851 275583268 352643628 791482208 408230993 697449195 138798214 118555406 713567106 299451686 321868 911398891 407749644 702294444 203247133 694202812 12363387 588582685 797491245 19297837 294779589 653644820 579581206 398108754 410924683 268706504 992527587 667153244 679683800 303934269 234148601 596159499 109474531 765219070 624047641 626595273 405698193 298533061 956889897 879801410 498116691 379940364 207822855 520516229 525091849 93251918 609721433 609300895 266206840 140884222 628972907 353477402 174726478 862210633 130635955 305088750 542413584 759732649 279780445 286837756 129742826 290332753 699772955 626108213 545568532 596121439 975960970 31569207 525791262 914386315 446528565 825021508 215749508 590582691 21401744 734377743 967508271 250662174 494030764 393104111 624027762 75676619 492682761 537084781 994007924 721450057 83683731 899991523 405258071 399163173 343340825 481107725 263131438 785182281 2218353 696887391 944996339 131788740 566025567 331735547 461708253 333444923 629910482 189071753 391907660 424339525 85990078 572471488 394853669 141450762 632279525 993906251 401519152 947882328 636980934 308730872 612683893 368991494 603476567 671193552 756022877 514383089 38595153 269426338 58395027 879098617 964601646 724923624 854626854 328355172 311142352 174163077 575498556 283214178 380395912 641988702 860157394 854052749 306436615 569933758 568593728 918915430 663324040 968773218 203446511 285439700 594813385 787705135 442681351 646013752 662125400 190967169 108523655 858925031 973995953 7914125 994054841 894166751 134687998 793650106 372686006 194719219 592347439 381497428 523455345 230185816 923396215 262404989 754355030 726587150 688839062 254386707 703925152 868553186 136195160 732096300 266048173 362862676 199315655 734870458 767849140 369480834 227903116 257749588 591494530 867519920 657385772 356190866 165968821 249513540 671103942 674294709 789464263 604659368 196388448 385521137 953521290 103000159 758093802 522220321 466796850 764212217 827614753 381475847 311627592 372404516 500299515 679635447 735429777 710675189 701115116 173629137 557149936 951902626 343308506 662576411 245558793 848104278 104270237 862430576 930494041 91664732 160559906 354369181 390755322 506001091 790517109 395989052 291318414 609194417 307467200 872123902 517083618 640056140 740996205 124334366 896274626 103035879 658156586 126798639 600732753 365195689 224350263 715798231 768291958 254041744 138129150 868393511 145470574 708795007 231863987 414015694 300227960 756666720 407189939 502874083 496527936 143010529 12019240 490133361 766021214 277367462 101824955 644070658 270755191 915431875 396212049 19707481 85318940 114574948 64718294 616061470 686839691 822024448 305053162 89052179 705722474 72114385 174706669 827954078 639533454 840782555 666111794 177488665 75372412 811340440 878185890 244161385 699239267 591301141 715975148 194726893 419180537 154118017 567333060 374226035 696636336 149539771 329493135 449340858 43782250 585870888 975783516 755320035 721284135 607267511 21731414 163140573 75881173 453742698 615795884 372324455 339018790 394684705 128728465 260075802 625505195 327672534 22406849 485277689 446428448 290083531 645869646 647453798 834542238 854317292 450793422 806796367 750240082 600886169 71030755 585424280 539928610 153226083 437620380 40400697 229877946 174102512 361786733 550321617 713990255 76201132 75522866 110569480 318127952 939440807 573655816 855761083 457490768 52662604 193471791 255408926 154317302 923961270 43383414 689448652 386279696 830755376 914580854 558629127 135598020 584709843 883759486 68123886 265677215 392329098 880405531 596426439 976760424 118655034 317600292 976722923 674245823 713372673 696207473 198539226 690549736 558296087 410098396 329067792 725162293 842356258 492180055 834403467 434849714 91182189 735968104 785744030 236578829 596379155 150000461 999511355 132794489 719230264 156782875 458639937 907148669 791544121 973254172 780263725 926411400 517321297 448885367 579714799 724656582 426886561 784993158 447494452 73045840 750160275 876842182 123360347 959779842 773635757 395420788 283476402 662797343 208274719 60316184 916734097 260560439 731572853 139085056 139267376 778739373 258137097 983500016 973829847 302199782 963427697 125732837 85319905 17845035 950239209 283568438 549798457 802918109 254083687 849196450 67184010 213167526 994790471 751541825 367591850 996375422 963063535 238606142 781420675 978041012 27158464 594928030 570512176 626073315 973409116 504437136 654108712 597584647 129006974 715461423 973088657 711658581 730517739 962663900 382377778 396844469 504550757 774030209 930350754 975335006 418643707 135709596 842646747 176494506 581124896 106746176 187951364 349922691 644207117 532116376 769729579 153378643 718690645 347391192 687568935 146241704 293878599 110804706 143310588 116479570 369894896 539979928 187645666 820434843 844124700 880514383 457597825 481313062 167564521 1668125 141424392 814258574 683088994 788068730 954975695 195060887 966557321 771809648 323658052 886120155 409851149 312213809 123069373 13821431 209409487 934912040 530787431 90824865 806283182 650447579 899521067 791711300 939311533 76054383 220937712 630384669 932845580 992865616 663154428 376128533 121697260 514108848 993085737 913910077 967372745 738749795 913037603 689069977 134725873 100755503 851460727 568305239 140875115 698824846 941270769 482671076 802367240 632711793 668547339 419656580 389855935 309784071 200193794 395413961 858419680 847902615 98834431 622631707 766728282 589166363 913146393 131206452 212767362 549963901 62476285 205351680 820022360 819246640 208781454 959514356 648732079 17260085 328331490 555019570 612832422 372024691 731604764 163427376 663439273 936013126 358266183 212652657 222554540 573472609 181087340 786712474 255416167 59533492 42375583 743691337 191905462 22899853 602317122 945011145 836285998 101153894 140279812 750474750 534122294 518283830 325274565 379623519 996766571 409811251 197040934 265472174 791290556 728876392 670905147 598225670 838030216 466328061 841721515 414464233 122460351 755521197 197821715 947069686 325716808 590373380 281165924 183443642 805652223 57606430 200116303 456358895 590475269 568327484 955575813 718362498 812428561 447835961 29183190 281546311 270430952 526660462 792990681 89452808 981122728 34438035 514343099 419139457 648210321 252084277 766521121 827125115 454700895 104326264 349743379 447620193 433498121 753217274 440171064 161724882 157932263 843605237 141042268 51618975 445635297 398605994 869807442 134960323 112338155 702150770 728360222 795979274 585494732 370125354 630963106 433425363 542342323 817227270 348012568 495905898 929193994 530714710 515277409 163753734 475770049 955389628 279206770 833391413 594214812 74046621 275943759 46478456 322695801 318686252 584863981 695665671 49580484 511904403 397476197 591997123 288369545 355064089 32921730 645257426 288533457 406757476 304086474 400565880 847799635 410478719 261039207 159855103 267669255 49565964 742296704 879337032 133704420 779229596 463579506 763966451 703545298 427709698 72799452 827987147 758672312 365069149 387901415 966910333 448724643 827475545 269839650 887012541 180220761 470218674 791664877 405621595 513073158 82510815 170881826 213033876 169442040 174286072 910728876 700744712 103212680 43705116 834130358 429443570 842920037 437730351 613464406 169743933 691323721 516776289 604112101 672856796 859689943 248239446 10097582 889169886 643688056 952918104 713254189 343502082 430974732 868945690 674118909 127866209 254481947 268097441 929750416 256321691 207870553 937434991 911185949 624418751 124758376 217612076 503939523 568482875 70473385 567127967 224297002 697746570 989740222 307487788 18903611 392229395 616884151 428705400 60287534 807032190 316124442 698601864 332682277 529295352 545659242 537398336 95827870 415725733 144693574 155420253 259273973 158106322 124255816 666123701 377447699 180652280 230074970 710437623 775061801 428846662 542711763 296260904 241296960 311160245 736452108 865573127 306781141 886380762 212587948 270416084 151971922 206272476 911689904 989742124 502875941 5212823 184000050 28557382 643631157 712636206 692596311 940728464 180770652 960185658 941941242 500856696 765691175 926170108 70177333 588015157 429344586 412410858 455387376 614339897 430317308 740204742 555708793 30694040 395199132 145054327 890105300 34300640 777993927 544795141 815483902 426577126 687888719 512344706 287954826 872594716 622296121 143869815 597828473 700185002 30939245 962810933 477539607 989703781 329099291 637975234 938939374 891014682 659431733 363788748 111589830 479566439 478768471 387269345 935151503 16334625 841849366 522618614 921413159 878527589 526123389 970874319 484924782 462482726 614949986 837134073 615318411 904693658 966274467 936940609 836469574 454252124 694616237 794778368 203805304 654304983 368908754 29204727 63808403 792031220 69867220 44234189 135428037 713098144 233178463 135871786 828223603 772298756 4623105 399329323 697734539 772637614 674927747 69229457 89584307 19342989 346089212 503216408 385747932 172436967 410692062 998382183 412364538 455540931 992678567 275739123 386026911 117777923 621286698 845791830 689067302 915748887 122883176 45432938 521515615 830034355 594490148 326596641 41938670 717160860 916590161 177156963 396037265 333605167 401306909 496511295 338220077 965719011 328973614 472788627 78061290 323516225 587147436 313580838 785621620 764565049 224169075 260915183 265978842 220854284 876071722 351234040 166693794 929081668 416329670 881806622 822234926 827773476 673421596 981710046 13259911 760693561 133702295 229744132 857806013 599146261 313924579 59496433 480868481 103687763 465247383 770567886 869004796 546851910 102595973 36424699 346334715 969231654 128378878 371428321 355489388 442463092 239192332 348958528 614283043 650212116 786109836 881445796 24264229 498038514 377626385 410728005 755366192 82519261 328582053 373659427 807781216 835325576 133581343 187931058 415269572 344705686 181191432 994713819 157481846 515706849 661501583 975465301 678998170 781619410 640359155 633318331 610864800 709184613 834897698 388595261 243578671 210928718 958872801 828378127 513628225 838035535 123193764 532672933 998086453 885787395 958035798 334242639 759295609 810665877 102539740 751008965 88056320 596564934 226298614 901765703 288885714 129208960 502274743 493844215 361988345 564858784 890377743 760903427 982466301 856846471 621009634 914572883 622856377 875866169 873840669 407819447 826781428 902919292 229041416 842750380 301022828 252471705 171221451 220153806 70166040 967113028 570134155 274942690 409060397 227752414 183129815 843248703 322916426 298354268 153732543 212248456 450543797 858831147 108297578 955751368 482104148 586373536 453417519 555264381 614377075 899756103 99839820 980787085 666604289 154203039 55880856 856947392 302501677 149002443 333721338 674965568 857006728 223708250 309618341 129640512 981905587 990357106 300728097 516586059 142183296 523249207 684308232 30896566 736734648 214767275 479341525 958695294 340009620 344982638 884319368 487225619 842840674 43306012 169631312 348711521 550144924 16196433 439575758 527974120 135589138 231764077 353509373 29460214 536227815 197326697 397006151 587021820 876447353 480270044 339190985 190821176 859941936 30934513 792294697 299976481 219876541 672482294 506630253 95520347 372585968 55641368 457855848 131846747 115642568 794437158 268168658 297198072 605260146 763371804 788850295 67619891 8439665 971482718 862050295 503351601 65726738 321097561 479708086 257005929 14278726 815007620 400715559 724468287 817689520 227623224 963671490 530410262 393656951 835678714 447536567 855637627 228045831 620289294 282269536 493644921 330888880 439531133 518772217 443521771 952461083 627809827 211844203 592143054 630390922 349081459 923249860 518213553 687938235 209646824 517587116 22203360 550192992 729836875 337529891 235397507 382557413 644550904 667275995 260808098 598109202 11203151 156849903 912736617 222448068 82400265 55860188 761830408 253517277 148130718 696370625 697138847 6162738 611183733 351901808 579511166 42866397 302642809 699786458 749186004 114938053 124013721 637169178 967089784 817478476 797919584 133232891 47713004 345490449 411615988 990444129 711326283 722273407 987431003 897071968 14017558 291448343 190969811 679881450 656063149 832492843 728231568 284131398 551803128 572468924 215615339 62697438 775691790 396664764 228889269 855113303 102942946 572409250 482564329 315262728 509439392 797597835 279595673 387876476 673778005 129550080 235828196 525878273 519553087 233517203 374384311 675241941 921573269 271748462 843139039 562237585 921581894 423678498 265442508 280130131 609179581 772748245 574821666 341817363 589308962 963074412 23038481 585942571 118703390 222799049 671139649 345315830 72804986 47823095 818345007 115000329 907255121 31745430 353358523 757157103 923991930 155257910 611270173 689577938 5290223 671587640 858676930 444840507 468843750 167877357 601276378 368665998 902697994 364960939 887628352 214420347 983641697 581061181 95840595 812157306 273385367 353672830 995813904 962348549 110956297 358056338 407597812 778333845 484108722 409811268 921991024 716855594 690129851 983991624 592726364 205788099 305978419 400076910 42077525 609928230 165728778 967783634 59624746 588179843 789860818 641854875 796615183 270111404 158025550 869758414 367719634 214696794 458752190 423273953 382287627 168422840 889952709 564984120 68816156 701271748 628518482 213318081 869429529 217954391 73993886 937281718 776076246 875919499 408008346 506600811 700576092 480567567 103997839 148624687 541124260 888522542 435812913 160380583 761607442 578883025 983570331 234459077 897237152 561362521 748254478 323703119 545872960 10336358 786764096 44829605 16775924 368032759 845869548 911151305 552996659 473789247 329803658 705011483 531129327 853425476 405227348 115386758 974874348 617629475 78526754 376108478 552964654 538320406 38605670 852017063 455411704 604716411 783170884 658480914 904562724 916752273 987042273 289070581 435626280 168704423 147084710 816594251 547712360 146270899 759966560 80678639 676526540 792626389 712069679 988923734 811888771 633515763 829090486 260331971 82057671 121599855 772607755 700565866 336153158 569987798 184595401 483326996 361129262 200757206 505438984 286993209 872021398 161410853 477544273 704134676 67985688 614078369 486387639 600802104 454990430 649153663 322249270 738153811 972834563 101372904 662333526 514422084 973930618 906293867 291563486 775787555 280785163 142898647 5274471 234208713 79141949 723457397 364808451 249063469 428685900 437236971 671492506 901323572 672123063 882991470 774459773 917240148 352867592 885873472 354246228 831659343 205202025 592739216 759679100 194973642 342041033 922779924 959735107 280963169 571420452 210262822 754560755 899491643 958262606 39148679 856640737 73012467 430118393 269857402 196460764 176013614 740494424 340208894 323139031 762943785 622979244 330423127 961699321 919617901 664356968 283498195 873380844 143300573 956501813 253515698 907800831 481048120 27845534 717246494 261210910 818482236 163727168 622552536 412609823 776445111 42183094 268283597 426479676 170997398 154954775 898227503 156656707 554844343 48536764 486684023 432779279 758198020 851829523 178156946 796416364 809098351 955503850 133878380 857530785 847088458 201362894 825913801 128446502 557844801 979851489 437994340 655805955 662753955 665511758 730787194 217360684 877454047 336956085 125891268 368389017 571747201 256821535 150381391 52472339 384685511 584555810 778698172 195282939 271721825 624476832 792505507 501191915 881216247 729427950 617003714 522563552 479362742 914250039 731512651 946900344 298223131 971405397