1000 412
257444582 395866456 132707520 753821887 570896078 566293637 921342128 672477093 648802308 825098108 663860424 753702636 858423861 167729165 700121047 541530115 375940434 415222655 803325105 903047973 123997370 435554680 871468937 927083042 509141869 60844650 545821452 125795547 922675603 36300388 682679889 694520945 78168486 428607061 252906028 952039995 710766507 411688184 93121048 286770661 261296762 585194610 263687084 834937368 707708565 725687718 51623287 704017444 344981146 54182096 426372924 519008579 73292793 659918534 458401533 978612211 531407725 617026485 970818555 491310538 873518183 598487555 930553188 767271798 270729973 248364079 150167239 748785313 638492362 442878080 201524886 34812474 586482086 131671084 195724834 624488120 65144030 226878037 448924198 917192535 636449806 767759936 94134665 963329316 549718045 10524812 436834887 860659584 255241888 907907589 171877883 964682784 234325952 576358635 896611547 438342974 31870449 417309557 147484508 474647781 518169870 669643657 682640913 796928886 410319689 79303636 240357835 269505753 274347428 735032000 649398617 462928369 712901819 227189163 970285641 458698806 703507808 821542361 421915466 199319646 245539509 917053976 534638764 541181125 726566190 433055125 116592024 187702440 59809200 270879501 224158248 350497594 419247316 786747685 667174415 483300630 9143628 846244035 538556267 837149219 290874673 984394808 335015500 815383546 433229951 35057148 460024795 257781251 401780550 250449806 87393090 90008931 159143712 194481601 493359368 688485188 386556790 138738031 996701675 697695728 769619509 222765853 582851263 965118836 547835059 823228253 49995994 376267788 676731532 819016675 565430177 436601710 515900156 913183073 766444681 628552157 782990398 248813223 216690659 53593609 184649220 282303926 659666539 785953438 330802348 733476827 454779151 676944800 44377326 964220188 422938936 774291429 941848964 919080309 687668595 592107258 819405497 212446575 627524719 416440893 585108413 464697651 970854956 227499438 489713884 114926571 790301962 908291308 231410961 436479092 101961130 831678005 181326987 902743564 342304113 851615931 460682858 198200741 889387037 481101840 592625530 359655606 642610092 639867729 384949045 457449625 669619935 785364310 404115949 90133610 608069117 93583491 535810002 481005942 307906539 510907332 83602479 839125203 122603923 733832717 574905646 599321639 73111426 759284877 453055572 69778426 899060937 370433664 582639070 752391465 976662961 424182031 287880820 979770121 649913431 438164934 934754895 323692719 349404252 944930037 533580549 796908338 847178471 606368285 331334684 622687008 8953535 421220708 990225518 293191754 406122580 519468567 109475000 404941497 736027471 418957142 325059492 992269974 168456730 690861371 118490516 900316577 697573612 702374555 993262216 771162202 391914682 217308854 763738610 785122626 654240324 316904366 420961511 362423289 48933941 330054546 409428960 33297898 29265680 608530232 952241640 959002671 409388209 154358816 579240186 909592849 940734886 252872394 576024618 76583805 172328933 166538507 951613583 489443937 187939875 404280155 128146149 235162102 362451435 485677034 434850841 230254700 977372511 179372092 554054914 642843319 805840603 669621161 768983730 246648510 402226249 69051383 74649230 936690748 119731227 646175731 992717270 667928329 859945266 418740468 345718258 427549572 832780282 565688314 899867393 33556314 923395096 665465112 875205990 808287346 186219900 898254645 793465043 764039249 55635157 445845825 806527047 713780244 576908698 731065948 734936253 378799916 549705561 556193216 597518990 680574498 37021375 701968457 31455783 257371414 812130604 493357384 291056372 349507732 807214257 794281325 703504129 45095420 564947665 996977631 104960940 154033442 66042409 427534612 383981496 68285485 925251901 197708406 226263320 85312192 422240744 854759731 641687797 33805137 496701863 45702953 25095955 929572169 695286501 978846601 918407677 450832256 599694299 196728080 580412680 636740616 835298243 196019647 832838407 326749628 186756528 846328218 422299151 66396083 819269780 761357151 734833967 489098500 844388036 550386621 129443306 827808459 439467064 459561558 708953218 105727769 730161252 640771324 71804912 890417554 711940357 122258384 626228460 3340446 348913075 696911468 304108602 246357496 29009356 6823003 391989813 319967469 306995107 854328105 431501373 667074247 708745616 368884822 145481913 150806848 479962436 128462795 792853285 990705572 248634591 869384398 863684382 935053464 932959461 572853409 112839602 959597699 115700496 490086561 645201998 41566218 517189993 223520510 903577578 58089173 801951906 688955290 501892562 348149144 68690509 36540389 98870476 977073108 448491011 503802136 304571616 714569652 943129435 247276824 665845820 463580185 270530576 695339908 356958624 281129488 80782724 128352436 249688050 41049086 318771402 114468784 641948344 298297442 172553736 227896195 677183702 575610739 117649362 231975871 894126113 123004360 626436559 486666936 577472624 50578844 187271686 719610047 740870653 478008469 236052159 857233529 798043219 965736981 778954581 903577662 939395750 635432804 782693232 257226512 364945182 620906797 510652251 307104687 626869041 462610225 267518065 887640150 800051620 486327762 329098039 532684411 130136080 734608133 59521428 872162479 660009382 573998791 264711370 546692165 851575698 461552243 772431846 749323112 115207948 495077229 555281226 823325318 967373897 450007827 829230922 760619546 872239562 582272820 262756699 229250759 725478407 791361787 339881652 382367227 828062666 227242248 102652215 267531699 685114094 694801245 644904318 556418313 261318144 507684710 632161471 972633596 910880958 525847539 615165835 28456788 184043010 703873151 306162414 542585677 351558438 245570239 311169348 970610580 684407488 215808373 950002776 775105385 503910166 238628907 790257053 78240309 944385070 801959521 374444413 715766856 46278694 667068433 753301600 869414099 734990335 1556467 303251579 774224839 269129883 544460007 703328157 304667841 156405129 492059500 843448223 474745322 860629028 882324835 566348430 378727408 218804979 948009841 949003057 43794855 235281574 910948254 309001038 586350788 441832047 829655779 520729947 581247614 455517325 40954458 206955 155075718 862196459 909801495 23738617 831371270 881550604 978124522 822817750 298026971 936699114 77177444 313963446 958559771 179707004 206246543 54286530 213062244 687742698 229886168 156558851 351174723 167831481 566547180 230392920 515704951 278619060 63919637 213596586 241626156 607417235 261463061 511115943 663227677 650686591 950581054 642048212 746917665 855155757 681172041 36726656 142524658 557711655 893339101 385941590 332709951 789264667 147301521 228554751 26486858 608951722 181289579 269593422 856103729 234671184 255015217 327836988 289582596 63575739 602389922 746386229 715434980 881310054 979908070 16985105 807496428 652442411 611056505 562900668 67247850 905393906 232276284 685360225 493957640 418584977 331829950 578196047 367937728 127214490 54106841 162150120 732887336 223836950 378986099 483090090 857614233 266824110 913150487 100544388 400648388 518508445 587187413 697829771 397999315 96439084 525532204 728952823 247831140 23668168 696211505 698940625 482217937 953085253 501156617 456766862 260657179 65890754 749876804 282682055 661919110 147513812 869546974 500936573 770345690 180803442 906784729 996381698 751752446 419565802 967809142 387341191 67361642 64164082 925026554 598590225 86693223 124303322 548288742 261741466 790593508 299139252 287838563 98115990 500942777 830013837 642564232 110529007 674046419 483005031 898708811 289062578 693671998 236544568 187167178 223295857 48909402 669864379 611683410 793797502 619377586 408913357 906298094 318528309 183617955 731035606 833604302 269164232 581710435 870460738 693903123 293877535 192170192 51252560 631978544 470342624 622372752 299905354 664825299 465953764 385222211 292026451 296904915 987014635 59958093 974536066 131303329 617535209 263872584 906560121 236667330 312935965 347769877 787892899 39310188 765052529 607487093 355314511 743951739 721471733 478690696 93617426 379805716 232581190 375566422 209901761 718686073 625771339 234619569 201762175 419778406 283557201 161839591 272359393 571903291 943349494 262950193 947999736 428274427 831646593 604698647 451521956 904120037 490065969 700177185 374577299 629543498 460829541 505019768 141503854 169957863 270984459 887276071 185101307 792030481 880906154 757764508 689973165 461665811 133334760 262729853 430409516 29818433 325642619 313056211 14942895 265847191 739427510 905294925 440209815 366375094 361659735 820541611 182151109 19750755 488289266 980415419 271639020 309302884 507776348 329262286 250393349 530201663 292645267 512748403 425163044 51854406 610911460 358580672 842562928 93289673 278654646 276500746 327374253 176931717 644674922 29459823 994845367 754214082 230766014 655852459 220773582 692040451 820305421 820045078 798069618 830184088 329011813 709578930 14750073 30686101 429518045 560841167 543483656 757895768 760154431 612221169 660947058 361459130 672126509 182294698 803380626 886763959 774871882 402648335 473253917 223425801 104812576 930746134 814335576 109249812 601774007 53712862 33013471 865285602 788491062 593863758 393339433 190431915 314112895 283462328 515048350 828764735 671560330 930292826 924846381 577750240 26017774 390905798 304671521 635203513 40444902 714126425 843131341 897115482 703537814 303086136 270570213 965693017 769384166 16489520 633379816 673207452 660130531 555986630 750429717 137613134 160977288 729273794 600459817 3041097 517642934 156608905 340478524 409161947 730623822 84354853 434240103 923603465 470068085 18689939 209234460 910669825 738954020 411952811 10600445 384265449 497232649 148728313 537644857 882206837 267584530 373136180 168523357 473472504 347961244 962781361