2 1 3 17 4 62 5 118 6 251 7 250 8 433 9 1052 10 407 11 1280 12 2002 13 1968 14 793 15 3052 16 5614 17 1456 18 5337 19 5939 20 2413 21 5615 22 20217 23 11648 24 11080 25 31024 26 5425 27 1737 28 28027 29 26846 30 17451 31 33535 32 10261 33 64019 34 23552 35 44937 36 30086 37 84870 38 17353 39 55243 40 48824 41 108936 42 58618 43 87977 44 82117 45 117306 46 194430 47 100394 48 60992 49 127090 50 117674 51 104635 52 172988 53 190268 54 127295 55 328294 56 278982 57 156842 58 189783 59 148688 60 208944 61 386850 62 280468 63 289711 64 522047 65 388556 66 158840 67 601426 68 521558 69 269407 70 365815 71 235117 72 1 73 681086 74 162170 75 840898 76 831196 77 148276 78 372502 79 985958 80 613979 81 536770 82 341125 83 943119 84 587755 85 749862 86 1226773 87 823706 88 637687 89 567493 90 1 91 1299106 92 664651 93 445067 94 769438 95 1704654 96 866529 97 758664 98 749177 99 961218 100 1268784 101 983861 102 587384 103 723031 104 944487 105 2302832 106 1172168 107 1206009 108 1454322 109 2289870 110 1309473 111 757205 112 1383451 113 1419767 114 1853867 115 515852 116 1481605 117 1268317 118 3086993 119 1437812 120 1570985 121 3480913 122 1667072 123 1758464 124 1846161 125 1198055 126 1908199 127 2852912 128 1973791 129 2004318 130 2381302 131 3188142 132 1798588 133 3304774 134 4486700 135 4859720 136 4876545 137 2534679 138 1455992 139 5350886 140 2235331 141 3677800 142 2829211 143 961198 144 2829889 145 4516885 146 6029478 147 2714104 148 2772973 149 2546127 150 2637550 151 4010825 152 1155301 153 3628146 154 4123929 155 1225378 156 3564936 157 6209329 158 1298233 159 7330809 160 4703825 161 6893189 162 7474346 163 6449907 164 1452493 165 8515468 166 6886817 167 1534006 168 3703672 169 9338204 170 4862376 171 4975281 172 10026172 173 1768003 174 3698667 175 10435231 176 5398299 177 10618532 178 3940329 179 6525793 180 5713921 181 11719547 182 1987561 183 9542321 184 8930800 185 5249854 186 5024170 187 11151161 188 2191453 189 13463165 190 12732653 191 7695324 192 7013791 193 6971427 194 7228493 195 14743728 196 13479285 197 14317128 198 5345344 199 8192575 200 2967336 201 9806175 202 3087629 203 8287326 204 6626260 205 10580852 206 5585796 207 8795654 208 14231324 209 13802726 210 9304946 211 18240300 212 6413904 213 8284887 214 18531965 215 4189375 216 16364159 217 16424721 218 9325287 219 10327608 220 9220301 221 15676145 222 11524636 223 20671202 224 3713173 225 15427568 226 13993616 227 5344263 228 22078597 229 13158270 230 4020553 231 13442282 232 14633353 233 13178447 234 10210024 235 24443288 236 19820907 237 24093836 238 26145009 239 13694185 240 13723696 241 17829826 242 4685281 243 14243734 244 14065225 245 27600689 246 13077504 247 28541556 248 15138971 249 12042055 250 5250167 251 24750586 252 15765183 253 22578726 254 16420580 255 31328761 256 32608506 257 18757278 258 16923833 259 20099945 260 16527161 261 17876406 262 33891517 263 18065789 264 12872197 265 14989085 266 36901376 267 28788457 268 13379283 269 18741610 270 1 271 37527973 272 37650726 273 20409409 274 25743888 275 41589776 276 30162600 277 40726998 278 7110313 279 14840693 280 21888468 281 32212098 282 12441464 283 41961754 284 19080943 285 42555568 286 27145062 287 44062461 288 22105763 289 47590445 290 48240612 291 40375656 292 46800533 293 8327548 294 24208091 295 50636089 296 50953726 297 25608601 298 23395822 299 11684981 300 25511165 301 50100752 302 9120601 303 54038222 304 26352386 305 28279657 306 51114501 307 31927961 308 31734466 309 37778337 310 48892573 311 26941696 312 33765816 313 49275522 314 10254193 315 30761424 316 31378192 317 31677814 318 17843192 319 32369625 320 31744125 321 25783255 322 62928378 323 64954646 324 33388307 325 45071966 326 30871035 327 19402109 328 57009962 329 35418538 330 28011610 331 70853168 332 34628416 333 71499716 334 73368747 335 30802096 336 21049280 337 45306857 338 77095691 339 49755617 340 76134149 341 79178364 342 38876552 343 73737434 344 13490533 345 63058053 346 49181085 347 40979701 348 32846212 349 76585934 350 39723769 351 70469481 352 36461081 353 38511802 354 42106337 355 82772831 356 14955085 357 42375618 358 72131256 359 68939795 360 90570169 361 83007180 362 86088582 363 28205001 364 53235310 365 64723591 366 38207350 367 69899466 368 68097625 369 88359560 370 50398515 371 84360897 372 28569104 373 101646587 374 26117920 375 55539596 376 98531452 377 28102382 378 40626179 379 52157763 380 54440035 381 55037430 382 54464536 383 18629758 384 44122240 385 66525634 386 46863683 387 72329426 388 71185521 389 102875290 390 32921720 391 111892781 392 59776569 393 80756730 394 62559837 395 61346330 396 118529461 397 110598237 398 61027471 399 56571228 400 62579739 401 126205037 402 50618098 403 76142754 404 62711479 405 45655523 406 76263830 407 59633875 408 62606179 409 129280340 410 47166625 411 74255762 412 97582969 413 117315937 414 63474696 415 141551390 416 72160776 417 117683644 418 67505517 419 45597330 420 71860823 421 96226202 422 58694911 423 80081497 424 93433041 425 70533125 426 75131225 427 125225841 428 81128986 429 82073945 430 69237091 431 116253170 432 27660383 433 93341728 434 68860764 435 86174802 436 158919623 437 28389376 438 153466762 439 133540222 440 144020296 441 171516637 442 101780938 443 62688772 444 48583664 445 165936357 446 81841617 447 73628288 448 134454142 449 59613869 450 1 451 173497277 452 173807530 453 89556319 454 164476360 455 50006594 456 181101167 457 175214592 458 83774402 459 79137703 460 190435645 461 97591411 462 119303973 463 138260486 464 98225217 465 100139698 466 164590653 467 33804106 468 204471514 469 102526320 470 89767440 471 204277789 472 75903281 473 87133012 474 82955530 475 145074832 476 100879381 477 85021028 478 216987571 479 36481438 480 108568943 481 176289284 482 77980579 483 106482789 484 115085035 485 178019228 486 225802614 487 226961273 488 55854819 489 88369407 490 231153519 491 223164880 492 136742419 493 102611347 494 102605048 495 152377246 496 192602695 497 98966126 498 123040952 499 222595794 500 41500333 501 250673787 502 123073336 503 182355095 504 51843807 505 249668720 506 129308886 507 129100544 508 135221689 509 93034871 510 103317670 511 228699030 512 112323851 513 129852657 514 130604480 515 45353818 516 271195132 517 234338003 518 275551966 519 139313620 520 140118217 521 113096204 522 37487627 523 277791957 524 47776573 525 167003937 526 220451841 527 131088384 528 125453125 529 290117296 530 109027729 531 194539150 532 138147911 533 140967567 534 151480368 535 267543325 536 226071865 537 153772101 538 187216398 539 311130521 540 153415277 541 273331521 542 175362812 543 125199728 544 158068080 545 160997481 546 162486954 547 216009632 548 137129383 549 30309237 550 320044193 551 210917266 552 93375584 553 315280604 554 161577459 555 341771742 556 169440055 557 57396436 558 1 559 148932783 560 166946285 561 337594062 562 318349838 563 177863617 564 176916808 565 132333488 566 184199831 567 202815208 568 178849637 569 182676411 570 184885856 571 370512756 572 62165341 573 365303520 574 373918355 575 287973072 576 179649296 577 187503848 578 178553647 579 364365171 580 189406762 581 333428913 582 153517438 583 268170492 584 149274620 585 173676824 586 192110177 587 109427704 588 200219473 589 394308390 590 68227993 591 160747075 592 191534544 593 91677824 594 169148393 595 210345014 596 211066253 597 212082571 598 171363869 599 104580395 600 168200200 601 399403523 602 72481201 603 190533888 604 199390093 605 325389420 606 129167136 607 409599945 608 223364639 609 205983567 610 224094619 611 206278541 612 161818129 613 416318833 614 231155667 615 328612286 616 449962650 617 269092089 618 183790522 619 168265063 620 79186813 621 468535562 622 209057031 623 221702348 624 239165641 625 465084361 626 274996099 627 208153036 628 389589173 629 220204802 630 1 631 490076111 632 233063426 633 212013621 634 203656040 635 273746412 636 402840405 637 505911664 638 86293753 639 468703848 640 128855395 641 369370961 642 146914424 643 106129808 644 352090099 645 489566566 646 464449322 647 216516384 648 453450231 649 340285500 650 91260433 651 546274561 652 457355115 653 410614750 654 235512000 655 365495104 656 136953585 657 304946544 658 264653838 659 95107978 660 199796779 661 465694273 662 546322112 663 226915507 664 286296282 665 197059799 666 164432917 667 287573061 668 273997917 669 329647061 670 511648822 671 411398136 672 519202646 673 349964002 674 299822391 675 82280043 676 377453150 677 210028896 678 616414257 679 320759506 680 278418231 681 517933152 682 478568853 683 416914786 684 144893962 685 642182653 686 169283654 687 180030869 688 498315637 689 355062808 690 255771730 691 454561009 692 155973411 693 589126913 694 337826000 695 413867546 696 659591506 697 674694461 698 113031793 699 265907755 700 342021525 701 326462976 702 595676467 703 649857222 704 660481515 705 327181661 706 488892217 707 344896064 708 353961872 709 645403970 710 126281000 711 695380736 712 313391493 713 330190508 714 202106744 715 723366588 716 257915879 717 735938801 718 559747749 719 471841562 720 197258851 721 440078210 722 153621441 723 436864009 724 349369245 725 126676108 726 359106776 727 664233705 728 382142682 729 458593292 730 746045846 731 364664720 732 666542207 733 659185354 734 581250114 735 309128995 736 390039040 737 365294944 738 1 739 623095102 740 366098767 741 794963937 742 729325151 743 136356598 744 320620600 745 816334353 746 221570000 747 428893731 748 334942651 749 459244819 750 234251000 751 777624401 752 219245103 753 335434743 754 292407752 755 143076778 756 403135055 757 715684348 758 686025431 759 242787149 760 705225127 761 453146562 762 376440641 763 685692793 764 560325780 765 871177374 766 865458631 767 424860064 768 413145901 769 400046445 770 648623924 771 875475811 772 741290573 773 171815903 774 462585817 775 850337705 776 155361925 777 527572737 778 780123869 779 416645908 780 423512361 781 948954700 782 443568734 783 333860688 784 660729925 785 434709801 786 620878427 787 502872265 788 349207453 789 382366495 790 513551927 791 936625986 792 484301952 793 811774972 794 166435633 795 279004985 796 468920815 797 473541625 798 497448728 799 617959098 800 510830432 801 902723570 802 722856162 803 1023225751 804 288589904 805 1042498225 806 515820904 807 692797331 808 410063777 809 1011643921 810 888866435 811 743217202 812 448768159 813 728387578 814 464622732 815 1010899721 816 422966800 817 658693883 818 475470871 819 528170670 820 440158293 821 1023170184 822 554176000 823 1111385584 824 269038232 825 1032415599 826 1104517080 827 198117009 828 512442098 829 1043871634 830 607953403 831 694704025 832 864574263 833 654287923 834 451570690 835 1144788057 836 499433283 837 580181833 838 546480327 839 653229063 840 369748449 841 1125840718 842 795432968 843 466343947 844 568479968 845 1167135102 846 357634144 847 676893593 848 499409703 849 843261480 850 835837191 851 527484321 852 589744359 853 1097022817 854 207126313 855 382853780 856 1209447514 857 602505569 858 470597282 859 679468816 860 938519542 861 656724906 862 1199767779 863 213749278 864 589749579 865 1256266747 866 617549059 867 361897649 868 648836263 869 1029923090 870 512589790 871 861584473 872 361724159 873 202440250 874 1284473225 875 657882092 876 548400699 877 933721461 878 225098713 879 679902490 880 610662013 881 477543141 882 639580969 883 890991102 884 229748653 885 501760000 886 1237892426 887 1335014683 888 1268660611 889 781588028 890 584767936 891 726935624 892 453529125 893 276030487 894 396777464 895 1070785136 896 815624000 897 1087010398 898 696816043 899 1053059625 900 716135689 901 1358069896 902 607089869 903 637018272 904 1360660700 905 890074666 906 578872090 907 829832346 908 248988733 909 105008148 910 682616943 911 1485518137 912 421233344 913 1129395492 914 253960993 915 596290555 916 634852359 917 658092464 918 570184947 919 1121351842 920 1526884012 921 1401955352 922 755217728 923 1368906758 924 783894077 925 1469788832 926 1201227461 927 329716512 928 1508724533 929 795083752 930 446674040 931 800906013 932 1491106799 933 754882363 934 806288705 935 1091784421 936 1051944157 937 820917096 938 795503171 939 933658713 940 1274820464 941 1532644199 942 650635318 943 904297079 944 1496119023 945 843070528 946 814472335 947 1645523089 948 473118992 949 1215622451 950 885731537 951 1699300665 952 899038765 953 1023220826 954 637112393 955 950289561 956 899863616 957 1253647908 958 958896512 959 1332402930 960 688640320 961 1710899991 962 843128989 963 796159638 964 884932903 965 805741750 966 1756954838 967 1285523001 968 905316237 969 708185575 970 931322973 971 1288841066 972 901633139 973 1399089295 974 768907259 975 1491402806 976 1690631020 977 902244231 978 826889608 979 879016182 980 613405843 981 834917516 982 877794561 983 577841536 984 827343739 985 1880198237 986 952007761 987 888827472 988 956631249 989 1930081959 990 1682831403 991 1892390501 992 324741781 993 628565679 994 1785366820 995 327698938 996 769033180 997 1982025476 998 552917674 999 700792210 1000 1976759848