1000
42202385 803422673 887092317 306957738 706102810 618430807 73384147 443242265 33015838 29540346 11306381 301110230 785283424 5526585 56672805 388153096 276503985 28936002 422004770 112315975 540304627 426116221 352709173 43174944 745545505 289198262 66077145 504129542 120254266 376104953 324659670 872567939 624866795 217729027 680832914 338523468 51437256 221203 451992956 68566293 50179342 973898223 236196945 428711456 151062591 587035964 159634008 817051619 1702578 46313854 3690427 756094993 23639943 399652225 207666975 165200255 955832890 120658789 210842959 16905022 204781540 321938798 678996047 19543536 91889010 73405837 248483430 36388507 68047833 582882110 359048289 376988196 462203214 393886 239575560 653109496 795666606 165120542 73058112 935207692 498823458 19922515 121975561 12292242 119737143 25547313 207824137 220646376 46756186 508813307 277460799 447293106 1901299 4811418 4511249 60986093 418041914 429440144 420363662 271242558 142181887 187998005 535881008 461549318 17668680 149252739 369395921 2749712 342308063 157337755 205650943 492969873 581533439 517737106 181741965 170789779 73266825 26816402 168580596 373538136 16255887 144129533 296394296 9738918 87700596 329460000 320735983 32879535 299379053 662199234 57864130 307868085 67793549 195112054 302870165 167629993 716957115 110754694 223103689 65086280 447484383 866585090 107448746 964908691 230487608 50527168 792832 537118852 14895510 179006271 242887292 277128826 514267433 15599604 670143786 188622689 500706008 22507804 381518755 113115767 247364954 59732229 256193899 320501508 136935261 379819165 482856448 182680676 458560355 276475123 47872352 615442597 472507028 773875850 449013648 49303848 447895208 321971054 304280088 333676351 338944610 822764713 27511253 16928630 203152218 9441397 473777986 121632210 61798772 55803095 34342514 409527909 169750972 508396253 60212962 67132710 347121063 110682277 631288079 168271293 672778128 284969839 571909035 19649167 188128948 39634171 651593248 4470683 110868579 142313144 100034066 143639987 528676056 504012535 612833538 48845183 117770451 90576283 737582667 135135950 646838568 101756816 266366595 115881016 273217577 183977551 49554087 7262926 99822060 44205934 741082631 50687522 350598765 282462402 529118294 50778624 385837791 281007299 587908784 121640517 631869279 219198038 136442371 10606836 9511564 149070393 116786474 570187492 90400645 206977456 702883211 337796094 121334376 13872127 41518466 356706646 235568465 359853173 931146604 56317213 11443848 64273941 27345659 213755515 492428050 95115640 497547623 390165924 58709620 618485498 3419581 445086584 726849487 48401449 875525508 18631127 123951930 189544472 138527521 584666257 125777486 268237693 776433957 493606613 155530396 117737249 56694831 533863959 73119380 495693761 140715798 740315860 193331508 133145118 674934171 20850434 290050706 182334790 106513458 316124993 2311950 760531375 213155354 253881009 281194934 133183407 654516243 756674997 200144727 96693179 790215 658972345 766965114 392566970 45848698 71599650 68571678 70200619 254615006 413279571 75207791 285320916 16841210 251697799 197821163 705669062 16276697 19726506 215878318 180023525 321125799 94203362 30044201 291179871 161780670 196894744 49560513 393394732 318966660 52870945 108877932 145515017 39586016 365977402 209662945 444074013 207185464 515946877 165301302 358877808 634700977 465841278 264542188 342043393 85437366 233396615 239415120 158941837 99231141 59100859 501170049 637642654 50101751 10971534 289870065 751542717 391568829 196040286 150140928 51527150 770338386 11251653 88028157 91268660 45937904 93723825 563409 10122586 248051890 30786967 75663976 85044999 554058869 577346529 85302065 691712 508894570 34417118 240923056 395319885 76190333 241585953 70932051 416495376 575819160 130413959 116035423 136061003 99170437 390259984 164383179 358565191 798138876 279331997 323231875 543666332 357483695 735962397 48402336 470962349 3030295 389338303 462081468 794666127 301215104 227052862 455846127 94893279 307973586 447601491 394703695 124254595 294459282 256946759 208085312 154653249 9718623 131839119 27663242 63350031 501042638 654405005 145761043 488211621 105290637 72984382 423030253 96552415 401934663 340238269 244299896 165877378 308073 15554519 12247050 282949716 118100972 97369870 228708809 16661660 607502384 205650533 68472744 413179276 94866365 214380347 279529127 269643773 205709283 149736094 144557845 74474794 763581624 54102628 110287241 109490161 55951700 9808135 131049644 22736307 91264293 592589075 363318885 47014671 935337787 681353264 120142079 346713304 87761490 7884377 915733335 46476504 35152077 545484492 317806520 264622228 95352396 477045550 435729162 972534427 749723394 516434648 17581565 39860763 550809933 512150582 265270480 155631106 351594252 469323097 403499211 116548114 489644590 157836723 540153071 386386960 328270223 787945149 9810444 117731615 377982401 828935351 389589189 28037638 141380273 16184361 87401551 216023316 42443925 243965659 290184853 315898161 95873070 208682320 278863956 124798901 440401179 126565540 660877214 619208766 90682226 494876307 489153346 512835 46862863 4006586 783091960 422470956 287900165 754282803 539156112 373433933 96444246 222818827 155309226 505490555 132410035 466123273 459076570 152983750 339933313 23468333 436400 10605464 140580748 375347185 624358580 7941458 349236841 609463888 9743604 30969346 451860869 155336647 106210154 149144490 121254437 225548618 375292024 120762771 546694952 460424197 104130629 64849157 635537362 7092380 371498193 41964895 623459571 502377614 239887156 378381528 123189679 438258074 17950715 514186647 16913651 16672102 15480912 780122590 106838583 6849709 267668941 664738247 56304515 887189556 69704023 52578007 21926927 27116728 2306423 128128364 148687267 52109844 356305955 546381802 20405072 431024011 610106460 26251002 177320508 105170785 49070076 118131137 40042654 297148034 824052240 786437647 105846992 167507675 373185323 868302202 414473934 365369119 9803873 150461554 169933187 67975474 13057059 867133171 50539547 41643451 219972109 711584502 697562231 905092511 391611407 18914234 361775664 167026193 40442844 146664443 30867370 31233119 158035954 221628660 148263185 228322199 217125120 104730972 422069910 65828186 62528174 474181380 379161271 30469891 826615685 32106551 237880814 156297187 296334849 280185400 206453021 11290285 167730049 78583922 70395117 298052875 572230460 88008181 67019647 352285265 270385849 317813458 545160409 84136660 45632804 286532949 85213399 297167937 203600454 369434676 39973712 94613918 349069613 150859434 650357004 79970847 206091401 260095174 14514709 670101568 570535245 351119910 344572165 46857700 166273211 119094981 30465030 138877309 33244536 38667306 815499940 138731658 6697069 32543621 200615472 134145078 293367591 10631078 293358925 228272340 347237285 51416356 206361307 31815268 223790551 119597865 350824620 414439631 34035412 49266751 631849687 156726930 168328275 39615144 228678253 566674897 41350220 66663408 650029445 537651641 47403991 314138006 292305596 232758510 169682229 2072994 36993553 650233526 29687392 257963949 195302166 489981560 104135419 619706138 336880291 82082141 1089662 538777734 119301157 230670383 349222680 398380530 444428009 677494030 331693324 371142994 486596207 576745876 428355655 156322042 93942867 665821297 215392818 197511777 62725977 630095110 153982949 105822925 179498540 739123055 31397064 314236277 84962450 118175465 185727641 67329247 595901148 200971606 2031155 683129352 81527340 171568938 374145212 356042224 95817036 161991710 865977363 9416710 249487456 337557146 35576494 513546306 7696839 93013801 195964404 118396390 203407538 560525625 300014856 18251197 10477192 72078010 214446899 483712365 648328041 361923698 193952216 109279858 518348863 473889537 170375990 19345686 188933228 53633766 39025155 617174846 446130990 406770032 8552557 375189486 110639868 242091760 64206262 54165948 166404799 168287786 740929138 235136867 54531925 250110482 20081775 579557825 366498666 597229192 174870318 45699201 334972581 96048502 100226847 648167404 668395355 67473439 954430294 209653610 286331816 19642143 245094729 369187612 8222216 84120050 619649073 467028814 71833310 90555661 118454619 53600510 107422586 117787539 372022489 5820990 934802226 196297415 86968042 355103953 13957309 144696865 246773607 266049692 67287774 291141775 103413548 101533571 296597625 268697328 689191239 654884088 519502646 627903342 267767221 13603358 455588093 10136900 284197399 404378578 124422236 651082682 59739369 416603868 101231526 386969724 997162553 61828453 744207239 72189059 653560957 238528930 111331846 759119837 469508739 54509620 205188151 485280752 218044610 282875617 14836650 938217357 169689650 80718830 98854701 271216193 232263910 580837708 763355474 30481552 154074867 4061952 8139835 225906749 502346147 59651949 70002442 105838578 280037960 340686683 534212792 750643079 801212623 77624721 360905572 416341751 622490610 447636049 287567967 365724287 202195018 177543474 477707511 727990800 30369863 85949753 391081700 359544747 80428465 76495112 135919378 564572287 116689060 856519979 499369660 221301267 273438544 379685796 143442048 259599414 475660885 396970203 100727169 97340590 328552297 274648778 34724189 127483948 888361533 79236482 33808965 83839850 716451936 8646570 137150706 301967113 94730750 470204315 249543914 486298214 922464408 127671127 1011603597 297394208 376423140 105981143 255317256 256826174 24484444 194946066 259309683 626517302 520623205 209471556 144289028 23104246 96015443 781356542 604753166 209996394 265204850 185062479 112145116 7609875