1 0 2 0 3 0 4 0 5 1 6 0 7 0 8 0 9 0 10 1 11 0 12 0 13 0 14 0 15 2 16 1 17 2 18 1 19 2 20 3 21 3 22 2 23 4 24 2 25 6 26 4 27 5 28 4 29 7 30 7 31 8 32 8 33 10 34 11 35 18 36 13 37 19 38 19 39 22 40 29 41 32 42 29 43 37 44 37 45 53 46 48 47 60 48 54 49 68 50 79 51 84 52 86 53 104 54 99 55 133 56 125 57 149 58 151 59 183 60 191 61 219 62 223 63 259 64 268 65 335 66 320 67 377 68 391 69 448 70 487 71 547 72 552 73 640 74 666 75 781 76 795 77 908 78 923 79 1057 80 1139 81 1246 82 1312 83 1472 84 1508 85 1754 86 1805 87 2007 88 2103 89 2358 90 2483 91 2740 92 2882 93 3179 94 3347 95 3783 96 3876 97 4323 98 4536 99 4990 100 5333 101 5841 102 6075 103 6727 104 7077 105 7838 106 8204 107 9022 108 9410 109 10369 110 11022 111 11938 112 12590 113 13788 114 14421 115 15933 116 16677 117 18143 118 19126 119 20847 120 21993 121 23870 122 25170 123 27245 124 28755 125 31414 126 32798 127 35651 128 37553 129 40575 130 43030 131 46404 132 48714 133 52731 134 55593 135 60153 136 63276 137 68288 138 71723 139 77414 140 81914 141 87813 142 92662 143 99700 144 104795 145 113189 146 119042 147 127662 148 134655 149 144592 150 152450 151 163383 152 172235 153 184311 154 194386 155 208761 156 219157 157 234869 158 247463 159 264398 160 279334 161 298215 162 313681 163 335373 164 353343 165 377536 166 397406 167 424173 168 445994 169 476096 170 502202 171 534194 172 562819 173 599652 174 630526 175 672761 176 707624 177 752513 178 792440 179 843036 180 887378 181 943256 182 992718 183 1054159 184 1109704 185 1180176 186 1239510 187 1316844 188 1385239 189 1469247 190 1547445 191 1640676 192 1724112 193 1829031 194 1923513 195 2039371 196 2143697 197 2271729 198 2386339 199 2528643 200 2659964 201 2813471 202 2957968 203 3130652 204 3287893 205 3482067 206 3657211 207 3866322 208 4062848 209 4295742 210 4512434 211 4768818 212 5009016 213 5290038 214 5556746 215 5872236 216 6160742 217 6506861 218 6831461 219 7208349 220 7571762 221 7987659 222 8380313 223 8842245 224 9279682 225 9787086 226 10268664 227 10826524 228 11354066 229 11969698 230 12560961 231 13228226 232 13877275 233 14618311 234 15325630 235 16147555 236 16928633 237 17818810 238 18684213 239 19666914 240 20616223 241 21693741 242 22738898 243 23916210 244 25067810 245 26372411 246 27622796 247 29050321 248 30436738 249 31990724 250 33524452 251 35229581 252 36892736 253 38770630 254 40605301 255 42658030 256 44668435 257 46916404 258 49111925 259 51576997 260 54005618 261 56681184 262 59337314 263 62281343 264 65172852 265 68410257 266 71582447 267 75092692 268 78578716 269 82427603 270 86234537 271 90438408 272 94606598 273 99185803 274 103751151 275 108781581 276 113737833 277 119224241 278 124669910 279 130632245 280 136606977 281 143119311 282 149600280 283 156725220 284 163823835 285 171583396 286 179329334 287 187791349 288 196223075 289 205458359 290 214704696 291 224718455 292 234794100 293 245742043 294 256686837 295 268649354 296 280594157 297 293555042 298 306601646 299 320738320 300 334931795 301 350315359 302 365784284 303 382491617 304 399350233 305 417588465 306 435864291 307 455688778 308 475639167 309 497136442 310 518896340 311 542279215 312 565849705 313 591306775 314 616985898 315 644615871 316 672529928 317 702551522 318 732840357 319 765468859 320 798481440 321 833799887 322 869647216 323 908067049 324 946910803 325 988686280 326 1030895881 327 1076083741 328 1121967956 329 1171046231 330 1220797311 331 1274023307 332 1328028605 333 1385670312 334 1444289812 335 1506909395 336 1570322565 337 1638175769 338 1707063809 339 1780461442 340 1855250509 341 1934803706 342 2015655518 343 2101915595 344 2189624669 345 2282969113 346 2377983814 347 2479068190 348 2581866097 349 2691341778 350 2802860560 351 2921112838 352 3041821070 353 3169940059 354 3300403728 355 3439165599 356 3580419711 357 3730214204 358 3883173103 359 4045283045 360 4210630156 361 4385901437 362 4564777166 363 4754078511 364 4947564437 365 5152421608 366 5361256882 367 5582584592 368 5808559503 369 6047398992 370 6291816044 371 6549870523 372 6813521550 373 7092390990 374 7377388338 375 7678331568 376 7986126433 377 8311055453 378 8643164273 379 8993980668 380 9352920103 381 9731027476 382 10118414559 383 10526699374 384 10944358055 385 11385107696 386 11835894829 387 12310674870 388 12797222552 389 13309456004 390 13833984398 391 14386267714 392 14952015553 393 15547023844 394 16157149301 395 16798963265 396 17455989129 397 18147565757 398 18856204238 399 19600760704 400 20364822467 401 21167049674 402 21989411506 403 22853812494 404 23740074412 405 24670571554 406 25625115129 407 26627087852 408 27654478844 409 28733330939 410 29840262740 411 31000521714 412 32192046995 413 33441309397 414 34722946274 415 36067736226 416 37447220479 417 38892783283 418 40377521297 419 41932908564 420 43529605066 421 45202403375 422 46920026352 423 48718053035 424 50565500067 425 52499599577 426 54484709672 427 56563701975 428 58698793301 429 60932146869 430 63227968093 431 65628304150 432 68094029231 433 70673774414 434 73324098884 435 76094748544 436 78942272427 437 81918550283 438 84976386957 439 88173227327 440 91458985473 441 94889914539 442 98418376653 443 102103197381 444 105890216758 445 109846961496 446 113913157457 447 118157762217 448 122523374610 449 127079513376 450 131763806202 451 136652692603 452 141679821967 453 146923467221 454 152317799291 455 157944564348 456 163728879313 457 169763790085 458 175969956546 459 182439595558 460 189097021625 461 196034754914 462 203170407109 463 210609646144 464 218261640815 465 226234602991 466 234437706009 467 242983652142 468 251774130004 469 260933238621 470 270356772795 471 280167283155 472 290265005219 473 300777908463 474 311593621371 475 322857336248 476 334444898985 477 346504850555 478 358918223098 479 371835379136 480 385127552038 481 398959309286 482 413193865334 483 427999937024 484 443241743698 485 459095231816 486 475407315421 487 492376251945 488 509840045896 489 527996463829 490 546690086730 491 566120391141 492 586118860287 493 606910763014 494 628311447605 495 650551926819 496 673447598805 497 697238853155 498 721726513439 499 747173884563 500 773370120241 501 800577185200 502 828592207608 503 857688363475 504 887638971729 505 918750888722 506 950775159548 507 984026170493 508 1018264354812 509 1053809167201 510 1090402092424 511 1128391197871 512 1167502389006 513 1208092992992 514 1249890742449 515 1293267937704 516 1337920047451 517 1384262751261 518 1431974175714 519 1481471369931 520 1532444248789 521 1585315334563 522 1639749618202 523 1696219605553 524 1754360119401 525 1814656380724 526 1876743524276 527 1941126164162 528 2007411727573 529 2076150348863 530 2146927032046 531 2220292540322 532 2295846190640 533 2374161861128 534 2454794801637 535 2538383805875 536 2624443099920 537 2713628218282 538 2805470141592 539 2900637166928 540 2998624778455 541 3100158061801 542 3204702910573 543 3313004785686 544 3424533258899 545 3540064497260 546 3659009058211 547 3782226559395 548 3909094897581 549 4040480814155 550 4175783372125 551 4315884162802 552 4460135984253 553 4609516263711 554 4763322707419 555 4922560376075 556 5086528263772 557 5256271387664 558 5431037498993 559 5611960694143 560 5798247001157 561 5991038226140 562 6189566084550 563 6395019503858 564 6606550675533 565 6825472530615 566 7050863163682 567 7284072022734 568 7524207478281 569 7772649356137 570 8028440990987 571 8293073655558 572 8565536463048 573 8847364613003 574 9137555004631 575 9437705513918 576 9746707587806 577 10066317973833 578 10395368546413 579 10735638563774 580 11085998209589 581 11448263543885 582 11821221222591 583 12206869353124 584 12603896363680 585 13014359891553 586 13436952908347 587 13873814531890 588 14323545722218 589 14788458366103 590 15267078152832 591 15761743949796 592 16271028515371 593 16797366531652 594 17339190269106 595 17899169223402 596 18475605518679 597 19071247125448 598 19684451268349 599 20318035496361 600 20970241635578 601 21644103579256 602 22337766830962 603 23054358959224 604 23792043235639 605 24554074194617 606 25338431250007 607 26148669304161 608 26982662725739 609 27844026481075 610 28730705548030 611 29646401022157 612 30588911516148 613 31562281782418 614 32564140165855 615 33598657563916 616 34663476858056 617 35762934624587 618 36894513375120 619 38062881578362 620 39265391378371 621 40506786397906 622 41784506384637 623 43103488685903 624 44460931866385 625 45862215236655 626 47304314621444 627 48792776004670 628 50324678342198 629 51905721804185 630 53532787075501 631 55211991180875 632 56940050398897 633 58723278918931 634 60558435284695 635 62452090012824 636 64400689655211 637 66411369416078 638 68480398156803 639 70615057846347 640 72811750565743 641 75077952835189 642 77409819154647 643 79815470790847 644 82290776961294 645 84844123809825 646 87471422754013 647 90181394534899 648 92969681953243 649 95845639903643 650 98804694503409 651 101856388116012 652 104996315347258 653 108234408729683 654 111565860848794 655 115001432667251 656 118535949108426 657 122180520785646 658 125930170574207 659 129796343367092 660 133773735233914 661 137874588946657 662 142093333508618 663 146442622913250 664 150916988025388 665 155529598448625 666 160274473025282 667 165165838600689 668 170197428641059 669 175383810440394 670 180718976374593 671 186217919893864 672 191874232898987 673 197704114988045 674 203700699088894 675 209880734846187 676 216237471282492 677 222788331824430 678 229526135400992 679 236469511424235 680 243610940439957 681 250969491098367 682 258537976357214 683 266336248352111 684 274356477054473 685 282620062198595 686 291118592909275 687 299874195754137 688 308878851543882 689 318155397907455 690 327695305179773 691 337522932162223 692 347629343634665 693 358039748741013 694 368745457756610 695 379772713250132 696 391112020044859 697 402791596689152 698 414801522953679 699 427170776802686 700 439889956221299 701 452988953738213 702 466457757270551 703 480328509937197 704 494590503687885 705 509277015718246 706 524377638245555 707 539927000031437 708 555914050411647 709 572375704983320 710 589300429062216 711 606726126011929 712 624641936418143 713 643087331087273 714 662050475926473 715 681573729474561 716 701644397223564 717 722306334498381 718 743547642468198 719 765413667702893 720 787891774683752 721 811030202321923 722 834815763406478 723 859298441259141 724 884465633047088 725 910369388474432 726 936995912302847 727 964400942289245 728 992570126429200 729 1021560853102123 730 1051359831207581 731 1082026376578271 732 1113546355147236 733 1145983281041026 734 1179322053877790 735 1213628507971948 736 1248888290071215 737 1285169937258034 738 1322458233048794 739 1360826044699342 740 1400257572676268 741 1440827838231683 742 1482522441041306 743 1525419530071908 744 1569503347026833 745 1614857427386969 746 1661464865179144 747 1709412256137805 748 1758684341940406 749 1809370807899214 750 1861455473113835 751 1915033513433764 752 1970088151575170 753 2026718119117359 754 2084908006817473 755 2144760663542333 756 2206259080887275 757 2269512994781975 758 2334504854071398 759 2401347905410101 760 2470026809466483 761 2540658821749868 762 2613227635041619 763 2687858339695565 764 2764533501694082 765 2843382926863417 766 2924390970558894 767 3007692827764716 768 3093271936416718 769 3181271684401836 770 3271675084173350 771 3364630117163654 772 3460122735320492 773 3558307141255954 774 3659167670830271 775 3762868584194986 776 3869392988103555 777 3978911356731946 778 4091410251479749 779 4207066480954778 780 4325865800673879 781 4447995438343328 782 4573440923257217 783 4702396681010721 784 4834851383722149 785 4971007640513126 786 5110852366836907 787 5254601044145453 788 5402240590148314 789 5553993833092098 790 5709852340630275 791 5870047181162999 792 6034569332866575 793 6203664505818263 794 6377322906973748 795 6555799771912556 796 6739089471500524 797 6927457950485715 798 7120899249031993 799 7319694817436883 800 7523839237787148 801 7733623581252607 802 7949048642916561 803 8170417834520774 804 8397730720879383 805 8631309523020254 806 8871153293731887 807 9117596789739446 808 9370646345462363 809 9630649592543352 810 9897613171485337 811 10171904481615904 812 10453531507915409 813 10742876136480821 814 11039953429713073 815 11345161486223202 816 11658514458369118 817 11980434549914408 818 12310937922582710 819 12650461943507819 820 12999032586666749 821 13357103988810331 822 13724703396212213 823 14102312361368794 824 14489959273108393 825 14888144808403035 826 15296906789976199 827 15716767109413377 828 16147765666964591 829 16590453713025306 830 17044874782998859 831 17511599989388651 832 17990686000286870 833 18482728333732872 834 18987784770599300 835 19506486073900585 836 20038892475957839 837 20585659880064104 838 21146863867188186 839 21723186292063083 840 22314706805330653 841 22922144786450215 842 23545585824723711 843 24185778280624426 844 24842823390210555 845 25517501537258776 846 26209916727082126 847 26920894571457855 848 27650546716260126 849 28399729707878955 850 29168575848080227 851 29957975515054119 852 30768067934249477 853 31599794919553283 854 32453302723571761 855 33329571341192106 856 34228767916118424 857 35151914320200862 858 36099186716417636 859 37071662611900845 860 38069529988569691 861 39093906858061750 862 40145008852436859 863 41224002088167606 864 42331110663312582 865 43467566880575875 866 44633605815605520 867 45830509883806037 868 47058546384901847 869 48319049667165981 870 49612301242938775 871 50939706716732793 872 52301565218447283 873 53699340012517948 874 55133364187553050 875 56605164042502958 876 58115086147079737 877 59664741828647497 878 61254499281323215 879 62886032305356782 880 64559752357640258 881 66277400942575028 882 68039410973151301 883 69847620649874737 884 71702485129204290 885 73605918402461955 886 75558420956083888 887 77561989146414356 888 79617149911089240 889 81726005107936661 890 83889113203957404 891 86108657780284636 892 88385255118190555 893 90721183286101047 894 93117086148314894 895 95575366285041346 896 98096699879220878 897 100683588837227102 898 103336776525912061 899 106058868050556304 900 108850645611426152 901 111714849672853209 902 114652307487396897 903 117665873593760863 904 120756447733563430 905 123927008064958748 906 127178494671432708 907 130514045838963284 908 133934655718857722 909 137443587605049458 910 141041925560576631 911 144733067377610506 912 148518152900000190 913 152400761995472448 914 156382092750636025 915 160465874648359166 916 164653402345163866 917 168948566680986546 918 173352729357657942 919 177869981346450256 920 182501760666121492 921 187252321634561675 922 192123222121376066 923 197118901295937737 924 202240989888415413 925 207494161658833052 926 212880129141602504 927 218403761824380268 928 224066911140993120 929 229874650325522750 930 235828925721387603 931 241935067673741917 932 248195128912020729 933 254614664208163002 934 261195878600302120 935 267944568327881997 936 274863041062541703 937 281957394948547606 938 289230063572328891 939 296687393145990235 940 304332002451261935 941 312170503018745280 942 320205646235955710 943 328444386872094953 944 336889615149903955 945 345548579538161734 946 354424372624189881 947 363524557634869689 948 372852384194510897 949 382415795150105875 950 392218214211459995 951 402267907889602226 952 412568545983136690 953 423128755139161862 954 433952379291683600 955 445048487441692550 956 456421114620403425 957 468079713334815574 958 480028603037977628 959 492277635938677323 960 504831348857396347 961 517700082125277472 962 530888611165001542 963 544407715372647352 964 558262485606718856 965 572464170864606393 966 587018101960021871 967 601936097435984868 968 617223767907364196 969 632893420352684999 970 648951043153829194 971 665409463195536595 972 682274967039677673 973 699561028936520771 974 717274247944104942 975 735428671596360533 976 754031316683295610 977 773096841982083238 978 792632613947647134 979 812654010940790560 980 833168780600035598 981 854192937529340523 982 875734729586152857 983 897810869821330804 984 920429998093395847 985 943609661767040985 986 967358924812350325 987 991696081703285826 988 1016630773105075288 989 1042182072749062612 990 1068360097764187774 991 1095184847588229513 992 1122666955330279563 993 1150827274517211591 994 1179677082752251517 995 1209238142639933106 996 1239522263930447934 997 1270552283513475050 998 1302340612084974993 999 1334911041205340709 1000 1368276744463865007