0 1 1 0 2 1 3 1 4 1 5 1 6 3 7 1 8 3 9 4 10 4 11 4 12 8 13 5 14 9 15 11 16 11 17 12 18 20 19 15 20 23 21 27 22 28 23 31 24 45 25 38 26 52 27 61 28 64 29 71 30 96 31 87 32 112 33 129 34 136 35 151 36 194 37 184 38 227 39 259 40 275 41 304 42 376 43 368 44 441 45 499 46 531 47 586 48 704 49 705 50 826 51 927 52 989 53 1088 54 1280 55 1302 56 1500 57 1672 58 1787 59 1960 60 2267 61 2332 62 2652 63 2940 64 3144 65 3439 66 3924 67 4071 68 4581 69 5053 70 5406 71 5896 72 6656 73 6948 74 7752 75 8513 76 9108 77 9908 78 11085 79 11624 80 12878 81 14088 82 15069 83 16353 84 18160 85 19107 86 21043 87 22940 88 24528 89 26557 90 29309 91 30911 92 33873 93 36812 94 39340 95 42503 96 46657 97 49293 98 53784 99 58288 100 62252 101 67123 102 73346 103 77584 104 84336 105 91166 106 97299 107 104717 108 113972 109 120653 110 130725 111 140984 112 150360 113 161540 114 175205 115 185566 116 200475 117 215752 118 229925 119 246617 120 266658 121 282496 122 304408 123 326967 124 348175 125 372877 126 402080 127 425984 128 457968 129 491024 130 522464 131 558720 132 601008 133 636680 134 683059 135 731148 136 777349 137 830160 138 891031 139 943724 140 1010557 141 1080032 142 1147380 143 1223753 144 1310875 145 1387988 146 1483720 147 1583445 148 1680881 149 1790585 150 1914590 151 2026484 152 2162828 153 2305099 154 2445069 155 2601650 156 2777220 157 2938317 158 3131437 159 3333221 160 3532963 161 3755107 162 4002424 163 4232679 164 4504783 165 4789392 166 5072652 167 5386019 168 5732693 169 6059579 170 6441040 171 6840355 172 7239687 173 7679347 174 8163004 175 8624155 176 9156335 177 9713763 178 10273592 179 10887268 180 11558974 181 12205691 182 12944696 183 13719099 184 14499781 185 15352145 186 16280924 187 17182841 188 18204464 189 19275348 190 20358533 191 21536876 192 22815693 193 24066916 194 25473168 195 26947499 196 28443208 197 30064899 198 31818504 199 33545692 200 35473372 201 37494547 202 39550460 203 41772729 204 44167928 205 46540906 206 49172812 207 51932393 208 54745996 209 57778732 210 61037831 211 64283448 212 67863031 213 71616032 214 75450495 215 79572922 216 83991220 217 88411424 218 93261845 219 98346661 220 103551487 221 109133855 222 115102367 223 121097702 224 127646579 225 134510824 226 141548640 227 149080356 228 157115272 229 165215333 230 174026784 231 183260717 232 192741981 233 202867968 234 213648715 235 224551517 236 236367535 237 248747249 238 261475028 239 275042648 240 289460938 241 304083700 242 319877456 243 336420460 244 353448096 245 371567527 246 390790460 247 410334924 248 431379260 249 453415875 250 476121089 251 500242815 252 525793833 253 551830064 254 579785319 255 609050212 256 639230048 257 671244132 258 705106603 259 739680313 260 776706651 261 815455857 262 855448096 263 897811016 264 942560588 265 988330200 266 1037230993 267 1088391214 268 1141229288 269 1197125668 270 1256098915 271 1316510252 272 1380914704 273 1448273426 274 1517883627 275 1591432029 276 1668940901 277 1748449408 278 1833044634 279 1921491661 280 2012943680 281 2109457900 282 2211061964 283 2315414709 284 2426240136 285 2542073823 286 2661898417 287 2788218608 288 2921069827 289 3057662713 290 3202482749 291 3353797584 292 3510388528 293 3675299972 294 3848578572 295 4026907948 296 4215682815 297 4412858941 298 4616980632 299 4831742384 300 5057206883 301 5289439345 302 5534918877 303 5791239188 304 6056666556 305 6335677504 306 6628357437 307 6930047467 308 7248518552 309 7580945328 310 7925268966 311 8286905559 312 8665972388 313 9056964561 314 9469190337 315 9899340800 316 10344978195 317 10812646216 318 11302506401 319 11808067592 320 12340465560 321 12895835184 322 13471298692 323 14074751432 324 14706415924 325 15358653718 326 16044771007 327 16760265056 328 17501748957 329 18278736608 330 19091533782 331 19931170507 332 20813528200 333 21733375809 334 22686739556 335 23685069573 336 24728784376 337 25807372223 338 26939767332 339 28119909893 340 29343152484 341 30623259200 342 31960800192 343 33343482660 344 34793856793 345 36304923581 346 37871265688 347 39509410116 348 41220129472 349 42989078616 350 44843087267 351 46774096833 352 48775814142 353 50868062308 354 53051882555 355 55310570758 356 57676017674 357 60138975145 358 62692158799 359 65359320688 360 68141856372 361 71020357373 362 74032695520 363 77168294320 364 80418753931 365 83812506025 366 87351410952 367 91012968627 368 94842114337 369 98826797352 370 102957370257 371 107267834404 372 111760656703 373 116409812959 374 121268574929 375 126323266877 376 131562855937 377 137027967801 378 142721857192 379 148614495096 380 154768986371 381 161169878157 382 167804611339 383 174721685096 384 181925372792 385 189381109293 386 197163591252 387 205255440307 388 213642431491 389 222382416455 390 231480980109 391 240898437368 392 250723142819 393 260935654576 394 271519949583 395 282544982109 396 294018019164 397 305893618541 398 318276219316 399 331144197656 400 344479615444 401 358364599940 402 372808567484 403 387759628973 404 403341156912 405 419529258826 406 436303990600 407 453763100896 408 471918742735 409 490711840240 410 510288043469 411 530621151992 412 551689165288 413 573608347624 414 596394325201 415 619980050462 416 644537375577 417 670037820676 418 696457337301 419 723934125669 420 752488206025 421 782043737965 422 812803380435 423 844736496564 424 877817081292 425 912209311752 426 947938750763 427 984919920548 428 1023391688560 429 1063321510408 430 1104681629456 431 1147666972398 432 1192310073868 433 1238514969340 434 1286563070768 435 1336420344562 436 1388057640024 437 1441706269011 438 1497407512176 439 1555054090223 440 1614977390126 441 1677142528931 442 1741519521016 443 1808382716375 444 1877784339476 445 1949605024351 446 2024234846296 447 2101638999889 448 2181787487251 449 2265005548563 450 2351359069027 451 2440715926552 452 2533535101445 453 2629783161337 454 2729431259337 455 2832864791232 456 2940166654679 457 3051191465481 458 3166479086983 459 3285999225422 460 3409725784561 461 3538115246863 462 3671271649495 463 3809036081683 464 3952043332204 465 4100268606112 466 4253690713168 467 4412850115939 468 4577877063500 469 4748599195819 470 4925762688688 471 5109351354544 472 5299351766923 473 5496403573880 474 5700669459544 475 5911964161147 476 6131164537781 477 6358267054900 478 6593269790696 479 6836929507683 480 7089448946946 481 7350631118691 482 7621506183868 483 7902088473973 484 8192392418253 485 8493313030040 486 8805102427253 487 9127553898583 488 9461877418772 489 9808111847380 490 10166294188048 491 10537482618557 492 10921990011527 493 11319603019568 494 11731742505648 495 12158480311167 496 12599883946096 497 13057204114037 498 13530828311193 499 14020541029168 500 14528010440651 501 15053352030460 502 15596673859984 503 16159453755640 504 16742170717832 505 17344613324207 506 17968739745144 507 18614722483016 508 19282722799604 509 19974486404318 510 20690604318246 511 21430877695040 512 22197604734152 513 22991031652892 514 23811388762000 515 24660737667542 516 25539806312200 517 26448419735087 518 27389274801963 519 28362712203068 520 29369051067716 521 30410725447013 522 31488630387185 523 32602629646360 524 33755887479100 525 34948864756329 526 36181993987547 527 37458148258799 528 38778426254524 529 40142749669104 530 41554830686098 531 43015282085200 532 44524680160618 533 46086415434904 534 47701834399469 535 49370941329455 536 51098090725800 537 52884086311639 538 54729685679151 539 56638889080017 540 58613344144967 541 60653169067440 542 62763471280791 543 64945293336584 544 67199620268332 545 69531170683398 546 71941957671432 547 74432252906780 548 77008046381744 549 79670678062272 550 82421417023064 551 85265828056165 552 88206367190368 553 91243509216924 554 94384278587720 555 97630384183968 556 100983448368179 557 104450032515472 558 108033128821659 559 111733477132000 560 115559314352629 561 119512805342641 562 123596010266958 563 127816664003781 564 132178406968035 565 136682320976878 566 141338063950901 567 146148362511639 568 151115817542812 569 156249545504912 570 161553969564116 571 167030608624433 572 172690785982056 573 178537918294551 574 184575272225949 575 190813590496148 576 197258240375492 577 203911295022477 578 210786029397727 579 217886705445179 580 225217407278698 581 232790791531672 582 240613362900704 583 248687892634013 584 257029942741887 585 265644808020734 586 274537573628722 587 283723148222040 588 293209405317100 589 302999990268826 590 313113145006317 591 323555423404852 592 334333133514080 593 345463833340492 594 356957041912872 595 368817493472003 596 381066570029188 597 393712356958527 598 406762652820632 599 420238131786497 600 434150288940176 601 448505208793112 602 463327952367789 603 478628464085357 604 494416355338776 605 510715964790638 606 527541158085408 607 544899687330112 608 562820923665142 609 581317063821896 610 600399919641600 611 620098138198536 612 640428426112631 613 661400587448413 614 683049042425559 615 705388711596723 616 728434072712976 617 752218837255259 618 776763113248096 619 802079221290643 620 828207495815368 621 855166145778688 622 882972873008408 623 911667340746443 624 941273725505556 625 971807424840285 626 1003315700102116 627 1035820723821648 628 1069344090352125 629 1103932455966216 630 1139614859020062 631 1176410448805105 632 1214374598864769 633 1253534251743872 634 1293915693821169 635 1335573795960783 636 1378543401097556 637 1422848221319828 638 1468553129383363 639 1515690799956344 640 1564293166516897 641 1614424747201586 642 1666127308844239 643 1719430099581232 644 1774409114212201 645 1831103906066156 646 1889553195298560 647 1949832827141276 648 2011992820236000 649 2076069124819451 650 2142150756126033 651 2210285510985537 652 2280520254411510 653 2352944127771536 654 2427616975635772 655 2504582845319136 656 2583945992808324 657 2665764081443732 658 2750093738040536 659 2837039707488432 660 2926673524819026 661 3019049000919441 662 3114288228848160 663 3212460666518850 664 3313634625518204 665 3417933157330286 666 3525441694287916 667 3636225799033608 668 3750428437060688 669 3868133149067883 670 3989422215985181 671 4114440161552672 672 4243288925437108 673 4376048190963411 674 4512885343937794 675 4653900720904541 676 4799193283614817 677 4948932734346456 678 5103240604717844 679 5262213517855573 680 5426047425872910 681 5594862674991135 682 5768778122846828 683 5947992988129408 684 6132652037270872 685 6322872184118140 686 6518882790900576 687 6720828017151235 688 6928850425010915 689 7143183825071960 690 7364000517656454 691 7591441685870895 692 7825775759762444 693 8067175209948329 694 8315810810736387 695 8571956901248872 696 8835818385652228 697 9107565434892736 698 9387512153534824 699 9675864637374215 700 9972827203195233 701 10278721660254193 702 10593791491513684 703 10918241446180137 704 11252439016228567 705 11596630196045664 706 11951059142572628 707 12316103249230501 708 12692051614508756 709 13079150182543460 710 13477828834639746 711 13888380863752575 712 14311097701378403 713 14746421806412384 714 15194696174551312 715 15656215768541289 716 16131483362544368 717 16620848270110439 718 17124657966437969 719 17643431051136648 720 18177574157616942 721 18727440509397088 722 19293618025709427 723 19876522313126360 724 20476567225864524 725 21094360436962893 726 21730383666464224 727 22385059306532535 728 23059074709441567 729 23752923864199024 730 24467099175800410 731 25202312487220380 732 25959134053564537 733 26738068298065000 734 27539918663189592 735 28365271737807901 736 29214712801360613 737 30089075482949832 738 30989034360015237 739 31915191041061992 740 32868484472201740 741 33849610550281505 742 34859264272732704 743 35898421603999165 744 36967879965299262 745 38068355989887292 746 39200946746555337 747 40366477061586088 748 41565771442802948 749 42799972152091852 750 44070021170401912 751 45376771139319802 752 46721503596207612 753 48105195323852920 754 49528823581532624 755 50993724860437336 756 52501011147446217 757 54051695754882260 758 55647275365966531 759 57288905725707656 760 58977744116542256 761 60715353806594465 762 62503046588288195 763 64342025408672880 764 66234037806392296 765 68180450139725446 766 70182631693920884 767 72242410426532115 768 74361332813050442 769 76540825425713504 770 78782928212685510 771 81089255217118946 772 83461425202465552 773 85901574961380090 774 88411526449715556 775 90992969725097707 776 93648285484837128 777 96379378850065628 778 99188161949368920 779 102077131795457004 780 105048433519360970 781 108104067374459420 782 111246811022091719 783 114478911422494040 784 117802625431899944 785 121220870072621461 786 124736169378218320 787 128350888497604312 788 132068267407797479 789 135890954252256616 790 139821610688586830 791 143863643292026132 792 148020020075465712 793 152293535095641625 794 156687966593499188 795 161206433232662443 796 165852071691164725 797 170628858955746217 798 175540282972114459 799 180589641565380839 800 185781339473964784 801 191119046846539912 802 196606457409614152 803 202248212541723452 804 208048408721843731 805 214010935033944736 806 220140925185502249 807 226442695298524120 808 232920591913977196 809 239580029993294167 810 246425817847181642 811 253462538004749969 812 260696172109368163 813 268131792464242312 814 275774510164139701 815 283630640570309088 816 291705824196869952 817 300005456294335291 818 308536504512269444 819 317304925805902368 820 326316726125808209 821 335579268466497285 822 345099165739742727 823 354882765056953832 824 364938180260339687 825 375272402635004704 826 385892484849765416 827 396807008405984392 828 408023721810821768 829 419550086250058345 830 431395547539732646 831 443568305585969467 832 456076636667668427 833 468930539029060281 834 482139086652526468 835 495711043801114324 836 509657403655681344 837 523987777587021540 838 538711871417722799 839 553841330029774767 840 569386773694953964 841 585358489843254780 842 601769268653750248 843 618630368911481796 844 635953165596786992 845 653751216740490625 846 672036945565412156 847 690822418813030304 848 710122512879588248 849 729950408280920624 850 750319427809934115 851 771245351491239797 852 792742703682069552 853 814825628375531137 854 837511423149989300 855 860815509011467104 856 884753480452369287 857 909343697262146513 858 934603131187955120 859 960548349840797616 860 987199459792273831 861 1014574492754656526 862 1042691691186909733 863 1071572408938174655 864 1101236467031818937 865 1131703259143801538 866 1162996149676503485 867 1195136210814173740 868 1228144769878355160 869 1262046654349822060 870 1296865000763511187 871 1332622496221231112 872 1369346282241403094 873 1407060970129824116 874 1445791479110570701 875 1485566665226013035 876 1526413521158732548 877 1568358569899337912 878 1611433330661930849 879 1655666532168373159 880 1701087273699864303 881 1747729081754022325 882 1795623431781942332 883 1844801311974197352 884 1895299313597822309 885 1947150953131105342 886 2000390191825278135 887 2055055968846711057 888 2111184968365278832 889 2168813373467321037 890 2227983649969257195 891 2288734878776595672 892 2351106673347440280 893 2415144243415363708 894 2480890322515097895 895 2548387134302007966 896 2617683946294270288 897 2688826303273416432 898 2761860386237820431 899 2836838666741457935 900 2913810900713175512 901 2992826331982067184 902 3073942100564891188 903 3157211256276340307 904 3242687607391031951 905 3330432032204220044 906 3420502434802007836 907 3512956213387381127 908 3607859616739520308 909 3705274404350754747 910 3805263238123420036 911 3907896725025655700 912 4013242219203633800 913 4121366585803059123 914 4232346609167185536 915 4346254151644067148 916 4463162147277874185 917 4583152457467634891 918 4706303391370969049 919 4832692799352793840 920 4962409647452350547 921 5095537511377382173 922 5232161237360637688 923 5372375701610424591 924 5516271907220003768 925 5663940445184538598 926 5815484361756518592 927 5971000806918696667 928 6130588434423215265 929 6294357165636540152 930 6462412706009627872 931 6634860415824930947 932 6811819610386480684 933 6993403163282752611 934 7179725725171423919 935 7370914603462598901 936 7567092524679564665 937 7768381961773015067 938 7974921021779773712 939 8186840783277107920 940 8404274421789963201 941 8627369328729768964 942 8856267927527664872 943 9091112509530556520 944 9332062879945950880 945 9579271185860986196 946 9832892045307222784 947 10093096042092387879 948 10360048383245964455 949 10633914301243564004 950 10914878646882594229 951 11203117938884729316 952 11498811603739493671 953 11802156997658976857 954 12113345670451765125 955 12432569398166030442 956 12760041931173957189 957 13095967968468212385 958 13440555626511175200 959 13794033155646274495 960 14156622550804467048 961 14528546285675911232 962 14910051445897982676 963 15301375300445721779 964 15702759129939012631 965 16114466822610602108 966 16536755545024146025 967 16969883256649223296 968 17414135481843201176 969 17869787116950351411 970 18337117761974616519 971 18816432400800225732 972 19308028815114730695 973 19812205966849339855 974 20329293688832274392 975 20859610329053423735 976 21403479744416130617 977 21961254291514597088 978 22533278633938791996 979 23119899089536360488 980 23721496548428171922 981 24338439515039345045 982 24971102938931864417 983 25619893766264392044 984 26285210754312398560 985 26967454891002369119 986 27667065880675055580 987 28384470099573262208 988 29120101456672886756 989 29874429782205509637 990 30647916223232598180 991 31441024854499899152 992 32254263107190800415 993 33088124104207145378 994 33943109763618066278 995 34819762329555380068 996 35718614878680743559 997 36640204254220794788 998 37585115851278875272 999 38553919744021950437 1000 39547196266028073751