3000
275057286 805587682 774748504 338183032 389157043 897454159 945239690 956630437 583710106 752537154 524006751 10666091 888404440 824335881 917632537 573579571 65924887 487164228 938125722 103462308 55675018 765812709 185917622 793424880 90579647 900298534 162635791 697059902 871287053 753943314 375913472 146344338 412047349 3178329 337043724 801204393 900632488 134799767 610351183 336858948 887336921 134357933 347525039 628257715 811210168 117673929 201837285 729651409 604838158 139963006 685630071 513029530 758292069 871547693 158970763 701388071 624362580 321606555 398447972 495649632 928066223 626877799 494510324 340113572 630056128 684070403 993834319 383204970 818870170 456701855 720063918 706207091 443576142 920105311 186981159 107302663 37779240 388818444 836954072 495133752 381297804 522584142 8163281 139589873 246648188 19650398 693494298 871010769 341256953 91942269 219176754 121839530 571336422 566203433 461953102 201392550 250273835 308303774 584597520 69144004 765005629 157177791 627867449 208581770 77283101 814848608 315884433 967578696 56183405 5354858 315228801 289997564 527939000 175908436 282103791 627103542 195558835 975598089 350630664 389332142 920056712 569807419 511171672 491393134 136010851 973124774 545302038 238801040 133944901 129899557 160461398 898950530 139593702 640845202 107532299 69393157 308210163 275933086 889488208 364393569 281287944 57233362 654391133 661743298 233141799 936494924 288846840 281216988 764609366 639477504 670549130 684666077 61801276 181720802 28575564 50328481 7361929 573877602 141645875 141306831 556293513 302107274 40257360 548403569 942952476 306014 617796727 103678992 128755454 359801288 468072561 262559753 417034650 974980048 924303051 650176449 763991325 65666244 931393437 528600690 705143749 454458921 65783121 619461379 636179723 94358685 669789861 496058006 520752642 811435736 637364837 929562509 966059364 530138552 477966078 761528193 382960920 948279159 865207186 364232728 308080446 185796100 626792481 725115096 160776148 551095532 227807899 924767473 616761776 11717689 305884517 174421878 466176610 224183992 793883258 954872687 171059031 316189472 450930693 691811673 980141562 940811884 473890536 946200926 323466789 951856614 560245472 706427709 752652126 425452657 70660437 60732571 611248758 549969272 638364021 624541260 101064803 718688274 401825086 570342934 730405964 707709603 597281166 49098927 931893595 243680777 3971614 102952626 559870249 307418661 647280653 392528165 100746898 121171188 191245444 424213688 925544156 751490916 130641396 530712635 29459927 53818187 443961560 640708685 456303814 82325581 117766298 409884971 653530209 519591384 980227905 236452526 79817341 430025425 285551454 11710935 673706202 142039422 967179916 86092805 301974437 466976923 478620970 402721335 440664465 669866414 826935023 218724975 421357329 810092774 749437610 450817256 716427315 45915524 944042295 172731128 128241105 61808592 582616100 634287668 581399977 415360358 870740195 661217318 845385783 8808002 525444607 371608339 150847424 345140877 457701144 452821861 664634154 936322114 855543196 105298618 606188527 534994573 176539947 880062210 345087346 778493912 183395820 61514660 824409436 127438114 86762143 805166895 41763061 521894597 439454562 623163038 937254955 162711110 136896709 635157092 171519112 514857670 6765430 322366536 859998547 316982928 627704751 377149054 253305041 335764301 334964027 712009922 870758874 511503974 592072131 68362573 142514239 775467951 129877233 966923675 755422420 69155730 772090569 797185481 591050327 64061485 272864872 380821636 226772595 409761581 868495082 398291708 924619251 727776866 573174598 637134152 44759793 200879349 14283205 150581188 536643650 201763586 862591110 259918877 713267561 307179594 328281450 855781800 82647545 310675037 675221829 690586319 379830768 299828751 487771799 823397449 363890236 760636671 56735438 443179186 22914605 925230520 841470894 800050210 653007385 267161845 289700715 550283532 468041194 156500275 700864720 857201198 358263861 563455829 117120074 71531421 870635424 445401524 779829576 805799323 756076562 307567758 348901995 988423684 607396509 836673794 811821132 971286746 449826818 868556571 266982285 325257777 646303444 108453178 125307986 151827183 228131377 415008702 702110715 696172572 571508977 402975435 405890123 929772838 818947618 523010198 853820614 542099395 820928076 486166543 200415071 429520991 793734301 549317066 417944674 253647163 238507213 82282160 77450262 688334031 803355085 344432547 13591807 449658528 305402079 991416149 601485711 533533457 258941204 156112780 82222382 830450181 559088215 488112505 612739372 230552186 11122702 319076339 772651582 684567133 657759236 973066653 114088123 304009890 522383719 384549152 557657054 760890932 466831312 635107316 301741317 122702750 979539864 167849478 572361278 284941942 11781980 26363343 818475399 270723184 182476123 900697781 101173364 594080692 241326640 566429091 824632878 104965696 738021784 597284459 789532829 395781020 422867466 903620953 699790910 945251185 140686458 109964317 558658470 607517770 745071634 712916141 730220520 724611497 880765620 155098151 862069793 892547600 33977848 533061546 15787138 216453971 286275680 116960502 810534663 527602320 535905947 487683895 632568017 126444085 84968353 422100845 522225105 360352173 178238151 74532368 158119711 318924609 184496686 716778182 778958733 929568320 282210676 361695606 506696170 15492649 516793758 221282316 908040250 550771606 754343862 923827388 619741932 40619542 893304244 282792948 568221862 281726545 770476843 53306232 408170630 707961551 475407078 782912089 68313723 506161583 857444457 226433435 825086193 894457497 795727971 456561279 676542170 77938646 818256886 35754693 93431296 187566997 257037010 853987900 738338603 11380871 630331641 210596888 52000413 376152238 493389837 472738630 657878783 263866679 526044862 918565767 971828230 853968294 701477855 892658308 360129877 411438666 119091742 37732423 158412516 767336067 494293702 834954687 845274713 165066941 870709380 791222363 352633938 127746389 645210262 90972541 139127261 128058256 154085783 43644028 504210495 647475620 368899012 14605631 911342300 747460229 933171399 735686883 601428522 487165607 480861544 814074753 898604273 452469640 851807176 57016789 219805706 198617232 744487830 917596774 363684173 615197209 708819136 716318112 595459953 206545752 659807007 587103568 334604008 813892790 483263950 838814503 313884764 852162963 853420135 77743417 452139545 639107887 813430300 53568066 126273493 146808198 720159174 877394121 599277838 424482703 786927264 819083545 623099935 531415093 589196672 839300463 999128656 150532161 408134928 594588608 357077913 67941934 34208529 544198276 734351078 517472480 235529132 48235841 222151796 88949266 125979258 674291341 580573507 791925913 580375761 706847001 938734111 300534934 436757475 390528302 725017638 223684738 62128200 200633926 607616185 651324872 39934388 606744840 801857034 300585670 53849802 11451300 221043958 88058331 555649576 955395037 605530811 791178709 856147232 827682607 732644329 834642845 354490301 313217836 479085111 934866063 872581191 270335575 87917350 309338665 660863877 812934988 385539757 722992078 866085269 993155942 226833303 758536011 452417135 28690336 59121681 506266937 40141637 280165639 446841623 595791213 88077029 52372433 239486275 796740616 732571395 972130605 483899814 87061695 137864794 962984925 874444112 10445984 85836853 962361463 172301003 599217084 627812804 557840760 174725515 493898072 550996701 401558819 104950437 3413835 430249155 164072118 362197127 322907146 296754111 809038750 918698360 384831141 713927537 10700988 34088110 299015285 982831593 517987924 238593335 120696386 333489202 113037446 131142370 419326055 927915263 155959727 18543138 555728067 713800487 45785008 902142493 117313541 447343827 7092929 120727377 877592982 23681401 335440858 53016482 320435513 996995962 971714842 705266654 563439852 982415830 739354764 862455138 817763777 109859041 953564827 938460163 443348243 919118627 922118888 862674298 847033890 78078614 733733790 255278310 644395456 779518798 9937156 761708997 79378978 17030086 734952728 956971961 40711487 70393585 9988442 361147000 919905901 834219638 918930008 483345753 669151821 510801125 198317244 339431951 620660166 4398424 130408468 64008408 923517051 52527355 779199060 623067294 983122324 365449204 878345604 480034133 144968001 888282761 241743130 76863334 757829201 976695858 33835294 798540688 899605798 896340091 12204042 672028052 583076082 931134050 7890158 104744256 294451529 206207402 444176208 915111695 210605826 574584676 979120104 134122877 479628385 610835517 609706525 315267062 976284721 340568483 795301196 973769077 81367597 889560680 50632410 839196798 718772891 936984059 490253839 470895042 685840503 502457881 142923094 121432938 286108285 150813252 226177194 580559814 209537009 522869756 348187862 420142835 97454431 179824319 406782066 429599170 790659837 16488591 597382587 766944557 209573428 245200136 593229987 290941025 134760815 643862397 130137822 853533706 433362809 620391661 176945102 119203311 975365897 319868196 240636249 113990535 323197802 319329798 694550349 532734811 842199554 42738210 952877647 792170340 75078884 212176066 74285863 865738721 81181011 671668450 485199631 290754439 916868586 78429618 581695464 51629400 574808369 564349640 757679461 8171178 37257655 934624563 127374489 12623551 107009112 220527093 126614086 430206914 539856891 673680789 962941726 234572798 568935353 768335726 26743137 644014237 833028146 101029001 509752957 914209158 772697451 994952589 57479950 542082391 925898561 491691769 446228145 500706929 56041408 56423959 361394461 93299063 991048522 341285305 105922614 950573988 561812398 85053054 233297256 954185643 758733843 48755335 188758440 180185550 817091061 68017932 824199787 502635560 169046933 186469098 269361071 794260738 33938040 326841022 336343128 959836601 818532791 782571274 313059883 727090553 838995233 674454345 820389617 682560109 15739649 778828585 485650450 430068401 716397994 718947706 384254043 327648190 767703041 425528837 507833740 437310455 493546769 332033527 939946016 662593702 518502625 209307086 309370794 552440665 388664462 645713922 364793619 59713606 280801549 677853502 786804160 972313137 352307846 459710130 507389599 220563849 91055068 993040049 650632250 807453062 711987755 34886292 135101252 332207149 312931484 642934992 769517605 806478253 827484873 709463620 321588309 198503851 771287060 630959103 750944516 159951522 129189378 115738134 219665128 409990928 646107991 6469287 234820418 998415837 318695771 742210017 71496040 409750840 735250065 722128290 217203901 299754173 609530937 204821507 631961323 922462421 847756500 253995281 728940673 527757726 963458901 50528981 726261578 587262314 534004438 329722447 747213836 663193817 297976936 819395319 73184744 944084927 678380960 160521516 795017117 997076732 902731533 866513157 406827571 490497951 588641447 476547826 790252125 50688737 681369334 274729801 973151158 381642187 528725082 554608184 909399913 344700336 457653520 635661490 931962650 991657958 965383938 531692840 654851774 115877227 203604512 580552872 59962153 881985472 741074388 854979270 879062203 496322274 574008781 138406127 986820226 15166581 614953954 629588704 65855318 148839641 904318505 39006475 530481828 285559940 593614659 439881740 482776630 51268178 928059585 267255633 895442491 745959876 798948473 402810618 861837103 2552984 983363491 921799256 737054811 576954232 629294879 468633367 73276506 55820013 607039495 912613086 70986594 74509802 542201789 136841912 223349443 299036647 175848387 753831271 437112941 621979401 46229364 919889571 525763933 974288949 187145203 421206423 572765178 838610031 824017042 434602280 693679369 659896886 208917889 430734179 89367471 690729123 899367547 15160331 746549136 358923395 927773417 817535731 285949551 322491559 954377643 509298994 474044560 130226030 115646618 911157501 604721785 14392336 831047071 130485717 988681286 870708629 404208495 413962817 709318659 80741890 848565098 255514381 740638776 909999341 686248561 682522601 600728463 438132461 697682933 199793953 649572210 477972703 17329683 935521761 652980617 971707326 297337108 127025176 954449710 412983726 38182677 411687848 427376062 721746102 542173566 268573701 444971084 946382061 682536519 6806096 27123950 383617970 262320478 620279080 146133664 948569039 155318034 746862128 239217853 853000967 946656081 888790063 183490024 816502118 676828177 836470641 640725797 974165285 816012171 447691861 239665364 706711202 859379709 667041426 280973658 254069628 788131482 725944742 52968042 323184354 732750839 80091992 706802324 995071317 552887426 852935988 796156709 708205461 452314469 35374561 413722781 251486903 776680978 449729159 67989020 306025508 138716153 561231172 280190792 954728325 8923032 519856156 661439526 868302741 39413935 942413184 122372369 827545417 520874280 27856765 3246124 253625118 107948758 710048448 101212788 513352538 415500790 897369497 74074352 720331613 785260412 340313488 971818517 414457743 790042647 892323891 720483251 928758801 306071416 674042 883487125 314994448 373046552 397443004 35813543 264976841 192372542 10702266 92522258 713246822 38559031 95768382 819388294 999024144 658333185 920601082 364893036 926350329 817970578 438967388 646681941 455747343 779280876 471016811 870205086 421839877 215857056 590688336 350598677 521928472 443878732 86602155 689439275 669441638 336561513 725252818 934418479 528934055 588471438 879457091 94697230 627030469 827741828 914085524 478570967 338591366 687202959 843464003 264941694 357689890 134947744 764139989 813437233 914228621 87673154 683642318 188584851 303530210 126847007 539183528 677975036 423242093 478302037 367414310 92683730 814863550 945183482 27102209 196313959 533654919 759075654 291011189 13201742 586817481 57613067 491772709 925408847 744816026 187753065 42866894 102505916 322700809 807006884 768459503 89445783 894680038 304618175 278030634 50726601 431465182 817214162 728701637 854707276 148032552 948632302 799907360 962896103 893815783 679525923 159210061 279987056 438601577 302737604 145705152 877935412 360350671 637477861 655860613 957683052 825230926 698727507 912705322 448088 358250744 681164824 89893872 105447135 985782999 367924506 8690090 269764535 37655022 737391728 976988165 185687574 538540383 776895524 148583676 284872519 308937801 160310091 564859575 747539378 463047696 710564727 477991143 823398367 200558941 133851755 633597772 878306221 685095617 546303093 878754310 43346360 79984271 968648182 1309850 918283624 336572687 9999940 40564512 374227709 599908022 17552676 559915284 138448404 646964555 561015314 423320924 955902356 721325406 840696853 555958087 184373101 403777934 33949229 860287822 604336875 20317339 493885594 335159450 705412956 892705041 213913759 601275670 972689312 35078294 602585520 743489290 371650981 465101815 784053802 598395045 65009836 801606479 10826682 55974595 301087387 571841996 479295519 256989742 293167401 172508725 812947829 330056856 576286659 699413412 190344678 33139888 719730751 536746626 368299338 425143706 429451666 582213097 26419376 254657332 617291391 481521250 998146622 841458726 946623065 634716777 439853770 864149256 288839609 450680452 920123851 589926996 22522448 251935723 846916738 168206203 424444448 512380920 498263060 731107 64310686 541124092 33870995 784041437 77870717 402170333 61701497 359838737 836899784 88120873 614496069 306707528 422158477 465159044 148166253 221297896 99875821 440536378 85447151 241231784 891216830 858087356 831158781 766255632 110023078 530591872 786978190 534467526 42972792 137757603 387714987 107283478 678881695 421585982 743841269 756752412 676272669 805542766 116591148 513172452 746179993 583603572 819879980 20854824 901278970 820562588 242152720 853671145 261098965 180116225 94902929 4832148 38203580 926061710 623604135 743012 309169935 410582324 387726892 204659081 548339927 775441880 164458913 79737975 49544215 908300183 836490387 725816885 713842948 805597889 91505690 312539295 241717814 911385671 333394119 142996784 584464612 575546839 849184283 845563577 608179418 944087212 702912079 498899352 722665275 326516213 499642364 31835210 589614891 887369256 89010645 137954817 515327489 253469559 70209146 564871705 161769741 906699533 290688589 728129043 564813776 382194279 40668337 659047944 146096303 374062456 654561082 730560915 802125649 503745365 428640845 410305066 300348930 131552924 909204418 875530560 310585491 261363135 759882124 900200383 1248745 848892769 890671554 516576234 102362327 960880701 81447938 116648422 720096587 224652881 844777466 137426716 459363515 885445803 796474661 605459818 112024613 303552096 188537087 914150262 807297461 469694286 176971682 960162746 453763564 938692454 835693305 764349056 52571943 448091782 517065792 53820688 296984550 260253699 422913276 251863232 73650753 356877569 368511654 646263695 581530450 213289119 783690411 40893964 951251277 432681425 498870137 63275889 736233522 539923578 829942505 396047336 9617863 859430541 208726435 463381428 798122995 44419739 80246837 850694938 345027875 449828983 757031980 642012426 710082682 179945255 893875658 636249790 536822824 114903665 282513484 970869629 328192785 918720249 864279947 131960415 203918028 215666437 47752658 940151550 755590015 877695163 188715239 765207879 589642058 397441675 81105660 240281406 294377768 13868851 90976343 639405644 463697834 700524677 133934423 26296869 880469932 880326435 662546659 269809110 995230100 945060143 93195092 175939238 716296746 957475039 307899653 920214774 173141476 355652311 712882677 928731491 85863828 901597916 546455723 675505886 151555944 480077737 915787292 298450067 493946588 859279989 937855711 957644422 559804665 924306488 983941292 292790950 804632922 646487950 415116414 652379375 444064447 508311506 828318614 12877546 465786545 136218266 933092320 491444375 491870578 645974996 272692219 577734406 400089265 819147943 105756645 404161564 151742033 21543936 702611631 645688622 880823925 492983695 603333043 293144943 417290182 439790688 438452247 74439457 86278638 853568662 726818832 382859439 361880167 407653799 395736985 680183066 543872066 181345658 171627440 888258998 827320654 444319660 318509757 79926272 115983956 424266402 484087836 267725989 445810338 39215820 913414611 179150616 532199515 369264008 324811913 949489697 809054696 763264160 876445508 747849688 616832821 455780694 983225481 831229343 863434493 231478819 511412408 259822912 412824477 535556203 148081909 92661484 979875863 466591666 172587757 948376173 890858068 509191947 68618515 189184759 548407768 982033127 220851729 80607282 203813488 545663642 882613334 865384538 308927802 759058841 465750580 778276977 67355888 448976060 609506319 930790382 680454880 973435082 190613293 93279356 508991284 191211557 38457195 341383500 657803223 211044952 142276026 401177645 720236899 210894541 442878758 121161020 45444021 663730488 201768303 249257509 209394129 84381636 114642047 370838285 695956831 432908981 149115262 763312720 881885041 611137935 546619455 414856274 584573016 737232748 360651985 946080654 928444305 399109180 139980507 438763882 462670486 282256533 692457881 35423738 493151075 135336638 156584759 538595096 799067126 358353062 787852606 860977610 295251052 755011007 231815894 843724237 40436341 233447510 459553310 922321382 844585446 6172764 189694010 281674815 595921867 402862349 227755469 376882525 801971529 367735976 815646407 117158368 649992510 360620641 152582106 143143584 495957280 309166865 534255034 147540759 667519927 174623993 8518368 815287333 929635000 92850617 659011570 970071341 326298127 118564879 744909077 23399926 977253999 787119441 305074742 573175865 189981789 532830211 950058390 844469672 753082541 618221151 961628040 255591404 978841792 114210145 251251342 327315425 423377011 785506377 327372539 943413292 960130370 188407261 758700625 742281724 281257878 270228548 564869418 460072360 241309781 162294848 483472286 71080133 949414289 788547028 644255998 139396077 173893592 446830742 836382103 926976134 917568247 798010142 182567537 748926392 764736642 433818880 76241817 40630006 71841610 256130710 984043298 31971979 444537971 595260276 774253703 725795850 865488824 191639475 38384563 959314960 353934323 521856849 30395092 303348612 310403877 527167445 295261043 484297469 973998187 131643146 263789956 744082787 782169642 446357494 493009178 399422637 732692728 421767349 440052643 804534338 677898059 424095941 836506317 122436030 19356216 463276374 700748234 737361395 654915849 739132797 549192708 8850171 113505999 579587800 164715137 423909876 106755244 312492535 760723700 933269785 296652035 24513655 529868925 78821676 323387503 22878103 330760668 56080230 297161806 770813311 860614568 827576220 47425605 549637239 802528604 66781822 865429967 355793191 656659571 372862169 94925987 58368632 234228694 60948340 637956432 398943832 484858217 597228031 711436367 98098270 383014169 8088401 122611925 912883095 939426432 445999429 788277552 122703453 354596013 937955712 893516765 67726935 765531931 940942370 617364174 420576888 860240546 335310494 776370079 369416470 708172663 723812420 427785102 942401357 784760761 65741534 193861542 122135331 515485919 905297909 220233601 751016442 765902664 342845526 516415890 557845450 641361309 157209795 680548903 995957323 95165507 426582021 63684257 713213792 367524391 533564785 133790680 80281290 868875279 910160759 449697761 577047941 486489533 877482863 371965651 271250293 795740751 565827194 393385624 163743023 323641456 613619225 914759466 89544120 808981105 431175355 499905924 450342414 588385151 32971180 298816090 536067012 459553202 362500347 249280803 679593947 896065132 235587837 759875237 617456764 145748596 209572997 47021058 484754483 87055860 418986709 756004776 735312965 984813903 1906753 899055989 308455359 468042332 813815454 250515833 277023436 97507162 602938111 579882204 538408667 635909291 878698294 74475678 947978847 93714994 176272836 627572793 989780126 411860673 239964384 459753243 410125623 449537381 506774301 894880106 389109595 925761011 503401235 124422560 910574913 505307988 875994903 71546625 973350320 542326710 174578812 102890110 639833872 777516923 682772314 30758893 265942568 413986962 105234571 213921414 507701956 281507407 694010562 349998436 693368081 933974946 809751679 103493703 236028680 316525980 850890164 625138276 94803344 354291398 602077190 5378256 712115741 330588446 929441237 537982414 872915156 104020048 640872524 365265381 881536972 176161192 396024274 147479539 590148154 501258846 213917307 97850109 635282607 907927869 300364899 181167041 694419168 110116578 137177099 930447849 279158912 988067263 408102478 373962256 194875014 10179667 231856866 906990755 193284467 161298102 444973169 66199622 117834505 938362047 431465003 999371477 114523238 827489278 999367370 557187746 181264477 65801030 507554210 816547084 826245254 807919109 997714126 520664421 770552041 134891224 303628623 49710952 975474841 711731101 423673208 170349854 574427122 655530075 77340609 767711589 669344531 374830132 833911211 787179036 165708532 117892568 639066866 132748125 797898200 490950589 689935871 979162677 556751620 50006434 648226114 235513227 710441898 498456593 756177648 480993938 485864171 59806271 383221245 313855365 624053726 806894453 484205220 198480848 314940881 414062183 966192437 984285413 641408669 652620002 623980802 807117201 623028924 263047668 939865326 420927123 753998257 482317551 252606153 163266230 532323985 753348621 398779457 95282236 104321568 7473459 576276175 590185739 919796085 959497420 904041105 543849810 618908226 240762678 594847012 786365462 507341215 413555803 623167228 148749883 66175804 247148029 955867084 541721082 362712051 748248764 962648205 116710308 230566314 67770711 132492892 615406653 821119332 383788704 710688890 925440900 391262163 139481418 368142993 163574601 98978837 124700451 707424411 570403417 217979483 154787777 209285232 725320698 568343580 832452460 874070581 487035738 79600489 682454018 28756819 294828894 283219135 843921378 264055556 513785449 911692089 396548449 129192102 585327774 780337153 692397346 363285028 24115669 831878764 583944375 187690270 783373955 708644826 747631035 206293725 926624309 902418812 415578958 504461360 470762391 248031417 231048294 957798129 180148260 913502312 839071302 474977155 49237801 682992679 739032711 563023250 447201121 988097514 544731706 885045250 620951020 89645405 100846631 645066689 921524169 684791006 685273313 704898123 245952185 432904348 911191849 25092847 187839513 179287160 529554207 658601905 427318577 760602501 468916387 459983192 526621166 160504043 934960347 575858967 843496722 526509411 138882217 143214197 367123279 536130277 28259446 988074299 625775683 129106077 485657342 399816205 666413437 170930654 104714328 912365622 456351356 868422531 937458469 644190870 47709690 467012675 155309128 327544621 80131529 624225515 787527813 606752695 784729558 575004513 182611662 480742634 954030279 174010233 476473185 321153557 562656864 357248985 161744209 40948900 338871416 647401551 440765106 5284852 818332206 397995788 917650474 127199915 118934672 707625296 771390785 19160716 27154324 926699913 346705337 107285853 403441782 986749505 714038548 40687693 414270371 896650210 521430327 368300649 923176797 997903512 541970560 485833661 207668850 703714770 526782561 546540266 351116320 967547667 551825118 21964879 218059808 321991945 149164795 336994480 29617240 920555580 356155196 56771564 699771847 702860534 16573771 103213628 542126392 730612320 143901321 956396763 479778883 517848003 177213766 402955680 368267868 719184326 741305695 575936719 422899095 120604609 122476984 626531770 88152276 526818457 648496649 158728438 848810402 650177798 495722919 730943997 423249732 851878115 640231915 123021578 407255002 656805687 78751560 949381394 239934360 222652881 905778157 719713243 740500884 82991922 122668922 108768752 654692602 716490971 537221825 77591697 837095581 659698809 556639821 777764211 39033619 57652823 936492649 887844022 707830622 432215567 471304372 131080353 136610036 964052641 106618285 543865038 473374681 185369845 493246432 713309041 408022726 251540942 433022284 1039964 187049218 408207560 962325071 841741820 124698531 499546895 771849871 814310466 11762057 181006045 592074676 50795677 238658869 381083678 791156053 946489491 813299246 114976778 77569843 949909282 79029418 36704482 346290673 552404100 222074327 839537105 118229494 630097053 943594401 551251778 483653371 130643618 811975693 445978441 824901793 789190578 798041690 449268017 603501043 809803748 630274063 48092072 713115779 868932932 429175750 504271831 667938776 94991349 619248609 598024973 897416985 550794381 634729455 243707658 103198480 856803782 935761117 73944329 339417188 879355518 625196107 823070560 862515490 289688153 121565354 539933636 78878730 919607045 841718008 534896127 581927146 324508424 582988199 295042924 45957709 864680304 651831109 713896485 959671653 123596071 311921457 709604992 674390452 946650912 953312650 630105287 655971047 741590120 704049616 995388235 473461991 181762076 818458794 188493835 471450230 940024149 728427471 550328960 712147547 422661832 85225087 294074692 747170256 520729640 441633970 793127965 237926297 93465078 507024449 50114304 217061149 671462260 759719296 891451601 470629525 565548299 374073241 126600571 307138418 78122856 121988806 780600410 259884933 792963954 969094245 731335163 585504456 550038069 134180476 150168356 972699902 71921917 444243048 572386511 445167912 885877018 365514476 683094209 831858450 725055279 733208513 48919598 396517539 492927808 792887554 867147064 58476106 19477148 846263990 218130879 97600005 820769150 851247643 210001292 466249457 672858241 941336455 51753913 75412663 928033285 54438623 48112564 999955203 498681672 473015430 297639468 237075043 838529906 980733677 68933493 416101538 713942190 970369446 812619077 59386351 615773353 532282495 970378813 635250502 231062838 41026045 585366861 51831987 892273688 795368153 518081444 565131928 589220961 422351711 640544591 517254245 476790335 541173510 369725801 827988361 14188939 667365269 65063403 705235199 500615300 986513251 121336736 67073843 809399051 786472168 126460194 277688757 171271016 96839006 765455613 402333854 137865051 350822473 306682195 882655093 146190625 824763639 300303374 587927940 99631704 940847966 105182185 428938393 334537829 327424340 256926753 201243122 847305964 174506510 758994675 347921263 13536115 732847765 414995106 675451520 371836286 393971654 953140277 543107302 343327015 571112244 797957510 333708420 921934717 104639704 216363513 920641697 781919698 516666887 361085990 881551402 310031206 318784529 163006148 497085389 646208870 419932901 698328511 346031187 446955765 309839539 693952450 460491880 42687304 961463910 135943399 414523590 355435563 941600031 810147247 698762578 365228628 608104756 32470998 139679698 565260815 101350865 60321394 347180512 470534106 273923739 81248267 780565313 592708268 244254415 130167055 91433491 516703670 828495567 437464678 963659435 138335105 131417127 276667669 33538763 945397391 265127422 300578708 153349308 59243806 110725954 852111886 424472434 571347064 737099238 564152133 136607878 690966457 476989881 336304744 161500563 750913620 417553011 794582230 343621888 514323780 924749285 435055379 31027449 605761205 872520058 994686885 596612665 856453539 123870907 630151428 654367284 388998329 930730136 807716592 448242136