0 1 1 0 2 0 3 0 4 1 5 0 6 1 7 0 8 2 9 1 10 2 11 0 12 4 13 0 14 4 15 2 16 7 17 0 18 9 19 1 20 12 21 4 22 14 23 1 24 23 25 4 26 24 27 9 28 35 29 3 30 46 31 7 32 56 33 18 34 68 35 14 36 99 37 16 38 107 39 36 40 145 41 24 42 186 43 39 44 219 45 72 46 270 47 56 48 361 49 84 50 408 51 134 52 514 53 117 54 655 55 173 56 761 57 244 58 926 59 238 60 1194 61 312 62 1347 63 458 64 1669 65 458 66 2073 67 588 68 2389 69 810 70 2898 71 841 72 3593 73 1061 74 4091 75 1451 76 4968 77 1504 78 6050 79 1896 80 6972 81 2475 82 8307 83 2654 84 10128 85 3299 86 11542 87 4217 88 13796 89 4559 90 16598 91 5614 92 18984 93 7049 94 22451 95 7762 96 26912 97 9349 98 30687 99 11689 100 36257 101 12831 102 42984 103 15467 104 49114 105 19081 106 57554 107 21058 108 68107 109 25154 110 77599 111 30693 112 90687 113 34041 114 106522 115 40515 116 121379 117 48829 118 141132 119 54462 120 165392 121 64233 122 187788 123 77015 124 217927 125 86016 126 253860 127 100935 128 288349 129 120099 130 333218 131 134351 132 386831 133 156979 134 438486 135 185882 136 505414 137 207730 138 584347 139 241963 140 662223 141 284490 142 760189 143 318683 144 876703 145 369609 146 991282 147 432417 148 1135908 149 484265 150 1305348 151 559741 152 1474445 153 651828 154 1684644 155 730720 156 1930715 157 840988 158 2177601 159 975832 160 2483131 161 1093044 162 2836787 163 1255146 164 3196614 165 1450502 166 3635291 167 1624249 168 4144330 169 1859621 170 4663069 171 2141529 172 5292256 173 2397218 174 6017631 175 2738654 176 6763401 177 3141754 178 7659609 179 3516370 180 8692010 181 4005524 182 9754605 183 4583384 184 11027841 185 5126576 186 12484843 187 5826272 188 13997189 189 6647480 190 15793848 191 7430688 192 17845369 193 8426505 194 19981542 195 9591138 196 22508324 197 10711301 198 25382357 199 12123912 200 28391146 201 13762865 202 31922903 203 15363248 204 35937778 205 17354249 206 40147161 207 19655440 208 45074803 209 21923057 210 50654042 211 24719227 212 56525063 213 27936926 214 63362390 215 31140025 216 71090216 217 35045142 218 79242151 219 39530539 220 88702920 221 44022832 222 99357215 223 49466936 224 110638731 225 55690782 226 123664552 227 61969667 228 138320354 229 69519905 230 153860817 231 78127168 232 171744391 233 86865004 234 191817729 235 97306876 236 213153742 237 109157179 238 237617350 239 121274314 240 265034790 241 135644685 242 294207189 243 151928876 244 327570425 245 168654029 246 364872530 247 188373487 248 404654494 249 210657797 250 449991075 251 233658041 252 500602187 253 260629594 254 554643758 255 291044021 256 616068561 257 322541583 258 684519968 259 359320879 260 757727461 261 400670826 262 840669242 263 443693274 264 932997336 265 493668372 266 1031815820 267 549738049 268 1143536287 269 608269302 270 1267682597 271 675974113 272 1400702270 273 751782445 274 1550714486 275 831181239 276 1717195871 277 922602701 278 1895729140 279 1024817964 280 2096642394 281 1132133150 282 2319245954 283 1255290019 284 2558220753 285 1392700511 286 2826507780 287 1537335796 288 3123462799 289 1702722962 290 3442423020 291 1886954082 292 3799791064 293 2081314581 294 4194842589 295 2302859011 296 4619455511 297 2549164304 298 5094265493 299 2809622747 300 5618574859 301 3105516260 302 6182317885 303 3434072292 304 6811647590 305 3782093532 306 7505705133 307 4176311458 308 8252441830 309 4613404787 310 9084495739 311 5077182729 312 10001162243 313 5601094777 314 10987764350 315 6181234247 316 12085307214 317 6797576542 318 13293187298 319 7492179528 320 14593737756 321 8260191666 322 16038059260 323 9077399759 324 17626152747 325 9996032288 326 19336422694 327 11010474906 328 21233082394 329 12091193789 330 23316401987 331 13303291728 332 25560541159 333 14640221610 334 28045608388 335 16066107536 336 30772779718 337 17661678209 338 33711009841 339 19419749979 340 36960299580 341 21296433913 342 40522668028 343 23392435962 344 44361579638 345 25699188972 346 48601021905 347 28163698625 348 53245258186 349 30910893468 350 58250367450 351 33931185762 352 63770686048 353 37160541467 354 69812983918 355 40753846519 356 76325382591 357 44700009509 358 83499423582 359 48922520944 360 91345607227 361 53612471772 362 99802191478 363 58758361023 364 109107511005 365 64267715839 366 119276252529 367 70376843558 368 130236802600 369 77073580896 370 142283549049 371 84247218709 372 155438105863 373 92189406365 374 169616753323 375 100887824156 376 185183901047 377 110209487660 378 202170053935 379 120514994961 380 220478218266 381 131791442702 382 240557832573 383 143881429544 384 262452701562 385 157228087503 386 286049769810 387 171819819235 388 311905082977 389 187469788964 390 340077632709 391 204723165760 392 370438194853 393 223570893912 394 403672278945 395 243791831498 396 439860596026 397 266054833437 398 478855900338 399 290356819399 400 521502966150 401 316435305302 402 567909309786 403 345113016967 404 617910783263 405 376392791815 406 672545104481 407 409966192123 408 731958465144 409 446842239621 410 795965947909 411 487034743314 412 865843807910 413 530182173915 414 941786613815 415 577520808245 416 1023590676692 417 629078725748 418 1112823295993 419 684436027136 420 1209742289987 421 745103752024 422 1314124159511 423 811134604872 424 1427895048711 425 882038037333 426 1551391330269 427 959662281358 428 1684377559831 429 1044091913497 430 1829211990918 431 1134758951024 432 1986336161747 433 1233921604779 434 2155505352644 435 1341708155127 436 2339608305323 437 1457461276874 438 2539220680970 439 1583941276743 440 2754097183282 441 1721332114447 442 2987769767995 443 1868883558701 444 3240990389517 445 2029958866211 446 3513521018125 447 2204820997694 448 3809685011907 449 2392615461641 450 4130450297513 451 2597440745490 452 4475608401658 453 2819664900012 454 4850441467359 455 3058320308719 456 5256197794424 457 3318393658421 458 5692721962078 459 3600397096258 460 6166462978567 461 3903237693043 462 6679019804102 463 4232988878719 464 7230331061076 465 4590340091218 466 7828257318535 467 4974073533521 468 8474853905305 469 5391574694990 470 9170188028322 471 5843769792551 472 9923842324324 473 6329315476806 474 10738442538411 475 6857184488081 476 11614252223500 477 7428605242451 478 12562942914642 479 8042120681218 480 13587860149884 481 8708617042602 482 14689537925906 483 9429727761377 484 15882192440356 485 10203879572277 486 17170064523507 487 11044281412298 488 18554082903782 489 11953080442465 490 20051528232771 491 12928616557775 492 21667777867834 493 13986905882862 494 23404288363942 495 15130751593694 496 25282063127019 497 16358435926602 498 27307903296791 499 17689377019955 500 29483974201238 501 19127204943526 502 31835775834634 503 20670220687757 504 34371905625590 505 22341925243670 506 37095457251928 507 24147013417488 508 40037398398823 509 26083881125129 510 43208539229969 511 28180965828758 512 46613215997664 513 30444314814292 514 50288994403279 515 32872532105769 516 54249459682431 517 35499996095396 518 58500571205505 519 38334482147625 520 63087867216438 521 41374946757706 522 68028371668657 523 44662960748836 524 73330173412314 525 48208442003406 526 79048420618384 527 52010931734302 528 85204449710534 529 56120651885005 530 91809053038744 531 60550232609154 532 98929003740240 533 65300094510242 534 106590970141191 535 70430865996044 536 114809239915467 537 75958567494139 538 123664610695221 539 81884906409644 540 133190354085255 541 88283011649186 542 143405201200069 543 95173199331170 544 154406893389331 545 102558916097463 546 166236841843148 547 110528353382442 548 178919491961845 549 119107176503674 550 192572940515640 551 128301240983234 552 207248689899480 553 138216852273725 554 222978403362385 555 148886335518081 556 239904725937347 557 160318771475992 558 258091612551170 559 172642265005439 560 277579835201794 561 185897404738596 562 298541560812298 563 200097633644003 564 321056133237142 565 215397160456981 566 345175751307289 567 231846882939719 568 371108190802289 569 249465958745888 570 398951633081082 571 268439966455613 572 428772675580959 573 288832606233907 574 460821881600946 575 310670472746317 576 495220629193900 577 334176752572895 578 532053546459921 579 359431054423908 580 571622612586179 581 386469562569087 582 614077637126865 583 415560671747347 584 659525823919598 585 446803546637201 586 708330867322004 587 480246770314299 588 760677557254413 589 516212904289830 590 816701075897359 591 554825303757929 592 876839298007221 593 596148442458436 594 941319797311760 595 640569755699091 596 1010312594667885 597 688242379668918 598 1084344604991482 599 739251092242738 600 1163695710524003 601 794060974541512 602 1248579072916514 603 852861978022621 604 1339628514152744 605 915764439141677 606 1437187749470278 607 983326484793782 608 1541523508102718 609 1055783275370753 610 1653397600307571 611 1133277483048550 612 1773231749046004 613 1216478630417325 614 1901358780048354 615 1305677321662266 616 2038693979978093 617 1401056846526487 618 2185754202742784 619 1503420088576603 620 2342953721796108 621 1613125551247710 622 2511391583583016 623 1730407658133808 624 2691700644239475 625 1856228524594245 626 2884395302399885 627 1991029913651130 628 3090794880746468 629 2135110080107920 630 3311673084598159 631 2289621571138071 632 3547667483938753 633 2455108032243954 634 3800360924721878 635 2631947175788683 636 4070698443325630 637 2821519000384412 638 4359468757436968 639 3024491752865280 640 4668569855069823 641 3241341789877471 642 4999154717121552 643 3473721071458058 644 5352197382461441 645 3722449529601281 646 5729972475885871 647 3988125975835786 648 6133885625308292 649 4272726977331516 650 6565137110240416 651 4577257468795352 652 7026451867725999 653 4902467830863571 654 7519541612231720 655 5250721881762908 656 8045883133706186 657 5623249672242952 658 8608739339655406 659 6020988877794906 660 9210192483075735 661 6446765108618115 662 9852056464486206 663 6902082637308452 664 10538236766846194 665 7388109333963533 666 11271263743554666 667 7908221687793178 668 12053362453791316 669 8464256997259989 670 12889204656874588 671 9057666331770123 672 13781862648170089 673 9692482970325517 674 14734061523407096 675 10370948155976532 676 15751387366534606 677 11094860362418348 678 16837567115972732 679 11869035724657141 680 17995933287843275 681 12696205017715974 682 19233161925062845 683 13578592960329591 684 20553770316393978 685 14521947375396522 686 21961827894507287 687 15529592294965651 688 23465310460335315 689 16604273595056589 690 25069687402234285 691 17752848611169508 692 26779921888365297 693 18979359481607037 694 28605537873252238 695 20287188181009893 696 30553152104510568 697 21684512290152354 698 32628810201939439 699 23176242496639334 700 34843879276074099 701 24766536121521766 702 37206356939052460 703 26465142250428890 704 39723598691694542 705 28278019620731078 706 42409164990664261 707 30210270035962358 708 45272715440968054 709 32273511197050752 710 48323187130336132 711 34474966967855112 712 51576750451040678 713 36820887897825425 714 55045062208842976 715 39325112509347431 716 58738969163224394 717 41996389744250151 718 62677745637581707 719 44842365666117360 720 66875446532039272 721 47879517324679577 722 71345221191475514 723 51118432162214066 724 76110034076044142 725 54568447207939970 726 81186817410176817 727 58249174153790840 728 86591496115926901 729 62173413126846462 730 92351417289421407 731 66352549878875534 732 98486964271564586 733 70809918555204561 734 105017402375919995 735 75560979687240904 736 111975284209932847 737 80619597301853738 738 119385128943622898 739 86013524511146124 740 127270218184776375 741 91761418293304477 742 135669283411757457 743 97880139415779882 744 144611797091468340 745 104402681733172917 746 154125865562588239 747 111351541160680930 748 164257554058312183 749 118747195544567892 750 175042259650166506 751 126628854873158609 752 186513881310306758 753 135023621795855220 754 198727182102530838 755 143956334687523593 756 211724644239846826 757 153473572476835951 758 225547114969876761 759 163607961791093105 760 240259668140829550 761 174389592937856442 762 255913251358820979 763 185873780089334859 764 272557039930111264 765 198099764538608801 766 290268325519501808 767 211103957756286396 768 309108167186687232 769 224952021397886863 770 329135708869100069 771 239691116116614863 772 350442716173398777 773 255365253701596998 774 373102313504349839 775 272052347462414853 776 397185572880224117 777 289809030622200240 778 422801398783868835 779 308688444825796799 780 450037302133056343 781 328783004904049776 782 478978614083289195 783 350160670682572105 784 509754525571879939 785 372885534967132089 786 542469691204732733 787 397067173152713195 788 577226479903449530 789 422787074282869612 790 614178077709782921 791 450122461311893646 792 653449558818065718 793 479203208976410852 794 695163628847912783 795 510126953682935317 796 739501850966478615 797 542986644709894857 798 786613604644019982 799 577936160106301321 800 836645850831072981 801 615092396564696436 802 889813694824674205 803 654567129128373818 804 946295429080127480 805 696542599845037638 806 1006266923670363188 807 741158666970255819 808 1069982921560835751 809 788549616035299054 810 1137656078742695125 811 838931201802303025 812 1209496700960596655 813 892470638449848186 814 1285806345088761257 815 949329103419681430 816 1366838493881805825 817 1009761929198589204 818 1452844442364635563 819 1073968899855567734 820 1544181012067910915 821 1142143295617871886 822 1641150157711938768 823 1214587179786287084 824 1744051931788001828 825 1291539077581939308 826 1853308371387501994 827 1373230567631117850 828 1969278955707352398 829 1460018859873767912 830 2092321682670350305 831 1552188544213107936 832 2222935521989506906 833 1650016853930150366 834 2361548169947775571 835 1753926048935522200 836 2508586457304531271 837 1864255452813360512 838 2664640071006184290 839 1981336681822244756 840 2830217554482662139 841 2105668701990520781 842 3005827445280584078 843 2237655842044591309 844 3192166359309858293 845 2377694434975409536 846 3389838603539714978 847 2526373869808492592 848 3599449655230117530 849 2684175620115459042 850 3821822098661930182 851 2851572994360924461 852 4057673616920848042 853 3029261934512276749 854 4307724612440459291 855 3217815405608007170 856 4572946026611346009 857 3417798201386170206 858 4854189694879966638 859 3630031776554408577 860 5152312177657617858 861 3855197542781168784 862 5468459063512454076 863 4093968964639755358 864 5803640836584272287 865 4347315265477314660 866 6158875276739051800 867 4616046334336542029 868 6535513504040651311 869 4900964616041362460 870 6934753493623947428 871 5203213262096639444 872 7357803814552234153 873 5523754282690151794 874 7806257348210591320 875 5863543097848627865 876 8281533553592800718 877 6223927492923485913 878 8785066647402766511 879 6606049490526608732 880 9318733768536251285 881 7011045833664915589 882 9884215865535715853 883 7440504999521629757 884 10483213874527688117 885 7895781877758779978 886 11117939032318352422 887 8378228009047704706 888 11790380870673906716 889 8889714845005381773 890 12502555376760444763 891 9431848885514178729 892 13257066323317976679 893 10006235964370951422 894 14056267184458885731 895 10615080082471635600 896 14902545912076904848 897 11260284970251919799 898 15798967294187005045 899 11943757323171183904 900 16748313805515607960 901 12668091817310425196 902 17753412297457624349 903 13435543143863718602 904 18817868787920018265 905 14248373698003756333 906 19944971192439689537 907 15109636961471139443 908 21138063988933564777 909 16022001775559083769 910 22401388302437567383 911 16988150859933592002 912 23738827268387531057 913 18011676316964770717 914 25154335470562022066 915 19095735429341615441 916 26652899061701754380 917 20243507297841783890 918 28239101775428551538 919 21459216109356782564 920 29917616899300484725 921 22746594920510247246 922 31694304203724642091 923 24109408730470092272 924 33574571646691071622 925 25552623163216762169 926 35563938713897161455 927 27080649665244474628 928 37669289229521694435 929 28697944356265398047 930 39897000279537286334 931 30410342307312178792 932 42253587161166763195 933 32223053856016840451 934 44747133585814231699 935 34141349877216143059 936 47385155663035621941 937 36172084605992116991 938 50175339963250872838 939 38321408696889560783 940 53127175551855965459 941 40595553020054019018 942 56249516576594067504 943 43002566090467357939 944 59551426552237332830 945 45549704709861210830 946 63044039948665996455 947 48244330281866644040 948 66737782055409958551 949 51095890238728609624 950 70643334214301162484 951 54112942042814444085 952 74773756658178422354 953 57304177753755086316 954 79141318602891569998 955 60680682791768367393 956 83758601383148880789 957 64252543223661729721 958 88640918283425869002 959 68030016469242937522 960 93802701554486733160 961 72026105203702777101 962 99258762769160019211 963 76252691193511776213 964 105027050187912407649 965 80721872246608804807 966 111124532297137273903 967 85448894398683181771 968 117568637363116601691 969 90447747792698566105 970 124380394024980636602 971 95732692964294334552 972 131579743284924768315 973 101321599949458941259 974 139187181959085283450 975 107230933169138612121 976 147227338546613372870 977 113477493346149995580 978 155723636336702412431 979 120082218628719059167 980 164700168817542210470 981 127064475807426060834 982 174185769845355874742 983 134444047720378945056 984 184207940363237021399 985 142245458480943300844 986 194794987614393229533 987 150491477873792116205 988 205980656466283817421 989 159205387816206215869 990 217797220403076199877 991 168415902302189434605 992 230277921139430415959 993 178149779274938973692 994 243462236407825996909 995 188434404223989346429 996 257388023264572124009 997 199303384857435156132 998 272094299243018166673 999 210788150924508875264 1000 287627231832860863575