-1 1 0 0 1 0 2 1 3 1 4 1 5 1 6 1 7 2 8 2 9 2 10 2 11 3 12 3 13 3 14 4 15 5 16 5 17 5 18 6 19 7 20 8 21 8 22 10 23 12 24 12 25 13 26 15 27 17 28 18 29 19 30 22 31 25 32 27 33 28 34 32 35 36 36 38 37 41 38 46 39 51 40 54 41 58 42 64 43 71 44 76 45 81 46 89 47 99 48 105 49 112 50 123 51 134 52 143 53 153 54 167 55 182 56 194 57 207 58 225 59 244 60 260 61 277 62 301 63 325 64 346 65 369 66 398 67 429 68 458 69 487 70 524 71 565 72 600 73 638 74 686 75 735 76 782 77 832 78 891 79 954 80 1014 81 1076 82 1151 83 1231 84 1306 85 1386 86 1480 87 1579 88 1674 89 1776 90 1892 91 2016 92 2137 93 2263 94 2409 95 2564 96 2713 97 2872 98 3053 99 3243 100 3431 101 3630 102 3852 103 4088 104 4322 105 4567 106 4842 107 5133 108 5421 109 5725 110 6064 111 6419 112 6776 113 7152 114 7566 115 8001 116 8441 117 8902 118 9408 119 9942 120 10478 121 11043 122 11662 123 12309 124 12967 125 13658 126 14408 127 15197 128 15999 129 16839 130 17750 131 18707 132 19680 133 20702 134 21806 135 22962 136 24142 137 25383 138 26713 139 28109 140 29540 141 31035 142 32641 143 34325 144 36046 145 37852 146 39785 147 41805 148 43880 149 46055 150 48371 151 50797 152 53292 153 55899 154 58676 155 61582 156 64569 157 67695 158 71018 159 74488 160 78064 161 81803 162 85765 163 89907 164 94179 165 98638 166 103360 167 108296 168 113382 169 118697 170 124316 171 130177 172 136232 173 142554 174 149221 175 156183 176 163374 177 170874 178 178780 179 187031 180 195552 181 204443 182 213804 183 223563 184 233650 185 244171 186 255229 187 266758 188 278683 189 291106 190 304156 191 317761 192 331824 193 346480 194 361860 195 377876 196 394449 197 411713 198 429804 199 448647 200 468146 201 488441 202 509702 203 531836 204 554738 205 578576 206 603528 207 629486 208 656355 209 684317 210 713548 211 743960 212 775446 213 808185 214 842402 215 877990 216 914820 217 953120 218 993120 219 1034695 220 1077740 221 1122488 222 1169178 223 1217708 224 1267950 225 1320152 226 1374600 227 1431177 228 1489738 229 1550581 230 1614002 231 1679870 232 1748062 233 1818887 234 1892662 235 1969274 236 2048588 237 2130928 238 2216668 239 2305683 240 2397810 241 2493445 242 2592981 243 2696270 244 2803190 245 2914145 246 3029555 247 3149307 248 3273252 249 3401827 250 3535524 251 3674211 252 3817732 253 3966589 254 4121311 255 4281752 256 4447781 257 4619946 258 4798800 259 4984236 260 5176120 261 5375022 262 5581593 263 5795716 264 6017234 265 6246824 266 6485176 267 6732162 268 6987676 269 7252435 270 7527178 271 7811832 272 8106276 273 8411283 274 8727708 275 9055471 276 9394443 277 9745521 278 10109623 279 10486660 280 10876568 281 11280311 282 11698873 283 12132237 284 12580343 285 13044218 286 13524998 287 14022678 288 14537186 289 15069719 290 15621498 291 16192516 292 16782805 293 17393639 294 18026341 295 18681001 296 19357658 297 20057697 298 20782630 299 21532563 300 22307565 301 23109218 302 23939153 303 24797512 304 25684470 305 26601747 306 27551112 307 28532830 308 29547124 309 30595848 310 31681022 311 32802963 312 33961932 313 35160057 314 36399520 315 37680696 316 39004018 317 40371788 318 41786378 319 43248349 320 44758194 321 46318432 322 47931748 323 49598790 324 51320157 325 53098685 326 54937311 327 56836789 328 58797926 329 60823835 330 62917704 331 65080529 332 67313262 333 69619285 334 72002208 335 74463182 336 77003300 337 79626396 338 82336408 339 85134656 340 88022556 341 91004282 342 94084148 343 97263810 344 100544888 345 103931954 346 107429866 347 111040526 348 114765791 349 118610817 350 122580916 351 126678265 352 130905148 353 135267213 354 139770280 355 144416984 356 149209952 357 154155364 358 159259759 359 164526153 360 169957516 361 175560817 362 181343222 363 187308153 364 193459190 365 199803964 366 206350342 367 213102403 368 220064189 369 227244105 370 234650968 371 242289384 372 250163981 373 258284153 374 266659588 375 275295525 376 284197380 377 293375502 378 302840528 379 312598585 380 322655824 381 333023607 382 343713850 383 354733467 384 366089411 385 377794407 386 389861553 387 402298657 388 415113814 389 428321007 390 441934658 391 455963797 392 470417550 393 485311335 394 500661233 395 516477428 396 532770224 397 549556817 398 566854926 399 584676018 400 603031927 401 621941611 402 641424586 403 661493989 404 682163162 405 703452981 406 725385188 407 747974572 408 771236106 409 795193085 410 819869454 411 845281818 412 871447298 413 898391544 414 926140950 415 954714436 416 984131205 417 1014419549 418 1045608844 419 1077720291 420 1110775452 421 1144805803 422 1179843724 423 1215912978 424 1253038016 425 1291253567 426 1330595321 427 1371090192 428 1412765590 429 1455659782 430 1499812448 431 1545253706 432 1592014215 433 1640136525 434 1689664384 435 1740631456 436 1793072400 437 1847034109 438 1902564837 439 1959702565 440 2018485980 441 2078966853 442 2141198728 443 2205224001 444 2271085932 445 2338841942 446 2408551084 447 2480260690 448 2554019390 449 2629890544 450 2707939266 451 2788218724 452 2870783186 453 2955702513 454 3043048904 455 3132881634 456 3225261176 457 3320265021 458 3417972756 459 3518450424 460 3621765832 461 3728004413 462 3837253956 463 3949588396 464 4065083237 465 4183832712 466 4305934031 467 4431469485 468 4560523118 469 4693199262 470 4829605094 471 4969832158 472 5113974372 473 5262146794 474 5414467586 475 5571038951 476 5731965344 477 5897373591 478 6067394425 479 6242141418 480 6421730612 481 6606302335 482 6796000682 483 6990951752 484 7191284977 485 7397155006 486 7608720632 487 7826122391 488 8049503900 489 8279035644 490 8514893138 491 8757232271 492 9006212445 493 9262022026 494 9524854418 495 9794882508 496 10072283597 497 10357265283 498 10650040596 499 10950801753 500 11259745320 501 11577099968 502 11903100952 503 12237961253 504 12581898628 505 12935165604 506 13298021242 507 13670701422 508 14053447977 509 14446538951 510 14850259660 511 15264871851 512 15690643202 513 16127879938 514 16576896803 515 17037983420 516 17511436032 517 17997592412 518 18496799028 519 19009376256 520 19535652418 521 20075999332 522 20630798346 523 21200404343 524 21785180379 525 22385535624 526 23001890446 527 23634637079 528 24284176730 529 24950960400 530 25635450572 531 26338080576 532 27059294428 533 27799588267 534 28559470844 535 29339421478 536 30139930486 537 30961543633 538 31804821209 539 32670292335 540 33558498332 541 34470040147 542 35405533896 543 36365563498 544 37350727062 545 38361685393 546 39399115824 547 40463663321 548 41555987692 549 42676815325 550 43826891590 551 45006927726 552 46217651244 553 47459861434 554 48734377421 555 50041983172 556 51383481621 557 52759750997 558 54171691306 559 55620167415 560 57106064004 561 58630345978 562 60194002936 563 61797987555 564 63443274409 565 65130924258 566 66862023982 567 68637622672 568 70458794440 569 72326704223 570 74242545460 571 76207474015 572 78222672332 573 80289419362 574 82409026372 575 84582765337 576 86811937408 577 89097947648 578 91442235219 579 93846199463 580 96311272872 581 98838997378 582 101430952336 583 104088677780 584 106813748994 585 109607857902 586 112472738384 587 115410083555 588 118421625291 589 121509220766 590 124674771848 591 127920139431 592 131247228042 593 134658074601 594 138154764818 595 141739344522 596 145413906246 597 149180683496 598 153041964343 599 156999995966 600 161057076664 601 165215656322 602 169478243136 603 173847304615 604 178325365751 605 182915111697 606 187619291342 607 192440614774 608 197381853594 609 202445950334 610 207635918364 611 212954731781 612 218405432204 613 223991244711 614 229715470464 615 235581372405 616 241592288768 617 247751752201 618 254063378300 619 260530747313 620 267157520548 621 273947566541 622 280904846005 623 288033284688 624 295336896915 625 302819919909 626 310486689736 627 318341509756 628 326388781932 629 334633144370 630 343079343160 631 351732095950 632 360596226532 633 369676810929 634 378979044510 635 388508095880 636 398269249778 637 408268061873 638 418510216330 639 429001374378 640 439747325786 641 450754148162 642 462028059130 643 473575259539 644 485402089026 645 497515194608 646 509921377856 647 522627426979 648 535640281786 649 548967212490 650 562615655797 651 576593041028 652 590906965021 653 605565375715 654 620576402656 655 635948176686 656 651689009491 657 667807588321 658 684312800128 659 701213539051 660 718518896828 661 736238368573 662 754381665083 663 772958513111 664 791978857026 665 811453070718 666 831391762940 667 851805570403 668 872705365268 669 894102479054 670 916008501216 671 938435058522 672 961394034374 673 984897806071 674 1008959029492 675 1033590410375 676 1058804936752 677 1084616122809 678 1111037786148 679 1138083810694 680 1165768385664 681 1194106263765 682 1223112530102 683 1252802349833 684 1283191221012 685 1314295247208 686 1346130891440 687 1378714714541 688 1412063642344 689 1446195246977 690 1481127491494 691 1516878459036 692 1553466628042 693 1590911168910 694 1629231680160 695 1668447899882 696 1708579996612 697 1749648883145 698 1791675935001 699 1834682691765 700 1878691164534 701 1923724159053 702 1969804984477 703 2016957143736 704 2065204650238 705 2114572369245 706 2165085716077 707 2216770327158 708 2269652394684 709 2323759026677 710 2379117926382 711 2435757051259 712 2493704966348 713 2552991215860 714 2613645990932 715 2675699776396 716 2739183715169 717 2804130000153 718 2870571530318 719 2938541535882 720 3008073962764 721 3079203886318 722 3151967145833 723 3226399956228 724 3302539314112 725 3380423424239 726 3460091321469 727 3541582468441 728 3624937174102 729 3710197044074 730 3797404588642 731 3886602796562 732 3977835576762 733 4071148232707 734 4166587047064 735 4264198840050 736 4364031435107 737 4466134149299 738 4570557362710 739 4677352061195 740 4786570317420 741 4898265806992 742 5012493363344 743 5129308493418 744 5248767884542 745 5370929948942 746 5495854351626 747 5623601509029 748 5754233123500 749 5887812745458 750 6024405285116 751 6164076493074 752 6306893512345 753 6452925470782 754 6602242975411 755 6754917563242 756 6911022283238 757 7070632319793 758 7233824458136 759 7400676515452 760 7571267954004 761 7745680526051 762 7923997719975 763 8106304171788 764 8292686298724 765 8483232977838 766 8678034973508 767 8877184315374 768 9080774965599 769 9288903533849 770 9501668671592 771 9719170428377 772 9941510954889 773 10168795241775 774 10401130493464 775 10638625461885 776 10881391173054 777 11129541705277 778 11383193540792 779 11642464863010 780 11907476321596 781 12178351850994 782 12455217986336 783 12738203136063 784 13027438387201 785 13323058352651 786 13625200463385 787 13934004215847 788 14249612005373 789 14572170017086 790 14901827494292 791 15238735945170 792 15583050019564 793 15934928446735 794 16294533263255 795 16662028992544 796 17037583567896 797 17421369302547 798 17813562092096 799 18214340565652 800 18623887041021 801 19042388545482 802 19470035990790 803 19907023279448 804 20353548310072 805 20809814049980 806 21276027666943 807 21752399604719 808 22239144640208 809 22736482995462 810 23244639439258 811 23763842331883 812 24294324720314 813 24836325506276 814 25390088518960 815 25955861509813 816 26533897304176 817 27124455029879 818 27727799140761 819 28344198378074 820 28973926981696 821 29617265962864 822 30274502095940 823 30945926844955 824 31631837618462 825 32332539107822 826 33048342245256 827 33779563076339 828 34526524079414 829 35289555571708 830 36068994614708 831 36865183848897 832 37678472881138 833 38509219742726 834 39357789758807 835 40224554345164 836 41109892446664 837 42014192068867 838 42937849111576 839 43881266105838 840 44844853725552 841 45829032397618 842 46834231076608 843 47860885940700 844 48909441981336 845 49980354672359 846 51074088706530 847 52191116649150 848 53331920586682 849 54496993881060 850 55686839865624 851 56901970433705 852 58142907771813 853 59410186201630 854 60704350813192 855 62025956008458 856 63375567322128 857 64753763334404 858 66161134260682 859 67598280449341 860 69065814272096 861 70564362132156 862 72094563011376 863 73657066896555 864 75252536765639 865 76881650697832 866 78545100350838 867 80243589338763 868 81977835319234 869 83748572183880 870 85556548489966 871 87402525788078 872 89287280789168 873 91211607665935 874 93176316436478 875 95182231215468 876 97230192491307 877 99321059542092 878 101455708745911 879 103635031778249 880 105859938004368 881 108131356990340 882 110450236762238 883 112817541950096 884 115234256274134 885 117701385180696 886 120219954051697 887 122791006265217 888 125415605807042 889 128094840039701 890 130829817831008 891 133621667557701 892 136471539849716 893 139380610467480 894 142350078378110 895 145381163700613 896 148475110558816 897 151633190103555 898 154856698534062 899 158146954954383 900 161505304370586 901 164933120863920 902 168431805526990 903 172002784259016 904 175647510914446 905 179367470603829 906 183164177572745 907 187039172935815 908 190994027952482 909 195030347492208 910 199149767857348 911 203353954421715 912 207644605071310 913 212023453844413 914 216492268662276 915 221052848903768 916 225707029020612 917 230456682324470 918 235303718659172 919 240250081910523 920 245297753768646 921 250448757706190 922 255705156589977 923 261069050090177 924 266542578634044 925 272127927581823 926 277827324743972 927 283643037722902 928 289577378065923 929 295632705615120 930 301811425961970 931 308115987722451 932 314548886862979 933 321112671267187 934 327809938130918 935 334643331130885 936 341615544969628 937 348729330172555 938 355987490381900 939 363392879456994 940 370948406250100 941 378657039603135 942 386521805581000 943 394545784502370 944 402732115917080 945 411084003854928 946 419604713996336 947 428297570594617 948 437165961705742 949 446213344700581 950 455443243333978 951 464859244596736 952 474465004211148 953 484264252378567 954 494260790786180 955 504458489390760 956 514861292150435 957 525473223060698 958 536298383102168 959 547340946912280 960 558605168807850 961 570095389127292 962 581816031073146 963 593771597316033 964 605966676324916 965 618405948981862 966 631094185367104 967 644036241296491 968 657237064926598 969 670701703705262 970 684435301099572 971 698443093020657 972 712730414767256 973 727302708326886 974 742165519002091 975 757324491770621 976 772785378583702 977 788554045988822 978 804636471701327 979 821038740903910 980 837767053868272 981 854827733963323 982 872227224179135 983 889972083315008 984 908068993991992 985 926524771069781 986 945346358070600 987 964540823310528 988 984115368324562 989 1004077336656617 990 1024434210241216 991 1045193605481070 992 1066363282049973 993 1087951152133295 994 1109965276768824 995 1132413861820708 996 1155305267237030 997 1178648016760756 998 1202450794181789 999 1226722439264389 1000 1251471957482372