1000 707
564597114 291344539 90969340 37911662 980979402 390230423 245849303 733126606 710505325 940638610 505113443 113540365 478772637 542241946 243940818 474773714 722150768 45728306 112788262 650677417 990453311 872579693 845373538 461852607 534508939 523265721 424552959 177789871 286464639 121118493 501591474 613847840 879417457 716410125 275006405 287503371 500537462 499450506 234549900 958059389 337149118 33323542 190260510 235813415 990539198 103053252 571497442 821992429 732815121 992243456 98249916 159729007 366117549 751900904 892639806 287378975 84438325 328744652 165483228 929848095 625417606 712523135 622788991 812074505 838227042 454761435 935492765 327262681 141986476 138306751 259373815 625378178 427461402 679835075 903285 930397434 69814309 125153938 226491274 737060445 481101967 546540019 251522736 457330108 876681891 752918380 324272874 607275512 924622819 102754443 974787262 419156401 449861528 995670197 227128814 767555228 291666133 762580375 776333676 922206136 273349709 729385467 380582864 847984689 478575858 401083417 575111115 400144656 996100437 957031831 232209757 757493644 353423701 471315454 262891181 489596628 361113441 16590759 100804520 229733593 359809765 471302186 887865030 293798743 298589847 981816090 371934785 115522219 944474168 505557995 728379002 9912600 516738714 272518382 777192732 224430868 123179645 605089329 464490350 887218946 118236128 566443498 233618148 644102546 141867263 279923386 361801239 308866489 381639324 499005237 947308579 568559669 264125732 546328923 472428849 260046342 811379408 145973388 815617587 368372361 750343186 784119482 287833763 596133024 494971619 181873041 186211600 233217741 188399519 904192227 435841215 396187846 738592219 853700897 526584259 977471097 886683221 357867299 830908803 12917685 31605444 727788750 568419047 485438138 609161263 887421810 961575147 169229091 23236625 243247549 531103773 471641736 204781362 135775797 53662907 360334001 587488527 15563720 772604142 801780429 774865452 100704087 30288410 595857946 406946400 262231317 44509631 30014975 247838652 109695152 192880705 699215168 215182580 891062314 339118418 54677749 277418042 281436644 962279911 398431709 352407117 978682617 894172514 442667952 181041670 824860873 763746867 281119880 61345534 468169708 462761228 825861644 5510442 768692084 810290766 238566024 950486039 252717491 35107370 548472984 933846360 938015005 773853894 119927937 358861580 772061982 908876553 737600548 296257267 850775650 409295313 889200371 96711257 883425459 656938956 900915904 29600825 980704840 484905277 332429541 683191844 929011326 821237597 947560315 149941393 648182278 754090362 664590742 719077022 358558552 559570533 745303926 584644595 602560953 91270723 786318980 600471044 153513609 381522206 814592656 867580847 723381618 313098880 545945303 576595081 259716516 426571404 97674205 876261941 484833316 253916673 144621562 78802355 761773163 748655715 924558931 412896617 820321300 589098359 330458914 26389333 146004343 952109795 7913252 877618374 663658133 623867902 187612085 17029838 716554329 377976473 575432809 978796537 470017479 681330355 767539246 160987859 981066224 460596753 128594140 966737745 550518690 534708176 313222888 24614534 27955378 619772090 29346270 271216530 577622006 98845957 82915448 402908446 43928264 558523103 172878535 17040717 459864677 559046811 500767659 511203142 915266518 793908385 419669183 423549820 107778816 553450433 230915926 742009301 945408686 897145869 595152039 380034579 355342619 601633490 892711516 694610908 300574208 43270674 881094696 800760508 121133733 377430180 938229354 670238939 937686359 471664070 345269846 702339147 17548755 724330978 353041440 191571014 180811014 662174240 266067097 851323440 625682880 235567204 443098186 758183472 736312694 633825111 637037034 955126033 300557204 260246581 323876543 154277775 798146409 312121012 532163051 257958780 127380592 756832764 586723116 733109306 137978940 669684896 868708168 216379116 129270189 861806804 669408118 956571554 896810374 531605819 98123527 649372728 530232183 500692099 958090874 283557714 277942778 286147607 281067940 313420521 470052399 190850002 947703290 901923633 801013692 858398136 271185630 461639363 231585359 367251418 198616749 939078358 429725500 222373470 807905675 553541959 152302208 54498153 617059685 191202199 472290386 604026932 646320810 662183652 403485200 580995816 759822209 869601419 321007525 993405218 722167389 763861839 959658383 465091783 579241746 833934667 634560673 120387393 524801202 683270698 485950376 518337791 168546821 178065886 687548952 972933617 606171865 338437416 552885756 615423408 306426976 878594238 394491407 506688845 433193858 115137848 657485095 818739081 725893625 353213767 312953454 983066868 614736493 883825447 370374263 853449332 485211671 356253180 81917501 757129781 578677620 986329059 896442120 526321610 953405347 470732153 334635138 14665827 170126100 700203768 976640597 858477566 796705007 247457188 293176458 315024582 4490042 500677022 264204270 72080152 954945273 89642478 474266793 421110762 294314017 261218954 342392720 406037302 229196835 454386294 565304403 976273396 217167058 944259822 695891557 139730150 472763108 882585980 159009812 80206658 988406342 507635471 397729768 163909900 389439670 365892144 442853451 743340232 217571100 424505480 962827305 806951287 424499051 718815710 586163392 942839446 339220821 534156021 480557692 802147952 904090420 322907112 167613518 345745843 793401590 400510467 462136405 410915739 256941192 103253219 686469762 519098942 244332582 96803220 153374443 889762141 330156153 61844785 292882929 449694426 730369768 284694067 766004749 154869417 105831821 783836692 767880157 714932400 256568397 145947891 226556206 632765641 705752364 792555162 873752306 773332223 607241550 92279591 939130503 685512719 665426433 716023917 854645465 862166264 520622192 508044333 885720620 461094001 115147947 965116323 386401037 796512260 289410466 558730990 149235846 330617073 149413915 845237996 442864299 455436393 442435536 92685186 910711745 454904270 941090286 871968402 19076599 448282149 259134731 14349150 8446141 611485318 881412619 995830003 532110198 817248590 161134561 617237945 830473101 914398887 71741321 813581677 853624827 498639354 16158818 591220284 454890354 731292808 353966820 846426165 648998670 58176400 550216016 774803859 353806234 447503434 986058649 660798559 429343790 764633014 484695960 539501923 628810459 158514854 99160654 409526832 881420467 76872991 566002616 689300688 675689210 953706183 922639649 795252810 642341007 389786429 71734518 584291501 83578540 304200677 568231265 541045605 116665222 300726911 42884483 738324759 383661991 259341508 978112416 964020387 549710248 661948727 884811895 68777847 452855580 10777761 930655451 997046351 29914546 220505575 719450116 312562743 955357892 208414018 469566727 928101778 253855048 652012855 651504221 504386324 381974082 557650817 338542272 317872846 357387866 614175003 411669420 419600363 450895202 199228147 166704664 656605096 676273763 373840567 840198088 785066376 734292082 415394957 419585273 508271377 166136372 787466477 711819210 447878093 52659209 966221135 501946368 793028663 949796031 826430406 351495552 953920464 733673989 388850624 934706580 580080265 116170753 693591740 609150819 673458482 563148866 952936794 493582812 288348634 511053901 291361533 398787603 918004409 135692846 799305647 210120828 203356629 56371539 570046878 831104260 745763739 15205316 353036392 227185579 434382250 842460209 575396610 916023372 467108563 323478080 753042390 682755353 5938756 26493261 434632518 938671391 337581381 211756396 609164059 150091338 775958447 91736151 76145163 668880878 158059733 332237315 665081622 526893674 738402440 982743284 588201782 125083761 982803350 569266240 499461489 291381203 136292338 560620392 686291060 869717206 602075523 673399386 590421471 940970700 545853631 743312292 939095713 510287022 129156400 138727026 73197302 103760354 154117168 319615044 244990210 355685558 592946315 820725142 612425248 503597749 232601875 520824276 489225497 997179611 482061852 633955895 453110767 583141904 803545291 828266941 471693070 152052565 758365494 860829799 166481133 265708541 531967346 291694892 824104776 677150891 177716588 121161457 464922173 179432964 609079312 970107873 184774574 626826689 756765608 253971898 78996247 899746737 946415509 349557779 468221500 154723318 336123084 980322036 116807011 115849327 432596642 572995755 659804032 750074617 94487278 931392591 306269102 110031000 836017582 527805226 646181028 132517333 206373008 772047351 160909798 204292391 904485029 226705263 287020215 998444046 179500170 845190434 999964018 650537977 309191824 640517820 124740191 598066100 461757628 952105762 434345105 858749907 926802478 610721946 134204947 136628969 91136408 368760849 92978666 961554308 904287468 121538235 449369183 99163454 150606535 30962438 593830094 622484873 537623355 315190646 198406745 902726389 603038139 971154749 340231237 264656080 238370767 866453097 510400615 364679593 291649260 253607381 222139923 596887799 879722403 912670624 155762581 135110101 280589979 250741832 386138385 37044589 273638309 302228075 210710639 712208314 771146101 102734300 329016157 299166498 112512956 552965323 540895161 791128608 125488496 989205278 357519609 426173254 881826763 521782070 369161191 872921537 632508978 468579345 514625535 213860685 137724846 889470284 649069600 729359718 856034996 376942442 93212471 487625061 753680090 201838131 690211285 45445638 866660575 323290533 104091933 634084148 305695384 282720244 694291482 985264959 22017984 101318169 734075678 645046393 857978583 546198970 453304060 3201400 434329902 840384671 278468960 407468488 5051872 514234178 186303518 725368451 979864120 723373616 867286076 797261274 266504639 114340998 963748855 965383475 367712616 870186586 297585370 885131958 152807638 651135850 901611074 289372756