1 0 2 3 3 18 4 0 5 14 6 0 7 88 8 1800 9 116 10 196 11 9801 12 377 13 2881 14 1189 15 711 16 989 17 3596 18 477 19 6901 20 5203 21 8473 22 9179 23 3956 24 7067 25 6439 26 27709 27 41309 28 10763 29 27117 30 20569 31 10207 32 69091 33 4976 34 15376 35 114953 36 18650 37 204469 38 37225 39 16279 40 130300 41 74450 42 10877 43 81589 44 121393 45 44461 46 13529 47 119647 48 103973 49 212533 50 40753 51 335789 52 79523 53 278963 54 185179 55 33919 56 660631 57 317249 58 22577 59 318092 60 928531 61 291931 62 407884 63 178729 64 250277 65 90308 66 62023 67 738289 68 1167724 69 226229 70 1476578 71 1428129 72 252053 73 241399 74 107869 75 75008 76 161027 77 468329 78 299153 79 558207 80 448219 81 167693 82 785152 83 896438 84 49769 85 249331 86 810703 87 9392179 88 55277 89 1600216 90 165169 91 183296 92 748327 93 330338 94 254717 95 554273 96 286579 97 447921 98 5734444 99 337171 100 1603033 101 1994481 102 75077 103 612463 104 1357999 105 509437 106 816281 107 825847 108 381923 109 549337 110 2449852 111 712423 112 412163 113 3265124 114 960859 115 153679 116 5211799 117 2288729 118 256283 119 2377289 120 3300307 121 3843436 122 3077212 123 2819113 124 11952727 125 5007029 126 5364787 127 5910227 128 8644613 129 32576 130 1032256 131 1383111 132 183749 133 411601 134 358336 135 10874642 136 137549 137 1009856 138 1647979 139 450181 140 6595063 141 462313 142 600059 143 3366464 144 154289 145 7757504 146 1800724 147 3163627 148 3714076 149 2400236 150 36035383 151 2131891 152 3597619 153 1916491 154 1776377 155 5400531 156 1642577 157 18021897 158 7658719 159 1478311 160 13402759 161 4561709 162 491723 163 7299641 164 3465547 165 637981 166 13542517 167 3546629 168 850859 169 5505044 170 10203799 171 55943837 172 1179697 173 5951129 174 8363359 175 1800583 176 14720047 177 6247469 178 239777 179 10037033 180 717949 181 2698603 182 4685017 183 1435898 184 642251 185 6697172 186 1156339 187 24441436 188 15421204 189 1798949 190 26780396 191 11822588 192 60905221 193 1755289 194 41269447 195 5370031 196 1608983 197 28300073 198 1192739 199 2791489 200 22822204 201 948433 202 4189007 203 6435932 204 316409 205 27576611 206 18063229 207 5584949 208 17128327 209 8555009 210 65382349 211 6026117 212 8532721 213 3731323 214 88059743 215 17065442 216 888731 217 107567777 218 13360519 219 61165393 220 11418619 221 5152619 222 13605587 223 3554924 224 5342941 225 4773091 226 89734501 227 20440813 228 9546182 229 4942243 230 54895909 231 1256293 232 5354021 233 32018339 234 2302823 235 3916729 236 5033419 237 7416089 238 1740509 239 9226409 240 65149129 241 686407 242 15666916 243 4880731 244 1144331 245 11733413 246 5494609 247 48981717 248 2610997 249 3204989 250 15698407 251 7324868 252 63050567 253 2272051 254 197392959 255 105113611 256 2777063 257 16480953 258 24949399 259 6343273 260 1514533 261 13606709 262 4757069 263 5049617 264 57056569 265 11610397 266 53924764 267 50746184 268 5529311 269 170437023 270 1659529 271 3472789 272 38393437 273 880207 274 5208377 275 22117244 276 1466651 277 6638116 278 7037869 279 3685207 280 24632812 281 4105649 282 4299593 283 1897873 284 8679553 285 9614641 286 632249 287 17201699 288 2883203 289 30073889 290 18982108 291 17053889 292 47801917 293 11537909 294 5681257 295 3095251 296 37011553 297 11362514 298 687377 299 73851849 300 2059789 301 107396777 302 23734171 303 4119578 304 108746828 305 6879053 306 39799153 307 78852289 308 37065663 309 355181 310 19933933 311 6186393 312 753377 313 5804503 314 3906991 315 4703137 316 9938132 317 8287147 318 3526883 319 15669943 320 23218012 321 19341089 322 18080411 323 31756979 324 30140359 325 14107532 326 14905753 327 60280718 328 77364356 329 23797127 330 74038441 331 35873281 332 166812823 333 1313407 334 76091077 335 141029487 336 1909507 337 142685947 338 10502629 339 4083091 340 5259589 341 10507256 342 2268683 343 10519178 344 9189883 345 147030196 346 12247927 347 18149464 348 38088803 349 5778937 350 29480023 351 23380207 352 4334723 353 62530291 354 9743381 355 31402879 356 73098049 357 17332649 358 17443847 359 50653859 360 112119859 361 1548007 362 125611516 363 191882317 364 4129217 365 39012507 366 12389089 367 30552112 368 37166548 369 1614799 370 155993841 371 109440428 372 2690843 373 80530876 374 121249459 375 3339841 376 90390628 377 21526744 378 5008643 379 58187849 380 36744229 381 5165011 382 146983633 383 20041289 384 8034041 385 7038007 386 32330497 387 287288329 388 3443593 389 82750859 390 21110959 391 6887186 392 98516788 393 42221918 394 21783221 395 31673333 396 37879523 397 113784137 398 103495783 399 13242331 400 348406663 401 65368337 402 5673923 403 30880207 404 32141119 405 35185442 406 43748297 407 45391384 408 63678799 409 22695692 410 120659197 411 11491619 412 469892329 413 367906268 414 5354627 415 169795429 416 16057339 417 389103131 418 44187541 419 29435729 420 243167203 421 10545391 422 242910007 423 21269761 424 4598333 425 307778203 426 6326899 427 32188331 428 59546239 429 9842309 430 32282053 431 14060801 432 339185527 433 4462573 434 197728319 435 13505269 436 1486949 437 398187423 438 6001379 439 120548297 440 26777164 441 11550967 442 56942091 443 5947796 444 3850907 445 2356759 446 64739329 447 191890639 448 7064963 449 30807256 450 40047199 451 9675949 452 65925484 453 28267829 454 50787287 455 73536389 456 116115889 457 75385309 458 67723564 459 57624043 460 150770618 461 203149148 462 37581851 463 28060147 464 192908839 465 36014917 466 15304277 467 127214537 468 15431789 469 5233201 470 198052879 471 122395499 472 7851203 473 61217108 474 57557749 475 210055691 476 104656564 477 62809624 478 489581996 479 31404812 480 476333461 481 27531961 482 115523767 483 211099877 484 18356237 485 86446133 486 77099839 487 521329833 488 41295547 489 11388007 490 789441907 491 73410581 492 18981311 493 8686771 494 62642809 495 578241134 496 4825547 497 47438669 498 72314479 499 75904793 500 463342948 501 11956039 502 193627303 503 111971564 504 1991009 505 12140407 506 147549427 507 346969397 508 14163473 509 120406693 510 6071209 511 15559111 512 280944452 513 12142418 514 11409743 515 56653892 516 9335059 517 448145246 518 152353879 519 14521769 520 704260244 521 101566877 522 108822163 523 39070831 524 902314603 525 16409647 526 34729859 527 186712389 528 19690949 529 435288652 530 131277176 531 217116329 532 65638588 533 54711029 534 671851993 535 78763796 536 597357001 537 236498987 538 167391379 539 284462837 540 218844116 541 296660341 542 372275017 543 42140653 544 1588633418 545 711566681 546 51504281 547 2978200136 548 98332159 549 17937223 550 112367863 551 63215849 552 5979803 553 114723377 554 179519929 555 344200429 556 71748892 557 47838424 558 1236046493 559 18617167 560 1201793941 561 1363228948 562 24821033 563 412556129 564 191327464 565 30417763 566 342604012 567 155102219 568 17744633 569 456771188 570 45625519 571 38850181 572 215243397 573 32952389 574 23307377 575 70978532 576 26082137 577 1703277676 578 341914372 579 3992839 580 469575553 581 163043339 582 2662277 583 319488203 584 7991449 585 195653149 586 296571501 587 29285047 588 148898353 589 24800749 590 375704317 591 231752021 592 19289993 593 61232371 594 189021667 595 4222159 596 231545668 597 77184629 598 2814377 599 77159972 600 8438389 601 17221249 602 16888636 603 4332007 604 63157361 605 50637452 606 7219211 607 287011996 608 82308133 609 4418959 610 121267372 611 20211629 612 8837918 613 104040308 614 250479553 615 22543687 616 247398628 617 99636161 618 30060293 619 18271837 620 180349496 621 32160763 622 12179579 623 187909019 624 3064049 625 278108291 626 128721049 627 191819129 628 101192881 629 67427669 630 751654469 631 85763684 632 514869343 633 95563687 634 736199689 635 380023907 636 11669039 637 358360137 638 477767959 639 1316403017 640 210249199 641 79638509 642 527335961 643 9867553 644 1156245661 645 69460717 646 29587277 647 359556581 648 78940424 649 50224021 650 197371588 651 187483507 652 58602671 653 92611289 654 35157979 655 5119519 656 155282857 657 83715329 658 8533403 659 234410684 660 163855976 661 10429333 662 277866019 663 5240407 664 39982847 665 429726236 666 10480814 667 602710261 668 41914009 669 24336869 670 398556556 671 41923256 672 239874659 673 244495964 674 36674923 675 32620309 676 660081089 677 73349846 678 25370753 679 43986043 680 228261409 681 146699692 682 14663819 683 202966024 684 175992919 685 27992071 686 269516407 687 102667049 688 3733277 689 102638612 690 11194369 691 924050836 692 279793681 693 11452633 694 410668196 695 14933108 696 9544091 697 44777476 698 74434519 699 1707891074 700 160323052 701 33599493 702 3789483127 703 35371057 704 183366523 705 641275636 706 62879699 707 263410559 708 134397972 709 446611257 710 274971673 711 12065761 712 854920433 713 770253188 714 52294421 715 1924947925 716 85885771 717 1355847539 718 289635004 719 171771542 720 142948549 721 12414253 722 270218176 723 285897098 724 16552817 725 808405987 726 18622099 727 543061377 728 303993199 729 6339439 730 675705347 731 463202804 732 4226777 733 198645316 734 76131439 735 32234407 736 645597277 737 46494547 738 96694427 739 118314884 740 114085201 741 26219719 742 70910419 743 181751411 744 43701503 745 6627559 746 327665209 747 1090383508 748 4417877 749 480716533 750 211918459 751 365399033 752 476942101 753 35343016 754 2087376653 755 70703876 756 40612577 757 235977471 758 288446479 759 89406747 760 27073549 761 214148897 762 79473393 763 20860531 764 357584089 765 3190742171 766 25496543 767 715168178 768 472634269 769 315793997 770 222412903 771 70964857 772 419515504 773 157540697 774 47307341 775 71692657 776 66288973 777 586420489 778 21511043 779 203289257 780 337074379 781 212876117 782 1464948619 783 236621473 784 1626314056 785 596105729 786 813157028 787 799500077 788 645753907 789 74335297 790 1647868121 791 1291507814 792 22297283 793 4101653749 794 126329239 795 2583015628 796 416146708 797 178378264 798 5939919913 799 15243421 800 3418301423 801 2913489739 802 30486842 803 3277693421 804 853786249 805 1003547763 806 747061573 807 391201063 808 7178313547 809 142254932 810 6689114361 811 47150137 812 1204230259 813 15777193 814 13096091 815 274462889 816 13147931 817 7378763083 818 141981769 819 36671969 820 1420820092 821 36811289 822 824688127 823 94297036 824 94253353 825 40636447 826 53924921 827 366559517 828 64711219 829 49231309 830 325091576 831 16485493 832 38291753 833 296579681 834 13738187 835 292601189 836 329849144 837 341931419 838 230780332 839 109905496 840 804229381 841 84468841 842 338059567 843 984768443 844 101364623 845 247361993 846 211159519 847 742255097 848 1081155532 849 152051969 850 1641247658 851 253396457 852 2044094293 853 3125349077 854 123630427 855 34926937 856 662935729 857 247260854 858 23286899 859 211519597 860 61125979 861 150503671 862 94016327 863 122251958 864 132797963 865 44689591 866 292197439 867 628686589 868 89379182 869 129855029 870 822378589 871 345266459 872 1921652413 873 241346579 874 4143398517 875 992997329 876 3018982957 877 1224631519 878 428969683 879 27674611 880 911768129 881 738771149 882 24599849 883 484322701 884 156877759 885 18714301 886 335306837 887 491975944 888 56132309 889 18880681 890 233924359 891 614726558 892 37761362 893 155946629 894 1126947007 895 280703933 896 1057133692 897 782354429 898 3442965343 899 754758377 900 387157759 901 673810227 902 3191250373 903 434255663 904 935888167 905 736240149 906 3019033508 907 3543906371 908 1356803671 909 69109771 910 3101071984 911 998106113 912 29615363 913 39856249 914 167794999 915 10207634981 916 6641189 917 236922904 918 548028437 919 1184810468 920 199283068 921 40546279 922 7286669289 923 385287404 924 27029627 925 2022744287 926 486408319 927 714045401 928 486584764 929 148629869 930 3754544383 931 72488011 932 249111127 933 891742459 934 62133377 935 186002513 936 298747873 937 2740222397 938 41424109 939 10531879 940 1488020104 941 248533508 942 17551883 943 127518673 944 263409439 945 3175942571 946 95643239 947 140415064 948 297553609 949 172202479 950 105358153 951 1753500793 952 94786911 953 403693309 954 828700759 955 10902319 956 344429581 957 421432612 958 50884481 959 688859162 960 348919976 961 337188818 962 1081088108 963 494309656 964 2677982481 965 803588213 966 678025483 967 3088829899 968 2938040983 969 44862997 970 5553774263 971 2028168873 972 29909309 973 192366751 974 718070984 975 5249318411 976 101838479 977 134635409 978 565714309 979 45815437 980 769467004 981 754292219 982 30541019 983 1031848931 984 80172619 985 81160411 986 251935081 987 190896029 988 54102353 989 122164076 990 255039349 991 320690476 992 324641644 993 141409753 994 1042244047 995 216409412 996 172832381 997 3436255549 998 320731513 999 47690497 1000 772991876