1 0 2 1 3 3 4 14 5 100 6 115 7 196 8 500 9 189 10 333 11 847 12 1022 13 1352 14 1671 15 1920 16 3432 17 3757 18 2937 19 1444 20 7730 21 1092 22 427 23 4232 24 8668 25 15000 26 13037 27 19197 28 20902 29 1682 30 17999 31 16337 32 27856 33 32043 34 31873 35 16170 36 14298 37 47915 38 5603 39 12792 40 8260 41 16810 42 18949 43 51772 44 64526 45 65475 46 91239 47 50807 48 106040 49 26411 50 111665 51 6222 52 66690 53 11236 54 22419 55 49005 56 126636 57 85728 58 127453 59 97468 60 79990 61 85583 62 178279 63 136836 64 24992 65 207025 66 166001 67 161604 68 33898 69 111297 70 58331 71 85697 72 15636 73 106580 74 374845 75 211125 76 315742 77 343882 78 450775 79 355737 80 493320 81 290871 82 206105 83 523564 84 182546 85 462400 86 377667 87 267699 88 563068 89 673285 90 512997 91 207025 92 485254 93 513453 94 96207 95 696730 96 843376 97 442223 98 834897 99 581526 100 270650 101 255025 102 943211 103 31827 104 593892 105 269850 106 875293 107 1133451 108 1170414 109 594050 110 872663 111 546564 112 1152984 113 1417359 114 437209 115 201020 116 529250 117 31941 118 323259 119 920465 120 930380 121 907742 122 717053 123 580314 124 163990 125 1156250 126 564879 127 241935 128 582464 129 1337214 130 1980329 131 1922032 132 925066 133 2175747 134 357979 135 939195 136 1172660 137 225228 138 1961693 139 985371 140 1574910 141 2551818 142 700271 143 799370 144 1659048 145 2291725 146 2715817 147 1220394 148 1942130 149 1931487 150 2609995 151 889239 152 2538780 153 2231658 154 2173941 155 1830705 156 754598 157 961311 158 666047 159 2941500 160 1306640 161 3680782 162 294705 163 1408157 164 3747482 165 2377650 166 3967979 167 1617562 168 1536388 169 2084953 170 3184661 171 1647243 172 3273934 173 1107373 174 2711471 175 5181750 176 1597816 177 1389450 178 2377633 179 5158601 180 2507970 181 3767515 182 3254939 183 78690 184 3891692 185 4757275 186 5775517 187 2028202 188 3722870 189 4660740 190 3312327 191 5180302 192 3769568 193 2383936 194 6434881 195 6221280 196 1342698 197 4540653 198 4088139 199 5385736 200 6601300 201 700887 202 5548029 203 3255511 204 7821598 205 6471850 206 7312071 207 4470579 208 2959944 209 2271412 210 503993 211 4763747 212 3925074 213 3917496 214 5622099 215 9254245 216 3063996 217 8428931 218 4730053 219 4716822 220 4265030 221 5567874 222 3424831 223 2138347 224 4006320 225 9230625 226 8483473 227 6904886 228 8145338 229 1625671 230 4124659 231 10911054 232 5378340 233 2714450 234 9565725 235 12602345 236 10322286 237 131772 238 1180599 239 5140890 240 1313560 241 3078293 242 6159241 243 1023516 244 277794 245 540225 246 7313867 247 10249512 248 8372108 249 12421614 250 433325 251 4536072 252 13544790 253 12039511 254 8407271 255 8097780 256 2246272 257 1122833 258 16231081 259 8250963 260 7609290 261 14464359 262 7390363 263 17776433 264 15770612 265 13974775 266 12209229 267 11288226 268 15418174 269 7091378 270 15146991 271 9327007 272 16282600 273 1973244 274 2151857 275 12039500 276 3448114 277 6828881 278 8287595 279 5085612 280 19926620 281 12633760 282 4008677 283 20983318 284 14625574 285 21308025 286 5257967 287 20345143 288 20280144 289 18124057 290 7404657 291 5279322 292 20520154 293 4378299 294 15617035 295 5412955 296 20823748 297 17406576 298 16152045 299 13320749 300 22791950 301 14314958 302 2491951 303 9304221 304 21710008 305 21302725 306 7534977 307 26012724 308 9484354 309 21134055 310 27600323 311 2127862 312 27159340 313 7935489 314 20233373 315 12470220 316 14645494 317 31151590 318 30312767 319 23201508 320 19867680 321 12297189 322 9107609 323 3553323 324 22057002 325 10456875 326 10459219 327 11478027 328 11728788 329 13097161 330 20888989 331 6683221 332 3233182 333 4250745 334 20512775 335 28976495 336 10128776 337 113569 338 10908417 339 34055940 340 13024210 341 30233060 342 36068403 343 30118144 344 20430332 345 33604725 346 26321429 347 29861432 348 12841606 349 33860678 350 37581655 351 26785161 352 16246000 353 26790935 354 4675337 355 39849105 356 8533498 357 43648248 358 28967747 359 29127106 360 16355940 361 45091066 362 13058605 363 46833897 364 11482926 365 36503650 366 29429023 367 44043303 368 31768152 369 28911519 370 8115321 371 35924301 372 34502690 373 21982382 374 38520691 375 36215625 376 32233164 377 29136445 378 46941237 379 10485793 380 8301270 381 2517267 382 4171247 383 25083819 384 40643008 385 26532275 386 33588753 387 24612039 388 36230858 389 6960766 390 4796987 391 25531127 392 20511540 393 49012995 394 48278197 395 25307255 396 4576638 397 56739240 398 30309887 399 31287585 400 4642600 401 4020025 402 7634449 403 1948908 404 19477042 405 24986475 406 49657251 407 13251920 408 36181916 409 30612423 410 30845653 411 44483763 412 9958246 413 34966645 414 58670079 415 37923945 416 23099024 417 57268695 418 65860289 419 54950593 420 33370330 421 29953729 422 37677635 423 66979089 424 37670916 425 76585000 426 64715861 427 5834528 428 72785038 429 55457688 430 23492319 431 31950892 432 14059512 433 23811103 434 61492313 435 59896020 436 70081986 437 48124188 438 18914227 439 25439172 440 3786860 441 25958583 442 49198357 443 21783639 444 47798006 445 66140350 446 46856535 447 7660686 448 26037088 449 18144090 450 56429985 451 12610862 452 57068842 453 34339665 454 19632547 455 15775305 456 43699924 457 11068997 458 11080621 459 7444062 460 40970590 461 79057812 462 71509319 463 49090501 464 31666376 465 14559150 466 95109433 467 39910287 468 94399890 469 74786740 470 2224651 471 32464146 472 72679740 473 84142443 474 27891661 475 48328875 476 91506886 477 83123928 478 80472015 479 35563355 480 95823920 481 37943204 482 40671881 483 4310292 484 84403066 485 85621900 486 44029251 487 14941647 488 32082340 489 110315955 490 115656317 491 110415098 492 66048622 493 19443920 494 88408919 495 11156805 496 98877848 497 66198412 498 108999833 499 54531219 500 24953250 501 74381466 502 93393835 503 123215383 504 44743692 505 96654475 506 127947413 507 27609699 508 80171798 509 19431075 510 79100983 511 103403916 512 33983744 513 134830251 514 91924529 515 45141295 516 111091274 517 97827774 518 30027091 519 61236291 520 117668980 521 69217455 522 9255669 523 41029350 524 25627006 525 66005625 526 93524639 527 71098624 528 129559144 529 8675071 530 74535649 531 118235646 532 21877170 533 132101385 534 49633787 535 56729795 536 127061212 537 17976612 538 88194069 539 31085747 540 145353510 541 80779956 542 44469743 543 33417849 544 152271312 545 121483225 546 60649225 547 2094463 548 8208218 549 82081539 550 102978315 551 102313537 552 134546756 553 71865115 554 141286341 555 9097005 556 2060814 557 172498444 558 81929559 559 80932579 560 11709240 561 136064379 562 17762289 563 81144064 564 32385538 565 135351400 566 14842499 567 73774071 568 80900524 569 111050023 570 174248981 571 41081166 572 179094006 573 41152287 574 162860159 575 55294875 576 96464544 577 188437814 578 168684353 579 17881257 580 48062570 581 158991231 582 135486787 583 133607276 584 43981332 585 134266275 586 143896693 587 127835099 588 67364318 589 104423221 590 63326647 591 131797137 592 121406472 593 195165195 594 183400569 595 157278730 596 49493330 597 2971866 598 138300955 599 72477802 600 168523900 601 168680867 602 172694149 603 82660446 604 22861702 605 146043975 606 101855975 607 124167313 608 148433776 609 143707557 610 85054313 611 99303386 612 176146554 613 40207283 614 172526323 615 175319895 616 3478244 617 52915771 618 15407461 619 82379615 620 76251630 621 96924438 622 31950583 623 76849542 624 50619608 625 224218750 626 183073385 627 237580959 628 194299746 629 186742552 630 154979979 631 77641395 632 203108684 633 115133205 634 189561877 635 43628945 636 84738838 637 24346140 638 153495463 639 255745053 640 171012160 641 125729586 642 248497121 643 57055962 644 229795530 645 15531600 646 217208779 647 54419170 648 163996596 649 105300250 650 272226645 651 17577651 652 126964286 653 185914324 654 116720143 655 137802830 656 69750184 657 113667570 658 249353377 659 185872268 660 166803890 661 35827522 662 44809123 663 256009494 664 234491932 665 220670275 666 101742933 667 32476897 668 157665702 669 39984123 670 174691311 671 117062660 672 105381136 673 183889174 674 16069169 675 80888625 676 13381082 677 275914058 678 124233443 679 305209142 680 135705220 681 174994527 682 147112453 683 309748696 684 310977294 685 241181650 686 112064519 687 227648442 688 235212408 689 72632313 690 12005977 691 7639696 692 133762562 693 175563234 694 118207283 695 3477780 696 76354796 697 214241769 698 234478789 699 225410025 700 185154550 701 313513838 702 196579071 703 264896024 704 346755552 705 199969725 706 156348993 707 228430993 708 14350570 709 227211812 710 44043643 711 101272707 712 225503572 713 56937328 714 268114973 715 115127870 716 336985758 717 99906780 718 68700751 719 347914753 720 73406280 721 9357138 722 283739825 723 48267480 724 281307666 725 249146250 726 12846691 727 172828983 728 67690428 729 353585412 730 306113309 731 212675678 732 264847238 733 153127365 734 365828167 735 161352345 736 387788464 737 19554084 738 36438873 739 45328043 740 185522810 741 223687893 742 324171267 743 334541694 744 4661284 745 310258975 746 350522645 747 309322989 748 318536174 749 244596436 750 130049975 751 313020555 752 235579416 753 227561871 754 156775073 755 297097030 756 349644834 757 44697822 758 233906291 759 274982664 760 279654540 761 332994575 762 52107973 763 299817035 764 7782486 765 133041150 766 26444999 767 240610201 768 128766848 769 167946524 770 382902641 771 13872603 772 338916106 773 26291276 774 426779859 775 5525750 776 456795892 777 19606818 778 411504037 779 406583470 780 127399870 781 125042005 782 277629159 783 385837344 784 372474088 785 362956525 786 328116617 787 206869246 788 173450226 789 380570205 790 335144307 791 242138547 792 244224348 793 487357975 794 380028645 795 35098455 796 275411622 797 63520900 798 357305431 799 217694741 800 416645200 801 26519508 802 463002217 803 161905678 804 235035866 805 320124350 806 37454355 807 491912499 808 41174468 809 522930319 810 220400973 811 57879448 812 503597006 813 527015055 814 418217327 815 395346720 816 25616824 817 44054274 818 26510969 819 428987286 820 323724930 821 450933429 822 406530923 823 445682482 824 74382892 825 209178750 826 437007277 827 465755649 828 564713526 829 37111014 830 237822639 831 488459307 832 379237664 833 516253416 834 499855537 835 448455120 836 384441706 837 415670940 838 328401723 839 146415568 840 7117460 841 493682138 842 557435573 843 40035756 844 261189726 845 220633725 846 454389279 847 183656704 848 466758280 849 425515404 850 522823305 851 343271274 852 388155154 853 454028016 854 446443323 855 357861105 856 406386428 857 154234290 858 199038125 859 141673152 860 627341190 861 87087567 862 261299351 863 260669150 864 180777456 865 485598025 866 372059145 867 533242281 868 519927226 869 595822029 870 205379971 871 176763353 872 38855012 873 234989775 874 458231645 875 669309375 876 555865070 877 506086882 878 233273623 879 632280522 880 406002520 881 136604336 882 180654033 883 294722442 884 441422306 885 467846400 886 212802579 887 410693418 888 62466508 889 158064200 890 161030637 891 378151983 892 638652822 893 586922464 894 278580383 895 294136380 896 257472192 897 54177006 898 599294217 899 329773877 900 26795850 901 548777476 902 128447875 903 498603189 904 578254900 905 556117975 906 285603061 907 241858806 908 479288254 909 718313616 910 209057303 911 743609216 912 126776360 913 727781516 914 745832681 915 572271195 916 269057138 917 360741381 918 115983027 919 661291263 920 451431580 921 566910498 922 347149133 923 259838345 924 438054694 925 662253750 926 736273247 927 527914449 928 508134288 929 450507402 930 352934969 931 689074995 932 2895258 933 720187365 934 717875667 935 273807270 936 738550020 937 798951790 938 428924285 939 17931144 940 667500110 941 363047210 942 25282495 943 817219831 944 626988280 945 124555725 946 645747641 947 696820593 948 110996738 949 135990751 950 556921635 951 607157391 952 360113516 953 711127647 954 541245381 955 78616555 956 867629750 957 170653197 958 49903655 959 355916547 960 774559840 961 702799481 962 685911217 963 747768537 964 725470250 965 674206900 966 98376635 967 462869055 968 683747284 969 728007762 970 363685301 971 350736852 972 663904350 973 852056100 974 629858039 975 114655125 976 792939976 977 171815220 978 228448249 979 777295651 980 306553170 981 513259200 982 625266403 983 579773400 984 832016444 985 716996275 986 512976853 987 658027965 988 767899782 989 350167318 990 562517967 991 21605782 992 183612720 993 437151369 994 958343729 995 601143180 996 659142010 997 468178239 998 592220683 999 619093287 1000 731406500