1000
245517116 216857619 233411388 865028603 613893447 378829136 154209738 412001461 599818267 947835121 841439881 107349652 499255334 681989723 586124259 618211977 181953253 419698256 939679977 254416164 361862147 929344060 812574445 730382521 321132536 34005311 956482169 706070568 745798303 26061118 290388578 837100835 356667678 651399593 792373158 595106454 636528104 823630353 85079054 541395828 341753325 680774314 931482056 435526893 801322271 583783794 486093009 948397646 454253269 253566145 15176003 434368474 143639220 989891352 701481936 555092825 590838727 480154138 936069790 714061215 316882772 362458813 998386987 578278021 276787817 725521487 155840548 350767837 734088153 49311996 349053913 902215445 795540342 583944699 647132164 605467935 617237859 109249158 770241038 867081831 837581705 555663009 722829449 951902832 81407954 759051210 660289900 307642192 432605497 12938516 791586395 513281647 631597027 755318881 354272673 817866993 831125763 564984326 11953632 35291262 518368862 498756487 1355802 121835715 885971348 445514127 816980140 506551897 67280069 207561819 321228888 99511124 843924906 80151040 385930252 578842385 131315151 892842759 410334068 790487403 291249938 165013261 190421971 959883952 133439273 25607210 815757924 106876513 850921336 303032111 302825582 795034016 249044986 883293329 76680589 23168773 308192025 693037305 130703632 730815172 850892809 808657103 383233731 791958970 634638343 349456899 936200652 651827246 550581508 40610553 729763160 223087284 898163755 677344919 352915568 844435803 352577745 868147650 980496829 182214670 201038734 180477412 322633616 132092746 147439968 351967928 918768404 730736468 450201694 346887035 231110892 783931397 67175482 500787 979996064 443691892 82268978 774358334 157227037 903224775 216988415 20086451 140331584 406489563 2139242 310589390 725232834 120865540 508435813 177383514 486613880 756690710 356546816 964632106 620116535 915400713 588802444 165968720 794718249 944499454 738426988 937444352 944398539 61818773 138076161 954574468 980502961 52171154 946628817 826971752 560750796 230498581 923223198 812749194 357744339 242532341 175679086 285276734 929561784 563646764 588698157 34100437 789451029 296564070 82410037 974775392 697482583 206899392 439495217 742918449 585426647 811511908 562965322 65332661 610494027 510021385 563029938 183374672 778420651 50662632 812779219 425351979 956474487 457751338 980426157 817280120 187562648 380568269 205105802 389162214 769577003 525953554 689625887 492700491 695066237 864558005 993871520 388596932 895046868 277336554 996355148 370976957 618453465 385231321 108632228 460553722 678659806 849464093 766793946 758682436 296622566 921337331 18927385 399222950 337837592 286155963 635418845 249506855 291750999 455086055 572854893 429987832 376605208 857242921 747752836 191601435 494209734 424603528 784029059 957012077 801945678 596119440 387308684 56389606 411702569 606109880 691427087 999593562 372243059 848177810 216846663 160760056 841155430 475591845 875486027 897408473 137933126 561226106 171228095 487328240 837160906 42605243 737498881 428639836 531708047 785992970 610221036 490925141 256424522 730984496 199370561 909599115 440174176 967884852 481486661 76228624 130320235 868943934 315918184 670834193 812445056 59891154 146271126 597219724 357359792 691892989 497598156 724937422 773129713 641532330 902531905 544147592 186031685 695635286 561360302 284285828 544599270 691420788 251582409 992441693 297688786 871710780 598038644 849397158 750198463 920942067 974416755 893975530 382732357 759607616 252930227 749219717 908399245 126691435 646638062 158349082 639269896 943022234 265663489 740619463 747123909 514057906 74332087 556764507 491544440 195961184 936136308 695838712 651699113 895008186 540249464 608803125 6742635 260989521 824683179 619517404 342646549 624206663 308984167 263154535 78970314 214962493 517131654 593763911 848387503 455494930 390570991 349754814 250107344 212034701 359283460 187675944 174454291 925512144 506173163 196398754 378428042 712112136 322679297 598124303 974894088 493547862 465847876 311495503 600954875 531673053 367453779 170933574 865223538 559619918 38859404 769091799 807493402 801045360 125751854 755024805 22477018 372922526 352205044 389115682 128004601 809897099 25070280 970636368 719067134 830346733 546419877 824653395 475090142 511076923 801689577 911855544 847925995 367188135 12102051 424298567 146291678 373151781 210638550 115162918 795818380 938981737 48181388 552816279 365383927 442727210 398468688 709692202 726869289 115673209 152220428 322652246 100037968 664219729 186107896 793044951 850217022 182808853 254518841 417421430 725377914 418817322 737874653 251001099 300168718 605585434 750850737 254546068 238211648 970790408 173369317 696968955 160692034 698784979 32705230 685966037 752270356 577736557 384346486 724616664 914704556 652589987 825971421 335635571 960219889 523577902 768000868 567061140 970601465 293860669 40344425 141502661 991956940 724882808 751339630 59112221 501208721 293334666 789463421 923706302 365711107 956524871 560242764 698821633 613487252 641564566 763521797 475735741 10339238 330498388 675771501 358010730 866099329 507455609 464251516 97579349 573603400 208360852 997815231 775266015 622210509 807879901 873597865 397317526 532490854 136318610 986025775 341507888 202475708 825038148 775089385 226714106 687173221 273634757 544481104 301454155 283666558 621594790 410985785 944661299 17279181 147512018 159745428 169972894 113119673 483633113 643129323 226550687 968688593 417791296 708652259 346657869 767079681 210963362 532651645 26533419 327497645 312598861 544150730 467721016 479401358 100638303 386782825 264452985 552424504 123601599 479812228 106999747 793450395 208913736 463113567 129694302 45905111 644409364 79499493 84473464 312170844 402355668 986962963 51673784 173951734 726198118 674659515 951810242 501057867 60505037 463634571 1980822 798926890 99874687 121799318 932212785 983677856 690339860 716368825 310445123 786883941 735909038 297905344 645462051 926432832 930038114 754107188 469331346 909714211 310760237 194729737 626107652 206837956 71731739 368411723 102484350 847606256 859137998 996320490 257403310 20690705 154004897 470454397 345840940 93251401 195654791 668906745 986072323 483499785 189090137 362949188 143023846 498337707 907507274 313448009 585550942 548811653 496172537 785792592 189392872 944938847 660193632 548455915 590364800 297707964 251938543 485354349 372619901 390186448 675204225 846035728 823235858 499371896 983690101 908175047 440591987 455906984 732262592 971803573 768886738 804040725 763383209 235775541 424461046 612663905 420178142 511855786 661172213 71421754 892893982 345052662 643139449 685543877 742444398 621031449 425415937 400087208 196144571 521308280 649565855 427976942 66619856 324882468 725885274 887725536 361762285 349484414 181982994 305937003 863264325 842346014 347584408 522246634 952490466 764025910 68705303 462973655 281830992 243477487 998388720 834962369 689363022 656686014 769607945 358621125 3809931 637679880 325738112 249174610 940867302 509295441 588868462 545437266 736284219 566006078 128389723 846543162 721744764 953077235 442873976 415566581 956800271 870691941 754350702 117040041 642642563 611895572 278255010 591124580 832744170 836078419 677534504 388559888 909294238 600234573 429109196 254231236 561638674 733543519 306168189 624785827 324263043 761115968 90931581 454632443 233404246 350505547 210851001 289052138 697019104 693409557 931620889 534570786 923506595 825048514 920373156 12222593 303972256 156052738 725728629 754148098 693327991 726385515 109482765 215604173 897764335 402239538 315817522 795323641 708291034 628281972 933495927 195615196 343715830 537878569 50870614 429558395 483406388 681206964 471085105 705887348 197346549 263169324 243196303 441547910 324894310 46345791 568042829 732026755 752378774 228757876 531390545 479518845 648191310 776827355 997932195 932456394 345532342 740469125 40611625 822721914 616496070 900099864 118277064 967770015 671686762 396672538 133623505 613778634 54733975 961394546 146914223 572573415 507925740 401901868 595942353 18715970 803588464 387094819 67808160 797922013 969583066 935555787 763544316 645946308 911060153 474240797 343561168 438908529 323111419 539934635 534586975 458853571 362919199 597421805 486663332 678409370 715323389 793571063 265025190 524848059 380107982 654177777 486349247 735308307 711581932 354789670 882236370 822360721 927057368 24936501 518803993 126978685 758556708 933121685 344588141 907473253 833115316 604658186 572492044 605135526 726923437 335213338 688524828 57233948 364022968 139124508 74233293 116667863 345374259 468861868 905392155 664387526 700666030 994475719 715138853 107049817 336519654 935932879 639600838 838431971 978836084 572139339 499345318 72063155 99457805 385177575 739404948 929644440 274372000 393952885 293665093 926696159 236730170 16340739 489601229 886020674 719176200 79834600 245063931 306145414 719283033 489674769 99062458 29469237 920105490 714037653 347653551 938904453 418649109 276964758 132544310 212601896 835962443 331946574 465746912 546436781 178071685 487002478 375163471 637825727 819087577 987295217 813020803 750118499 192060921 411226773 396587654 679230819 206430562 695341607 416836172 321104289 411033624 990716590 308952579 602083095 613433603 998066136 589904612 651440059 630602233 913458543 27179252 691225492 130757121 643740981 784060982 960982807 957143349 358203542 930457413 662017209 286661134 983563561 371316286 765059105 381650964 922299223 696059933 467768867 543533183 791125544 851921803 841621592 733807292 728966937 754014050 747003329 138547652 532156365 315214763 847081472 99735484 570554232 203538700 229642929 722861099 929422116 122107904 514787643 726293191 894006174 257016176 942320095 432632093 291927055 170941651 495312815 171940103 262366349 216928872 123477701 715855113
631780937 388568971 291338961 595680219 832389067 381302895 759037516 58136814 372291055 488965758 641340522 783092222 155789291 501925354 676424476 446247524 69551669 793856499 422778877 791043863 130235323 418507395 331185136 410968673 815381634 23441133 214497186 61275553 982483643 505578168 547227854 927521104 588649935 82007034 489979090 16139797 326449312 440178063 361260573 276130130 230623002 548954805 181154177 133125817 785874213 97376411 381479712 612164771 826591180 633288046 36071873 676530484 922505838 211445547 725091523 588966267 760340191 377662724 345208259 160718277 417519976 515380918 296515999 635110535 450536108 90051370 276631000 445645735 565429831 894140112 602702315 318150579 26278362 439978915 678774275 650475070 966433691 22537808 381318485 681269071 425528103 697625887 894650985 443025696 438446697 317019945 151773897 966259420 74531895 510836065 53809147 582795515 133861176 491528742 961516485 950789901 654956757 363920185 149087344 122995012 237433397 860298158 843609482 247493164 224885686 59176034 925191832 417157076 783019621 780051413 417640494 296363037 802739409 786294041 1676133 12160469 961934799 673786443 626717643 830231542 288627114 364257827 67504503 386356976 495802328 274979289 917737878 422869791 707865694 60613773 231260952 432828102 586917510 875644942 904097720 985050729 615824865 458644941 390347189 336682467 201525555 22873847 636935529 61944916 596162385 294153948 59431990 522836233 665408950 516790453 980593976 579994625 328727926 950029468 16210477 787664099 877878806 561717747 976256479 535571506 167367580 230820557 232070624 579582329 868024184 498610660 351866895 179161070 866180714 73706435 6982419 764613761 614812455 424794293 449682094 802003146 780752720 590618443 353937773 529706073 665578897 970773033 156991568 844599264 912279339 749237961 364169489 361951081 912085087 749741297 584577271 648534055 697927532 196751588 111806487 608332772 631544044 486092896 252141150 245663573 45390843 57453861 199750302 452230782 542405761 583616265 151308893 831802258 28611075 916646115 438496565 690603604 323475725 497338838 553759268 783176757 829882738 334520903 832643474 129156035 911012293 670290579 749750043 205912981 357182817 967734206 268870516 576471096 653053467 779288270 732674523 104553644 104777849 363839783 825802460 265916465 55967115 715419347 556941790 973230043 755827601 106711473 690236802 892570564 951998452 559600056 957561591 258193674 464873304 88867862 384152540 773859906 986680039 956200283 975112286 505999312 549713834 664661698 631948831 446649029 951617998 389854374 16699908 194087506 850593031 550117085 795500929 787584431 208190893 200962965 89717539 161057777 269096565 263475666 700829274 76395488 709731163 827901971 760231318 946528640 985707196 153484705 201500052 504446114 889969975 780479898 469407264 811401337 534890032 695783187 29952395 4679401 408686540 314752919 811470185 458231833 738916493 515457071 580174927 963989020 882759631 4394516 352088533 67600594 445933631 792032083 96541888 845352829 685596718 353605922 123339622 230678900 192296430 597162980 141481294 6054179 685971040 231520851 81497578 936884688 748509609 173586234 99429450 843056429 475922533 880604614 147153441 643016084 841563306 315176132 203329757 514129260 408407778 788809453 1406480 797415285 256779747 256243586 406642249 457144073 122945667 50152700 914115935 383587699 2684257 135350381 419961446 150294267 5162440 804782223 465153426 143629452 998981670 974110328 23746126 815481095 137141192 3540191 249484028 802110412 149200025 108730448 785563039 24233003 965542666 288104687 767124527 201278471 126290294 175191334 176813346 237935915 860564407 47523369 501230785 55467432 602212261 194929866 49061537 415032494 909589558 652253712 220990685 242715604 767460477 346583019 258340732 116937472 762040492 371102486 31574922 512498544 72717003 573110245 733709804 339200544 137835079 80442886 886943432 560400982 345028188 390194176 281391459 609958000 308999246 754064231 85468544 965772295 620860035 595571084 720477428 727196121 647384628 480064244 244895082 971884561 59317855 566846156 281368215 844745228 609179530 912743803 445185047 861327498 281779603 848936473 333155762 335915701 198540989 291057438 65389305 90716814 203149585 689012628 37785867 315972410 745095596 728548099 188027195 672711212 119107565 489423494 769512373 37467481 582408012 317099334 160525627 169392140 665644985 621425416 495438085 381102836 747197542 151520817 163379864 566169291 841432351 835115139 430279364 679361735 405263603 860186553 220260987 872910957 549679575 312262129 738987482 46615855 711676203 505990150 46210935 795325640 852052293 97669248 114871319 178677349 813531949 808472167 609858992 214182846 816578497 372442160 247254894 979091949 411990694 310138840 635911721 961235107 843291380 413079526 50948741 302064212 717734246 467163591 235047413 150617934 981428761 621470211 446403294 400836841 667087931 240347493 647542401 598545671 368026827 843588762 685296632 275389222 983551544 156496273 887442535 912626797 259180742 531508780 166370983 226803720 905240133 423911172 318167285 708984139 867473634 413316398 21020503 782804304 847634287 826696587 475902025 708189002 71198656 835587427 523084595 171246239 483959563 150063392 837217754 546601819 238442690 58127957 848161786 143315987 12569052 661978640 332541234 391174586 760120420 367593668 834770453 358983688 718407730 718196415 713013441 770084246 929893675 171079468 711934021 860097901 945676357 207087568 251829524 713251591 832510050 494995789 237162630 268615086 944251195 26285180 837301697 854007240 645549760 959871987 834090538 303263398 728284265 724695574 725005859 173458205 345395819 677599904 725195295 600115 18083250 685576933 145174682 813879910 705515136 853424870 873826358 668343411 564618976 910025118 566428693 326323934 911090821 541441261 985136791 384886693 812998868 775170733 168162229 637136273 433249262 868309117 263767968 723831638 940111571 786647384 636501189 494034023 925380866 89305405 583128339 824165768 905473690 870060897 965350515 337599057 999437766 927635806 722364632 717093344 26652624 144170235 762244106 74826813 462794713 734152038 201078053 821631618 278506350 15633471 76981234 824047909 514408874 497702456 62453667 826103391 296062682 909997777 526994014 598579403 696632107 405997071 47163582 855163390 65049482 130699963 845614397 594593166 9976664 31495364 702886113 372247887 936898971 715692265 226077945 746027456 427088368 922467783 134281784 696022641 863696976 565271750 260846756 344368062 355150477 504036190 133476917 169984230 491610368 460695314 209246376 390728127 936961621 577113038 393825735 48937618 106522174 471326520 90707438 508806181 153757818 181549724 651004667 682585258 741930743 36639200 993437934 558347903 78479258 571366930 452484092 874506593 995147398 610556078 166171366 471896441 240686157 542246101 628685157 839892671 73824092 831124426 103138452 613506655 671133963 690421444 88917023 224537062 335879046 706708043 416674691 922246882 272280221 794844686 661820437 727919128 110345535 114958625 525538646 382330561 697189059 160070589 391620495 423390435 813090353 412042588 229802786 376532816 242648038 684322106 28208662 753077338 448006766 19568160 97015254 432019909 673234499 198820901 993269429 675610121 15410580 222458345 412088792 380501725 318830110 579587763 713593575 461596751 171751391 972669913 587457248 181888941 957733520 529270668 515465246 427979968 525748482 919548142 440017363 202233335 499648438 324999767 940829770 122350733 590625329 644455027 6824688 789265408 764901847 739304711 717191571 728549380 703112673 333500776 619371505 939207016 276285071 292733754 153369476 863800468 966604795 692172513 65271921 341269204 726687032 294841265 125352049 330755195 701403385 644033264 174785250 224980253 571880137 540609565 755615859 134062427 357589965 66572841 157555898 13159175 810013572 93643307 212732276 773034134 407997599 687734771 517378818 449486614 13177996 660768775 753517326 893502465 897322311 753199092 617073919 467886817 725162457 458580572 379111592 217121158 287827739 274681221 823302952 120209653 767983243 63925900 269396898 977304046 559840502 640574671 957989362 716465881 493665366 408404850 25291229 299868674 623108347 761542657 12330646 969005397 402473623 124737611 809241547 744307418 896538347 478400757 840348059 620908956 55258354 487554327 329830061 363570097 65275159 849164959 687442654 384717287 536862078 432427303 32531552 840822150 309825425 793084826 695989893 390035688 471187562 39624322 411340245 184464599 94307710 914605938 901250120 328576371 466502314 266734338 843868504 482335583 968105475 585874707 906266219 621998378 647169259 315510112 777362971 93909616 755088417 344460412 922093883 5257646 440978319 141705618 226534743 659920793 864262341 884972652 470124721 843303880 305099853 954676116 718395426 511670763 466562701 352321187 630281101 272157733 267107093 250451059 876935933 506872690 565066056 106951344 486856908 217698588 473492749 222704926 431912604 705565524 791031462 654535347 569830106 99727167 787642537 335520007 292417600 919828655 623797265 413242892 342178840 527890278 728530494 870973010 744279331 3446053 212756005 41771131 202589458 505660420 96190970 913320760 345406240 392593115 191035236 485429284 458946052 584626339 138491828 638987406 932898678 502523265 205784294 628541650 539591795 363158025 844799642 550630567 258320412 207136691 834198243 463590462 952962975 630036138 54614076 945869610 425401370 983588206 934709969 772267335 53801467 482337717 515320549 184170015 133451281 903604364 541783296 391904171 814695656 732140692 270618401 37653286 726580991 84568480 293732450 155119377 262231304 155412511 268872909 521519868 156630259 447609353 377130106 914488436 100973188 588091920 898854730 9153790 530660865 926663695 17926668 544276675 798585790 950807599
