1 0 2 0 3 0 4 0 5 1 6 1 7 1 8 1 9 4 10 4 11 4 12 4 13 10 14 11 15 11 16 11 17 22 18 25 19 26 20 26 21 44 22 51 23 54 24 55 25 84 26 98 27 105 28 108 29 153 30 178 31 193 32 200 33 269 34 313 35 341 36 356 37 459 38 531 39 582 40 611 41 764 42 880 43 967 44 1021 45 1244 46 1424 47 1568 48 1662 49 1988 50 2264 51 2494 52 2653 53 3122 54 3536 55 3896 56 4155 57 4828 58 5444 59 5995 60 6408 61 7365 62 8265 63 9096 64 9738 65 11094 66 12400 67 13632 68 14615 69 16522 70 18393 71 20198 72 21674 73 24347 74 27011 75 29622 76 31812 77 35533 78 39289 79 43030 80 46231 81 51393 82 56658 83 61964 84 66597 85 73717 86 81039 87 88505 88 95132 89 104916 90 115045 91 125463 92 134863 93 148238 94 162160 95 176598 96 189804 97 208021 98 227062 99 246935 100 265354 101 290048 102 315946 103 343135 104 368623 105 401974 106 437040 107 474020 108 509066 109 553917 110 601165 111 651198 112 699063 113 759162 114 822562 115 889906 116 954914 117 1035125 118 1119829 119 1210051 120 1297829 121 1404515 122 1517248 123 1637572 124 1755506 125 1896879 126 2046330 127 2206122 128 2363768 129 2550489 130 2747912 131 2959257 132 3169044 133 3414810 134 3674672 135 3953139 136 4231056 137 4553518 138 4894435 139 5259991 140 5626676 141 6048407 142 6494187 143 6972403 144 7454259 145 8004170 146 8585266 147 9208766 148 9839638 149 10554521 150 11309698 151 12120023 152 12942989 153 13869700 154 14848265 155 15898154 156 16968091 157 18165991 158 19430418 159 20786691 160 22173107 161 23717392 162 25346748 163 27093823 164 28884774 165 30870293 166 32964309 167 35208644 168 37515144 169 40061470 170 42745774 171 45621277 172 48583244 173 51840559 174 55272948 175 58947726 176 62740797 177 66897579 178 71275942 179 75960572 180 80805069 181 86097098 182 91668992 183 97626743 184 103798093 185 110520014 186 117594629 187 125153954 188 132996157 189 141515157 190 150477781 191 160047732 192 169989145 193 180762265 194 192092248 195 204181251 196 216754709 197 230349421 198 244641908 199 259880792 200 275747347 201 292867361 202 310860061 203 330030127 204 350008939 205 371524952 206 394130580 207 418197850 208 443301624 209 470289548 210 498635542 211 528792383 212 560271570 213 594058207 214 629534785 215 667250595 216 706645931 217 748865314 218 793184098 219 840266727 220 889474247 221 942135037 222 997399878 223 1056070132 224 1117418616 225 1182986754 226 1251779733 227 1324761554 228 1401107675 229 1482605250 230 1568090497 231 1658719976 232 1753561766 233 1854687639 234 1960736925 235 2073093892 236 2190709370 237 2315983467 238 2447327481 239 2586394265 240 2732006769 241 2886945274 242 3049356163 243 3221208722 244 3401187905 245 3592512723 246 3793023506 247 4005061377 248 4227162911 249 4463055005 250 4710223506 251 4971446162 252 5245101849 253 5535503794 254 5839729393 255 6161067848 256 6497731415 257 6854712065 258 7228615677 259 7623330065 260 8036894119 261 8475083661 262 8933962763 263 9418118487 264 9925411029 265 10462523605 266 11024896940 267 11617934233 268 12239315320 269 12896771777 270 13585030272 271 14310444758 272 15070516336 273 15874190189 274 16715374293 275 17601529571 276 18529985808 277 19511090802 278 20537817773 279 21618914231 280 22751551918 281 23947702460 282 25199271311 283 26516500458 284 27896426126 285 29352897188 286 30876604114 287 32479522357 288 34158584687 289 35929813308 290 37782516198 291 39730678352 292 41771175087 293 43922541749 294 46172519107 295 48537418615 296 51014119378 297 53624066163 298 56353223626 299 59220595535 300 62223146524 301 65385686134 302 68692173682 303 72164724830 304 75800494516 305 79628187411 306 83629500093 307 87830143703 308 92227598460 309 96855073986 310 101691723046 311 106767406868 312 112080099808 313 117668225736 314 123508080565 315 129634314071 316 136045606941 317 142786413531 318 149829833288 319 157216036239 320 164944671167 321 173067170894 322 181553063253 323 190448880546 324 199755562826 325 209532612688 326 219745582834 327 230448332423 328 241643486781 329 253399884372 330 265678661474 331 278542113111 332 291995030815 333 306117046516 334 320864410038 335 336309122964 336 352458723867 337 369405327179 338 387099788752 339 405625276742 340 424992778953 341 445308837067 342 466518379599 343 488717413735 344 511921219137 345 536253015532 346 561651236939 347 588226651002 348 615999839935 349 645113292672 350 675498363970 351 707282782737 352 740493639434 353 775295688181 354 811612595939 355 849591580237 356 889267677822 357 930831355879 358 974197982956 359 1019537160896 360 1066893579514 361 1116487401375 362 1168225082108 363 1222301932257 364 1278774320019 365 1337896685087 366 1399565980995 367 1464007035912 368 1531290291087 369 1601709749612 370 1675152303253 371 1751876670750 372 1831970195486 373 1915772523207 374 2003159994757 375 2094430230148 376 2189690807881 377 2289334024013 378 2393225262957 379 2501706797687 380 2614910366081 381 2733288969019 382 2856696768858 383 2985527283931 384 3119941019916 385 3260460958172 386 3406929941386 387 3559800299668 388 3719266715299 389 3885932806204 390 4059630242708 391 4240878839814 392 4429913791951 393 4627431613594 394 4833253243409 395 5047975936430 396 5271882814166 397 5505777363928 398 5749470634001 399 6003648731698 400 6268651369868 401 6545405189868 402 6833712668586 403 7134361863542 404 7447759196049 405 7774973028249 406 8115799209247 407 8471142764610 408 8841488619617 409 9228068181805 410 9630673360471 411 10050343383738 412 10487655424460 413 10944028389587 414 11419253881316 415 11914525091822 416 12430527435308 417 12968895380512 418 13529424977043 419 14113486059107 420 14721890880792 421 15356521632584 422 16017184963293 423 16705453352314 424 17422287498658 425 18169854191135 426 18947978481953 427 19758465332577 428 20602448968322 429 21482423009922 430 22398240744205 431 23351973827425 432 24344959099090 433 25380065401301 434 26457186478744 435 27578699932989 436 28746178931886 437 29962922923601 438 31228881232544 439 32546782408591 440 33918474991328 441 35347752443544 442 36834638201307 443 38382263385134 444 39992797092151 445 41670599328301 446 43415790270180 447 45231962788882 448 47121658795039 449 49089887814248 450 51136894196962 451 53266800433449 452 55482581645218 453 57789991727600 454 60189432366874 455 62685633465952 456 65282073114057 457 67985358012219 458 70796087047721 459 73719686726648 460 76760218628836 461 79925266137903 462 83215673148204 463 86637664978352 464 90195979590583 465 93899318572781 466 97748827900712 467 101751648855963 468 105913302883675 469 110243771349763 470 114744570311696 471 119423891226371 472 124288162433250 473 129348829542564 474 134607859413408 475 140074647455410 476 145756671035245 477 151667050481616 478 157808299102627 479 164191192380545 480 170824420310995 481 177723018079181 482 184890158433493 483 192338198643980 484 200077229555968 485 208124475044766 486 216483900562973 487 225169676104860 488 234193509798234 489 243575126436579 490 253319440945757 491 263442700434220 492 273958479062101 493 284889358370277 494 296241386913191 495 308033191478948 496 320280498013915 497 333009150279157 498 346226546300209 499 359954038780430 500 374209833561898 501 389023498452301 502 404404033599721 503 420375913678926 504 436960200990454 505 454190713329596 506 472078348134787 507 490651155049324 508 509933484809458 509 529964003898354 510 550755851465407 511 572341170051764 512 594748094153260 513 618020820355365 514 642175130729278 515 667247852804704 516 693271472541895 517 720296491876123 518 748341802648249 519 777449593989404 520 807657353706904 521 839022770935261 522 871568389684972 523 905342533763416 524 940388437606346 525 976771980276491 526 1014519987485834 527 1053687800681749 528 1094325253446093 529 1136507554738031 530 1180266541647769 531 1225665581535403 532 1272762082560860 533 1321641879110653 534 1372342664589434 535 1424936983216721 536 1479490933342050 537 1536102446808616 538 1594816050548935 539 1655714779168823 540 1718874696615209 541 1784407504198518 542 1852365691565859 543 1922844282232106 544 1995930763255032 545 2071752504185950 546 2150371260733360 547 2231895754494110 548 2316426560589877 549 2404108872402722 550 2495015214806683 551 2589269956214998 552 2686988660980243 553 2788336792944712 554 2893399377876082 555 3002318652309614 556 3115227339872149 557 3232313950970662 558 3353678005805347 559 3479482140133240 560 3609878712854201 561 3745082430203172 562 3885209599615904 563 4030446139405057 564 4180966867736618 565 4337016258190316 566 4498730040459991 567 4666320698825544 568 4839988730409426 569 5020012425633724 570 5206549962165994 571 5399844128222422 572 5600124769323634 573 5807708582845309 574 6022779666311054 575 6245615365831436 576 6476479055788780 577 6715731042253761 578 6963585323275575 579 7220358642637205 580 7486352664464262 581 7761977196735631 582 8047480698974920 583 8343224816987849 584 8649554924556530 585 8966937006658020 586 9295659206230361 587 9636134329444050 588 9988757627636996 589 10354058821414146 590 10732371712048426 591 11124167379210772 592 11529897968396156 593 11950165493009993 594 12385356244374185 595 12836007657927089 596 13302636752523293 597 13785927519386508 598 14286326546527770 599 14804446805431723 600 15340879258956487 601 15896400835152339 602 16471527333588471 603 17066957686081417 604 17683367107208182 605 18321637859161651 606 18982365127596496 607 19666345637493601 608 20374350564566769 609 21107381526305269 610 21866124699474978 611 22651488029815553 612 23464351951232119 613 24305853290092206 614 25176782443616189 615 26078173810427816 616 27011032177386748 617 27976647501087497 618 28975929471418349 619 30010056213737793 620 31080173997451971 621 32187746163008042 622 33333818855696929 623 34519733510309790 624 35746797310904865 625 37016669865906185 626 38330553308424850 627 39689974575961021 628 41096423803833060 629 42551782718190095 630 44057431657985060 631 45615108206977085 632 47226510433559901 633 48893771374508981 634 50618474834225899 635 52402597519951637 636 54248073744265709 637 56157320814781470 638 58132154704982133 639 60174823487901989 640 62287529793787467 641 64473012406127798 642 66733352068364785 643 69071104713276236 644 71488777612569656 645 73989473011768543 646 76575573434265355 647 79249983965443812 648 82015557642353943 649 84875807543225638 650 87833459966709118 651 90891815859249569 652 94054120566296159 653 97324351431435883 654 100705626159301147 655 104201694374813812 656 107816246391171106 657 111553784073653078 658 115417870530477285 659 119412763772163234 660 123542658639787300 661 127812649455289849 662 132226805919524211 663 136789961902804456 664 141506884117851961 665 146383335917571103 666 151423962903178601 667 156634251033323579 668 162019615012720506 669 167586573516735259 670 173340426517758172 671 179287398154615160 672 185433637137647127 673 191786514683898613 674 198352073944681407 675 205137374441079715 676 212149396051255534 677 219396472038521518 678 226885489198873832 679 234624452147981550 680 242621281653487858 681 250885396338781393 682 259424640252392789 683 268248086900335672 684 277364721805871826 685 286785187783916355 686 296518414554436566 687 306574684158358386 688 316964186665689484 689 327698945348505584 690 338789120701986151 691 350246360777870780 692 362082217908165398 693 374310271669679110 694 386942077227228066 695 399990826174275571 696 413469610988532816 697 427393765389210680 698 441776424258874391 699 456632522814189800 700 471976894249290908 701 487826848951162231 702 504197310375539010 703 521105182792136053 704 538567266195109746 705 556603097875325629 706 575229625500705685 707 594465976310254923 708 614331171863961075 709 634847257688445663 710 656033471426516381 711 677911449205365267 712 700502721152936785 713 723832157250745925 714 747921584747032680 715 772795470520329269 716 798478176488930393 717 824997752439291640 718 852378952922641196 719 880649437790843616 720 909836764660265118 721 939972562354156948 722 971084893196067629 723 1003205017537674052 724 1036364098288931560 725 1070597791738806232 726 1105937896497377151 727 1142419731783588212 728 1180078526687858455 729 1218954468538439903 730 1259083574696048527 731 1300505738654431287 732 1343260774137279222 733 1387393964881686270 734 1432946090027410039 735 1479962196726831963 736 1528487266380484205 737 1578572313738919620 738 1630263490716785763 739 1683611649247421608 740 1738667593904523917 741 1795488782607419509 742 1854127427296648252 743 1914640916228368422 744 1977086613895796617 745 2041529220389200813 746 2108027780452515494 747 2176647040335615652 748 2247451752288324516 749 2320514754808018234 750 2395902794119123482 751 2473688897118923493 752 2553946133747374256 753 2636756485985494827 754 2722195377713384173 755 2810345152245565692 756 2901288241546782097 757 2995116897961623377 758 3091916319668782989 759 3191779328842681244 760 3294798891963082085 761 3401078794899444091 762 3510715241734169404 763 3623812837764335209 764 3740476400000779126 765 3860822663443745293 766 3984960220845959652 767 4113006923626328219 768 4245080916041008821 769 4381313468315640647 770 4521827113896396204 771 4666754590951036499 772 4816229027573801311 773 4970398005934966865 774 5129399741666319836 775 5293383699027406729 776 5462499847840446734 777 5636914072033002359 778 5816782222950732371 779 6002272552542577012 780 6193553955457031004 781 6390812845348064297 782 6594224900034559527 783 6803979469270609329 784 7020266707526395572 785 7243296052262266922 786 7473265463877056745 787 7710387977865532944 788 7954877625192553320 789 8206969658484359982 790 8466887073548570028 791 8734869490054503678 792 9011157747035718906 793 9296016035672617191 794 9589695471728651041 795 9892465504421241227 796 10204597064382506801 797 10526386775492650544 798 10858117328768613683 799 11200091635912099623 800 11552614395958764025 801 11916018573550260285 802 12290622304522765124 803 12676766028840482844 804 13074792330085187969 805 13485074883718755166 806 13907971602743618384 807 14343865004459238246 808 14793140163813453058 809 15256216352702242464 810 15733496110485218612 811 16225409120374389324 812 16732388103387960996 813 17254903388666593315 814 17793407568202267000 815 18348383181805797538 816 18920316362885847420 817 19509734600242237605 818 20117146608959755625 819 20743094147960160620 820 21388123211961151093 821 22052825267360037435 822 22737771941713586788 823 23443571325006758567 824 24170836483825791274 825 24920230477898094697 826 25692395438757902982 827 26488013735239422144 828 27307773565993888580 829 28152418089146160231 830 29022668426469573637 831 29919290105405834123 832 30843055464448414302 833 31794797256360931574 834 32775325077260983730 835 33785497531894768835 836 34826181162946386901 837 35898308918501374030 838 37002789465679521662 839 38140585563148557383 840 39312669199960409512 841 40520085350606949831 842 41763853590024860478 843 43045053197665232674 844 44364774163828766920 845 45724186690937919111 846 47124434480644303211 847 48566727137415163343 848 50052286670375063185 849 51582423237507080460 850 53158419425972318218 851 54781630570414439772 852 56453426345813260907 853 58175273292444916972 854 59948609357121215473 855 61774952792525468548 856 63655838401352215600 857 65592907424229999538 858 67587771552115218779 859 69642131128287807236 860 71757705565856935537 861 73936331228730102083 862 76179814063561593580 863 78490057885877713531 864 80868988451647232946 865 83318660013030369191 866 85841095651752365345 867 88438426495579327745 868 91112808879815586780 869 93866540315272600077 870 96701886533378596279 871 99621232549266553375 872 102626992300507738177 873 105721734824806645767 874 108907996950186702845 875 112188447196727204931 876 115565787227262831312 877 119042889097067358562 878 122622592439686690914 879 126307882281314468799 880 130101781581279687416 881 134007500485777192819 882 138028216770914992553 883 142167268732367507435 884 146428038031879575852 885 150814111962315452970 886 155329045813803923045 887 159976572097170847995 888 164760472846057357572 889 169684755981593106618 890 174753398164657572873 891 179970571715271240174 892 185340505447848335923 893 190867676311089870450 894 196556531178821816489 895 202411732939622510963 896 208438008864799187138 897 214640358793103453384 898 221023754193782218774 899 227593405021935209776 900 234354594534547539399 901 241312905390856210532 902 248473894193569446564 903 255843380836488886910 904 263427268592878833247 905 271231789611286817188 906 279263153003692416099 907 287527858553604800285 908 296032500802659961440 909 304784035538996266201 910 313789399353710395725 911 323055849730775626858 912 332590751751489360217 913 342401867298736235819 914 352496943844800729201 915 362884083109985186875 916 373571508889760059490 917 384567880834071206776 918 395881850059510384541 919 407522458742406133659 920 419498887449632447976 921 431820795498233659284 922 444497840802321756014 923 457540112959757605005 924 470957858333837533458 925 484761849155676026490 926 498962864820091044329 927 513572161233907162582 928 528601171751445182405 929 544061907351122727989 930 559966396384015732159 931 576327193177564865298 932 593157052772123570486 933 610469364684977269978 934 628277547889209808928 935 646595601910482382113 936 665437753144023329942 937 684818924914651759968 938 704754084220897989812 939 725258838826016928558 940 746349052753796071180 941 768041355563192545369 942 790352437132184255704 943 813299694528795050972 944 836900814089004922658 945 861174323050329896942 946 886138828370320251156 947 911813717470811894506 948 938218704090978383575 949 965374425666742036746 950 993301621878842015847 951 1022021893695549092488 952 1051557209967415303388 953 1081930554200015792821 954 1113165038204599960260 955 1145284724223086550417 956 1178314088987124984294 957 1212278723811637953349 958 1247204378375703992193 959 1283117851100835384784 960 1320046407134319410648 961 1358018535991756223507 962 1397062920125304156172 963 1437209399144316807909 964 1478488337900196016330 965 1520931446229094637356 966 1564570666567222445617 967 1609439218054263476781 968 1655570910592719414808 969 1703001031588770861931 970 1751765146448054725216 971 1801900229089540265757 972 1853443917524991432283 973 1906435472868370951133 974 1960914486088338260235 975 2016922101986197331117 976 2074500211489034250509 977 2133692488597837056427 978 2194542996282711820601 979 2257097511546188619705 980 2321402649244996913482 981 2387506983076227861839 982 2455459542975615060265 983 2525311249500102979932 984 2597113963586253474466 985 2670921698134399090014 986 2746788998706752598476 987 2824772496124246422651 988 2904929876132177681096 989 2987321188636643271761 990 3072007102895085418907 991 3159050587935722080513 992 3248515795631122808442 993 3340469475171688802923 994 3434979093293622868470 995 3532114652898885079020 996 3631947482532629374014 997 3734551764247679189218 998 3840002508720805940198 999 3948377523281372402162 1000 4059756100246552575178