1000
681071218 276986948 606195025 292943410 259721365 597975983 496691364 519350838 646214171 719241246 618435386 301512878 150953043 240688964 349089863 692260627 112629933 435631639 273401282 300893845 812981853 837505175 464211097 401775387 339079024 722553909 737474694 820267454 443845573 514228426 677736096 751870031 259246001 594338116 184673541 924810857 20730625 951613137 792796078 406456076 325131262 971261440 465913635 382458369 893979603 639270139 771201969 474144074 841054166 144733683 820468590 111825027 38787319 11232336 844440591 254653854 192949631 354536261 154493457 676161337 201991906 267839736 59362776 321781768 337255215 141688851 412100359 512679293 657365655 193949757 207546345 428169393 855903039 454034170 758095589 625832537 792731186 950130505 226055099 905169141 231570755 669242091 34022454 907500720 416133377 380290454 506355342 767724015 572758243 422804815 373001774 698009325 946545543 869512240 133039802 434969971 809882643 704497159 880695692 417413285 350389417 173635758 843539106 414853797 242427485 426646392 876346917 163045460 336073937 247168455 261441687 671441208 170027375 583944891 788840344 572343875 62705157 312076628 412064262 715599987 392770009 791030412 184975061 663998555 173256706 409979200 252419399 415522121 7104527 546774518 78985897 676316882 608945323 801856938 101504215 282175439 194757643 330354259 639458043 166693624 10571136 428489741 75437171 112202011 689759276 577755879 452986833 439260920 20524241 423543627 697114300 733679301 229279494 682749811 503729432 856072194 195547380 805010354 137129982 720242778 817893705 351449261 435786488 31435902 263150713 851567396 101617632 777417430 599331594 157839568 996448360 945418891 791072791 182319873 931871898 43597082 251117748 696557566 956892712 639234195 232911446 917004943 865481388 75330513 131684019 768072407 142182277 252419498 581852409 863981844 454873007 620301574 131996624 253548591 409482289 386271805 118116258 455514470 890078062 221684740 589615430 389547847 192918654 922416382 983857955 41758904 150533899 190462878 590074385 313311435 830573264 920496156 774424163 870210202 412653211 752379062 157490396 983628595 629461189 508359801 803166786 632207242 696209259 407088214 968641181 842011338 36117605 665427117 187851506 18806758 382074328 937561968 170019625 892365022 165281256 107947767 954572688 153328522 53774176 119951736 348403768 855593633 441431165 821980550 73786156 583001060 681715291 630258798 107582781 852668061 399041823 640078844 549612227 437887591 269554369 558380445 200490473 917027474 739346764 508183912 678482495 577843424 373578787 551097730 329149066 428740741 568280025 655575025 319388964 754260814 159226799 612227983 808752913 829067998 101143723 678609312 804845586 605068881 688218986 601999035 243127430 460825857 996280251 484387787 724800049 257935340 458378023 183861066 741968684 336113332 863317047 574689510 725621648 60736160 300927888 262498895 57266044 479184760 708523721 585841822 77577731 750018653 590723681 718639465 553609404 638181959 635134348 307493994 714875516 800395365 723442276 649390019 100773804 408243359 949729823 825667657 458564293 389381025 249345330 535000522 174760601 385770589 636414121 673861078 558949563 816130137 341731331 726898710 593825491 645874697 859728164 936193413 882452482 531189739 736154274 387062612 142567541 164031481 984173672 490204079 707035288 876771322 773124733 962878550 977291565 37047366 371216974 678636965 910835341 675830378 410675347 72033305 881300033 830427263 52739340 366379483 842676095 161451467 229266068 442662953 920948080 383860878 409239599 904457299 304432379 676704497 520280146 348980210 11853839 159635849 379517499 659455544 173561230 162819576 443474666 682538083 269856217 246911410 869090751 12228940 621388788 215292637 805058737 406866972 944307030 654213672 613088797 113249872 666384321 559659129 345505710 260226327 129160945 665214716 546394193 110356336 835850532 378396874 370782687 399471512 622180120 518570715 175349259 941983274 11407659 788088803 124865369 638820118 20314615 290622018 932961796 122654937 812962648 523247011 84841582 336089655 284730604 318845664 487767462 369123417 975998603 464505955 463429921 952839911 24296242 596360373 961483505 861469147 49036588 491287334 602126272 491045031 835201425 439643075 113779210 641706179 959669734 408499212 182466032 599091074 722417371 737433714 223578109 545315986 810690794 25729064 801213237 20998454 741796173 983167848 323438281 80702075 24122182 129879956 100657983 149076837 463546863 884792368 456819879 503135211 66087958 613444303 816293510 453777948 381649931 335661318 515279918 345929452 942282748 142603151 907748430 996990582 801115575 826341369 15354033 431560327 337265135 192839674 329028104 606661958 354827180 698283375 409971249 569593242 187896941 141893925 752567394 984770828 386026825 816765732 601957211 697162065 758770220 212849196 441834347 670437318 701708538 460750413 466771768 624761062 480996950 73497550 350097492 349904921 918482466 861206039 832009388 277098763 124323747 836612449 554045414 429649514 647961272 772226787 420991038 525202983 468480061 464505188 223531487 188375315 133449672 427555224 450783114 9435876 557365491 745808855 870771771 290784248 818746443 858390029 750479685 39097409 725416412 64130344 651343914 653309109 166104219 569735082 182403810 280964329 66750664 235046246 760233484 212078172 406714988 70383831 245409343 939293790 233682434 360926847 447744667 602764082 117213077 451444683 857399880 830703032 441849363 279078867 933413353 646178404 964845247 100823751 329364924 171051578 937097865 371252153 324614474 728133511 476294263 274001465 337898105 814258428 947366765 537043334 576648622 618300962 571531017 940423126 158349542 309661922 296787581 494754908 533019253 59308941 343332574 1400529 54903688 663218325 441850598 462149775 213597923 380211189 628870418 646291727 536921290 700729662 717218282 757082109 479564309 883285567 353639517 756480757 297821265 790435402 788400349 656203128 9409084 807858911 875882381 898963145 185073409 404871433 546840550 382785930 718583394 823454494 212305519 903154998 477506835 521293983 346803720 272910223 377831914 898631954 18659600 672211929 584846098 283986550 133578072 984089649 82925813 617353678 371013478 456962930 188467872 97742178 927505630 144555787 711857079 247362631 77257795 357610136 565671046 916869854 598949660 619931735 159815148 202392029 500191477 429878638 716078784 594428636 226130415 803009334 865718546 389612784 733124352 287123790 93829966 503169918 390196427 37786344 993070374 537995223 668362795 253658183 49615092 540050478 964847785 987621000 827418676 485751303 113194147 539412479 441486073 712961920 799268558 59897986 782666483 783634654 391794123 189662493 14306974 581303762 280213335 675699812 860534013 966858852 918837298 41753874 654612461 483803297 956090141 178709408 453883395 500142109 495158181 128188371 953523260 895012075 481346935 846171153 878954841 774400199 124100830 888269463 200251290 311123019 758101510 550027055 914577849 990340669 568734516 923996450 313905089 899685302 830126268 522950049 974213464 174329282 826609695 408631397 604331642 524836895 554212013 293786283 999224305 668488649 683305029 228932559 759381219 64414754 249872440 371499908 907654533 98580044 689207214 120974574 219199938 550700509 551134172 783942150 131227400 238588701 354548837 934662045 85898668 944445563 740153630 726518168 585965673 47175714 280099765 274209094 997958778 106860952 646459309 548354768 740313894 375912327 897170934 416714703 344324587 930446233 37241896 516684024 231441739 2079356 277264220 479406834 167483437 949969413 235264679 507491912 653826034 735979888 367011124 717788794 370593558 494597062 741894653 676247598 649383511 516220198 281364612 282276196 415900519 699028726 87870343 294892507 472266981 883759218 686834623 773569025 519359318 205942680 853649635 970433473 700290257 51559733 144899906 273859619 61176004 807763952 131939858 290523043 159299109 665684671 352472979 644591071 581281651 829498149 684051275 968222521 6522256 815487166 435414106 348064600 337546719 670195012 606729304 64114230 804044948 981333032 92802826 135230610 514764463 226134733 148521757 251143348 108053477 427905469 291039222 530328295 298905541 829228874 474270091 418030387 833786557 881230573 46382266 763919977 383444916 535090752 228270510 978145673 801642788 424138631 921244860 38881977 89790433 134046328 617417261 167266609 227435570 288125819 772559799 722776908 464815671 444050129 74609664 393122679 219463415 81298898 300936112 931359813 143835142 492797519 762544689 299457950 212859414 505024006 955321112 923618436 71742099 673593029 829417310 840605599 681648306 599754956 867825171 576203258 401171229 620056852 538824857 83766153 860095036 580315520 801538730 701436808 289062454 935941608 205259959 253762934 574147153 348930879 66214189 574374882 941077302 881201182 613086466 654710211 937586866 830133850 575729524 461441049 2745163 821066574 576978419 781071713 577738942 995305444 403010193 632737709 369112428 824965589 716490736 387217473 294924040 305737042 236283455 963527613 543522172 785401583 979430475 707164569 649362679 390242078 659498517 118507652 359735553 817368820 532323385 516281742 502470400 690368005 328915604 957546404 80382386 863425792 928944488 16842302 49318225 629808241 199974233 30957105 399082093 806145072 421557648 647341105 481375189 830701930 889244674 816604903 519767471 215870281 322008523 378910891 119284647 999535171 753442740 846353118 933333060 433647100 927674580 835996391 790415190 518885337 574640466 812715720 893442444 978176328 788788572 254733090 542255571 259284419 390522415 881173431 69868519 326422266 609615164 597973986 517715503 780383929 781814793 573505665 983559635 522809963 849385994 948814080 444992066 837501718 132450432 534983375 463126356 252979808 680439474 458490984 599425486 961957638