1000
384529916 998967679 885171091 717281223 149935688 717050895 252044644 363103186 206418020 793583023 942231168 771089081 76837913 644413927 519947959 601254788 224262860 576566405 946333230 482365154 731857610 416709668 744988334 82026107 995003699 684842189 367036584 863298912 27657861 569611450 779466697 166185380 143233476 212523830 726072118 597530884 607834179 48716192 488863077 512337089 891912210 235963534 3880855 191826575 667340037 554099445 585653926 191471708 464750087 847113030 206332661 20085182 725215051 880547702 139521225 331606388 383443640 122492316 769044806 786080045 85235151 712756970 944756395 969325964 974025370 583034525 207405114 898066395 233334724 116940937 105160230 897120020 403432706 823228824 324685702 795290609 596383591 71379067 78227718 260671827 28319091 978151692 991201271 543279463 74965335 419906648 162283240 505406117 469020402 515082843 71538150 812318120 602866706 329089623 644540575 250908195 765599254 798167854 569724186 267195933 685869002 315284054 53003974 766748469 615888513 578007529 798484000 965769735 523005913 45545723 384229799 512632020 510168129 741647215 973254986 438140505 592923350 952953696 253683717 168758855 109848746 970255533 7748594 432272373 522618342 910543325 418534383 251523252 297179612 422449685 329482382 185089744 811129733 413211135 910662647 920453908 14345403 852048590 166637536 787372595 468343167 129735400 991092761 776489959 240173506 613373331 184584284 240288418 221979697 176247523 93027793 468661289 700250558 165289103 190355259 362180228 809174636 342447330 694427935 880993718 342224308 849872435 137049779 40245447 19631560 100647421 292302836 963598700 598688499 62872474 831869143 78706463 661340833 244787607 702502417 174538097 178766040 850456621 153113761 623829007 52018136 225787614 282644889 424819260 337448430 140655853 883691317 138473093 874744434 20916318 656427164 881973646 103541827 78376832 806757491 133227174 679505679 76157543 170306204 255300431 177504905 565742378 720134802 529572288 670268067 530993916 151908861 661126030 215409490 684997248 585122875 368560167 920503341 726403225 939699534 191233429 409705883 73646770 527737223 496302195 501420913 674143685 184758950 341723108 36169224 700456167 758946784 600233964 287793746 75643918 461109952 338937157 498842961 834791320 821505104 862333703 543172821 28765633 194703529 486735978 937522991 140015897 193809578 549865496 41841391 867584771 29091811 321040613 540791516 598380412 874380288 412855349 501126144 961302028 307803399 980263416 895019048 825051455 265987027 964592496 667239459 916846541 416716342 386763573 86882316 851370673 262628762 323047291 438358417 336828142 984334391 645662576 561698001 989679951 526281225 964417069 97817467 44502565 11005443 188062378 402008386 733111008 177553182 276534289 964443540 94582685 751283513 712463237 451513957 940792268 228996909 880827119 399171506 439154455 754028600 811403967 401785999 901642953 416697286 39968805 580090435 814341003 919146088 245536629 908725032 304653073 114357747 142284957 844326041 136756772 315548104 553335619 393359369 518082890 346839341 470357627 431211539 219483098 141903906 125257569 444666115 55400593 382996442 301418488 28274711 841470436 542045602 184735215 512319478 105509658 145288720 715267727 780139445 246738732 193142830 993713987 828247367 221441002 426267375 167081608 542402176 359392571 642503756 401518080 300281540 747313793 495906726 937048912 446715931 112467932 790779420 649791748 579761095 97671713 690462092 887127193 217228118 790108958 988181578 333089399 425387780 504986335 633436770 314934402 253879054 318458975 647068290 35288323 599153134 96282044 292556521 107063409 711608649 35329984 625442864 871453047 20539842 919492362 332479815 676664730 752319973 210639659 921343117 479397233 916643691 173371705 533048049 584572834 479695105 266996052 719266552 69045254 896058793 85606528 791272566 261052526 898180729 335997882 633206454 979254214 423900776 934878834 669410398 816817717 272369736 137772212 701857527 497533689 104808363 50526717 241356076 80819112 727282859 912440709 534192893 68813116 832618460 187152725 269633693 155351316 825968755 509451155 849486761 458717911 22129963 184878916 308677379 437215873 624976517 348404704 76137231 581841711 168883597 481687037 994285507 326081155 355479936 497670895 384363302 414281709 925495447 542258742 566356945 78737447 511488691 649852481 455067180 841970521 334623122 84923392 683851222 139539552 786639328 64415065 588571521 311409475 691352991 938920788 291401275 818014288 644647623 921743060 925306788 862945195 573352234 808193910 763812045 199563755 285234753 541987888 24144629 18282762 977580943 434521674 88118078 780176661 575607195 127812416 117137191 163761072 356884874 947817791 291680400 574711590 438261179 986764716 460044783 765759190 283286346 989194077 917562369 304576479 166671716 242817388 203309438 266759472 486512545 211485851 733544842 481231895 953936586 839479781 509571396 87941480 910013632 318875261 566319430 434632292 650420466 257672067 585877393 606615785 685871117 841021467 734213868 120033514 134911625 832318860 424147561 722126556 465456252 829586904 325814740 935846806 899782136 233905670 760624281 531466728 51532545 201912730 293633362 779364454 761518377 978494247 92402161 94876482 266527947 947553927 531369047 567888632 293245615 399789378 261017729 814348930 189253017 726903211 819507449 845200788 846574774 344261026 63140333 409952509 128956452 577386925 567443305 124799193 156683196 557246775 97641578 162525871 213609798 733745355 297022837 221240847 636127951 494156329 395186649 612426614 625265304 7031808 206160265 598931645 541204333 37754891 881090083 420781027 694502674 310760585 530244594 584872382 35688398 167822085 181222608 474345329 971108638 539207338 2002596 160605119 952024848 377068861 954299938 415462990 152331743 932846002 887860469 70914948 629699888 752606683 578692746 341967080 85835579 405074802 756061554 456583592 687102201 630207355 44397941 187751152 154823759 234082133 335280297 650247651 808644798 689162209 155909344 42223822 300355758 527217248 750061400 379024286 138528867 37080420 251869143 960289926 746141747 367983558 824667697 936254866 521710122 318606355 209030783 884443793 206435331 644574872 526890566 624830090 338817869 162083843 273351819 786932586 926610764 780726846 162890201 990313864 665419993 35856615 943373564 704905213 189993240 550292585 884171436 30490125 678063593 940341497 488724871 92548445 261756644 229757203 20928018 278263193 979519803 554461524 86096406 25044537 501817874 361647140 76665153 268851076 819725826 682310850 562257853 400901544 29293135 174918482 386928311 756176498 61132611 779664014 883228466 735987295 690571777 366197119 595593316 985147670 741429362 627794959 35339893 570083090 958844015 252702412 441888748 298447155 4187538 323155448 591377468 445861477 130209775 757005003 227175871 136305648 473470421 147805363 585958223 672805502 546884602 165275092 711859158 326789169 341713495 58445422 415147715 263089264 184277664 853580603 766755091 552903130 131761565 316710597 255523259 233126950 856922103 589975051 410232600 412076318 157551951 287761744 394823259 997818537 680251607 539713699 445450891 938249054 569889499 321079770 920382207 193519877 801613483 586444032 920463689 385604705 707160237 179622868 714428358 662906969 191346991 399138367 68809434 336829263 442917851 360929726 301998027 362435274 114925227 792238143 585852522 466927614 191979428 851055347 346995925 333150374 490369113 671067952 177523621 79566061 955765588 946547704 720698293 39397646 329727152 169981987 176293376 325489802 907992004 770574124 724141992 435243781 835042298 30848531 369529022 617754301 646453753 643985200 944339625 546350737 290719661 981376984 23636011 54717756 473253905 822457423 205339249 350244642 623982969 820524265 814880110 953210798 780882098 914759369 664807535 704084716 371344069 825542236 953790005 371206625 40612453 521914765 149799425 49092990 509567755 169514310 115402976 427881392 789629228 194023121 951777156 18189226 542322743 433156598 43836793 348549032 641543322 301786089 324896493 574067581 120508978 255147564 260881186 130522406 111236578 177486506 784505298 247590006 239903977 595242584 396392436 992466300 517086026 349755563 475404644 231004091 546857097 780153814 562921891 45436756 594629642 139127912 789161532 881862004 456892055 605963421 109985093 279128500 852811700 866751552 534184453 102693133 607303696 913005883 710168495 485039739 723327256 393836733 216944941 9625510 46412550 413501368 154989669 176425943 423401938 529135811 520902898 730229243 199437152 509880440 533047880 526675621 883660317 729246586 630741305 936985057 955549938 321244041 110314578 968196485 941279271 373879588 450854048 234162930 730902345 218878798 442800144 349546400 653110616 226247728 883424863 850241302 85867486 709541294 178599589 909092798 444377466 148257601 180641680 417778111 654443994 908895484 743951259 443274967 287114394 269852651 414781145 417856778 785677409 578365780 846672256 129750107 364205855 464991803 712234200 832561006 16444323 255401096 525210137 678283711 906529865 389145814 62818673 634026361 338968784 448809690 391661860 908324596 237350730 809182830 645465294 540018126 3652140 424804665 959301828 995208613 95337349 106905853 191978393 664883310 388036428 189943933 829542844 288676469 326670546 633732361 734303551 367890929 935441750 642945704 32577458 692234307 986934711 447505120 588894254 506151115 884695876 849290788 131122541 322613607 3657135 56020443 746395158 268428425 61221129 776984 74907380 407104924 780377132 232761619 370505 761955413 43798140 647567611 386866001 418666338 931015658 627919533 721438516 382175049 379528371 411933937 9515696 179249512 945336589 729009207 497589581 205234668 386155246 928530043 402960718 865396283 287122078 146451482 160611132 586033398