0 1 1 1 2 1 3 0 4 1 5 2 6 2 7 2 8 3 9 4 10 4 11 4 12 5 13 7 14 7 15 8 16 10 17 12 18 14 19 14 20 17 21 20 22 22 23 24 24 28 25 33 26 36 27 40 28 45 29 52 30 56 31 62 32 71 33 80 34 88 35 96 36 109 37 122 38 133 39 144 40 163 41 182 42 198 43 216 44 240 45 268 46 290 47 316 48 349 49 386 50 420 51 456 52 502 53 552 54 600 55 650 56 713 57 780 58 846 59 916 60 1001 61 1093 62 1182 63 1280 64 1393 65 1516 66 1636 67 1768 68 1920 69 2084 70 2248 71 2424 72 2629 73 2844 74 3063 75 3296 76 3565 77 3852 78 4142 79 4454 80 4806 81 5184 82 5566 83 5976 84 6433 85 6927 86 7430 87 7968 88 8566 89 9204 90 9864 91 10562 92 11336 93 12160 94 13014 95 13924 96 14922 97 15986 98 17088 99 18264 100 19543 101 20908 102 22322 103 23832 104 25473 105 27216 106 29032 107 30960 108 33054 109 35272 110 37586 111 40040 112 42700 113 45518 114 48458 115 51578 116 54939 117 58508 118 62226 119 66172 120 70410 121 74906 122 79603 123 84576 124 89909 125 95556 126 101466 127 107712 128 114399 129 121468 130 128876 131 136704 132 145062 133 153900 134 163152 135 172936 136 183352 137 194360 138 205886 139 218066 140 231023 141 244700 142 259030 143 274152 144 290227 145 307171 146 324932 147 343656 148 363537 149 384492 150 406448 151 429592 152 454119 153 479968 154 507040 155 535564 156 565751 157 597554 158 630870 159 665944 160 703035 161 742068 162 782976 163 825998 164 871454 165 919264 166 969364 167 1022044 168 1077639 169 1136090 170 1197318 171 1261680 172 1329527 173 1400832 174 1475502 175 1553966 176 1636625 177 1723436 178 1814346 179 1909800 180 2010304 181 2115789 182 2226235 183 2342144 184 2464102 185 2592060 186 2725994 187 2866502 188 3014214 189 3169152 190 3331264 191 3501268 192 3679865 193 3867120 194 4063022 195 4268352 196 4483944 197 4709868 198 4946190 199 5193758 200 5453560 201 5725684 202 6010274 203 6308304 204 6620865 205 6948146 206 7290294 207 7648496 208 8023932 209 8416900 210 8827610 211 9257426 212 9707721 213 10178844 214 10671128 215 11186088 216 11725357 217 12289322 218 12878478 219 13494528 220 14139373 221 14813538 222 15517598 223 16253568 224 17023548 225 17828292 226 18668466 227 19546420 228 20464538 229 21423794 230 22425048 231 23470944 232 24564265 233 25706136 234 26897738 235 28142008 236 29442194 237 30799664 238 32215888 239 33694272 240 35238467 241 36850204 242 38531220 243 40285504 244 42117151 245 44028340 246 46021140 247 48100176 248 50270157 249 52533632 250 54893206 251 57354072 252 59921752 253 62599212 254 65389647 255 68299000 256 71333627 257 74497108 258 77793210 259 81228816 260 84811119 261 88544532 262 92433424 263 96485788 264 100709820 265 105110809 266 109694010 267 114468488 268 119443734 269 124625916 270 130021410 271 135640490 272 141494123 273 147589552 274 153934390 275 160540444 276 167420185 277 174582280 278 182035572 279 189793776 280 197871029 281 206277624 282 215023954 283 224125776 284 233599337 285 243456628 286 253709962 287 264377280 288 275477363 289 287024090 290 299032046 291 311521712 292 324514674 293 338027232 294 352076308 295 366685528 296 381879432 297 397677260 298 414098622 299 431170684 300 448921500 301 467373578 302 486549830 303 506481248 304 527200072 305 548732328 306 571104944 307 594353174 308 618514065 309 643617820 310 669695806 311 696788448 312 724937964 313 754179565 314 784549506 315 816094264 316 848861896 317 882893404 318 918230730 319 954927138 320 993037626 321 1032609476 322 1073691478 323 1116344280 324 1160631026 325 1206606168 326 1254326278 327 1303860624 328 1355281425 329 1408651636 330 1464036460 331 1521515198 332 1581170103 333 1643074144 334 1707302250 335 1773945220 336 1843096844 337 1914841322 338 1989265135 339 2066471696 340 2146568282 341 2229651588 342 2315821514 343 2405195784 344 2497896980 345 2594036224 346 2693728570 347 2797108368 348 2904315177 349 3015476964 350 3130725636 351 3250214776 352 3374103107 353 3502537776 354 3635670162 355 3773675402 356 3916734452 357 4065015872 358 4218693552 359 4377966720 360 4543041878 361 4714111816 362 4891376138 363 5075061560 364 5265403330 365 5462622362 366 5666946904 367 5878635362 368 6097955058 369 6325159216 370 6560508634 371 6804297560 372 7056829964 373 7318395540 374 7589292540 375 7869855344 376 8160429859 377 8461346652 378 8772946998 379 9095610506 380 9429730659 381 9775684708 382 10133862374 383 10504695168 384 10888629727 385 11286096770 386 11697540474 387 12123451448 388 12564336373 389 13020686648 390 13493008408 391 13981858848 392 14487813195 393 15011430848 394 15553288816 395 16114018872 396 16694274257 397 17294691292 398 17915927166 399 18558698352 400 19223745849 401 19911793716 402 20623589228 403 21359945088 404 22121700750 405 22909680164 406 23724732220 407 24567778420 408 25439769694 409 26341642456 410 27274361428 411 28238969944 412 29236545511 413 30268150932 414 31334882304 415 32437920362 416 33578485367 417 34757783236 418 35977058100 419 37237646428 420 38540928597 421 39888272911 422 41281089684 423 42720891712 424 44209239574 425 45747684820 426 47337825800 427 48981373406 428 50680092291 429 52435739700 430 54250126810 431 56125186824 432 58062914905 433 60065299908 434 62134393051 435 64272378224 436 66481509596 437 68764038148 438 71122284308 439 73558715150 440 76075875255 441 78676311548 442 81362647534 443 84137668776 444 87004247103 445 89965262104 446 93023679462 447 96182641824 448 99445389930 449 102815176512 450 106295353298 451 109889463888 452 113601163813 453 117434126128 454 121392135910 455 125479188768 456 129699404801 457 134056930680 458 138556037580 459 143201229584 460 147997148353 461 152948472892 462 158060021064 463 163336867298 464 168784240097 465 174407414900 466 180211824960 467 186203183352 468 192387378261 469 198770354546 470 205358236268 471 212157453824 472 219174634575 473 226416476136 474 233889876352 475 241602071284 476 249560515761 477 257772753140 478 266246548740 479 274990042008 480 284011616006 481 293319761529 482 302923218474 483 312831136704 484 323052940888 485 333598182408 486 344476694538 487 355698758824 488 367274966600 489 379216058324 490 391533091578 491 404237616772 492 417341529705 493 430856904348 494 444796167540 495 459172291584 496 473998631773 497 489288755092 498 505056622354 499 521316795686 500 538084265468 501 555374267616 502 573202481148 503 591585244824 504 610539379132 505 630081986594 506 650230668548 507 671003751088 508 692420099850 509 714498907092 510 737259921316 511 760723692038 512 784911368514 513 809844480652 514 835545176786 515 862036490696 516 889342124153 517 917486218322 518 946493605260 519 976390091320 520 1007202231070 521 1038957080316 522 1071682470830 523 1105407303984 524 1140161319626 525 1175974829596 526 1212879013546 527 1250906230348 528 1290089772091 529 1330463587384 530 1372062590646 531 1414923000288 532 1459082071246 533 1504577810592 534 1551449300956 535 1599737064710 536 1649482779348 537 1700728976112 538 1753519389598 539 1807899338448 540 1863915433396 541 1921615250112 542 1981047710091 543 2042263479968 544 2105314667344 545 2170254474026 546 2237137600094 547 2306020673978 548 2376961925307 549 2450020827772 550 2525258519396 551 2602738270156 552 2682525130160 553 2764685558016 554 2849287866474 555 2936402717840 556 3026102759820 557 3118462226568 558 3213557422186 559 3311467237922 560 3412272778784 561 3516056936368 562 3622904908894 563 3732904748784 564 3846146968630 565 3962724098042 566 4082731228848 567 4206266608560 568 4333431214197 569 4464328297804 570 4599063959272 571 4737747782632 572 4880492386430 573 5027412943888 574 5178627799772 575 5334259139232 576 5494432525971 577 5659276386290 578 5828922678384 579 6003507595032 580 6183171085415 581 6368056310476 582 6558310353368 583 6754084975584 584 6955536105411 585 7162823278752 586 7376110382434 587 7595566471872 588 7821365226125 589 8053684367832 590 8292706451850 591 8538619733808 592 8791617607116 593 9051897985176 594 9319664154724 595 9595125685296 596 9878497855013 597 10170000993500 598 10469861397432 599 10778312296496 600 11095593249962 601 11421949468394 602 11757632778156 603 12102902663264 604 12458025620073 605 12823274463560 606 13198929343678 607 13585278863042 608 13982619399150 609 14391254377596 610 14811495365394 611 15243663248232 612 15688087539531 613 16145105604711 614 16615063843082 615 17098318930752 616 17595237108034 617 18106193367372 618 18631572710392 619 19171771481954 620 19727196616266 621 20298264806888 622 20885403828150 623 21489053975496 624 22109667268165 625 22747706594666 626 23403647118170 627 24077977807440 628 24771200620707 629 25483829603172 630 26216392403318 631 26969431885252 632 27743505301301 633 28539183341312 634 29357051759798 635 30197713089720 636 31061785783073 637 31949903236888 638 32862715513128 639 33800891186008 640 34765116431107 641 35756094038168 642 36774545231778 643 37821211650432 644 38896854401982 645 40002253039020 646 41138207515042 647 42305540279400 648 43505095322921 649 44737737097298 650 46004352626756 651 47305853725648 652 48643176028420 653 50017277869848 654 51429142535104 655 52879780641456 656 54370229123301 657 55901550102336 658 57474833265360 659 59091198430108 660 60751794488360 661 62457798256874 662 64210417011741 663 66010891223576 664 67860493490746 665 69760527343068 666 71712329974140 667 73717275133480 668 75776772066012 669 77892264269184 670 80065232425166 671 82297197484728 672 84589719583825 673 86944396791996 674 89362868225868 675 91846817368512 676 94397970943343 677 97018097669208 678 99709011568250 679 102472575527232 680 105310700152064 681 108225342501284 682 111218509642662 683 114292262434992 684 117448714403728 685 120690030429591 686 124018430583722 687 127436194149632 688 130945658510898 689 134549217823860 690 138249327115922 691 142048506604466 692 145949340566589 693 149954476037104 694 154066627159904 695 158288579842132 696 162623190609486 697 167073385324648 698 171642163838910 699 176332604963792 700 181147865365549 701 186091178268852 702 191165858470456 703 196375307623344 704 201723013193233 705 207212547156564 706 212847571388250 707 218631843309004 708 224569214875352 709 230663631327556 710 236919136932822 711 243339881068328 712 249930117220417 713 256694201812012 714 263636600330702 715 270761893860590 716 278074778134545 717 285580062409132 718 293282676058086 719 301187675539992 720 309300243561345 721 317625687977832 722 326169448907524 723 334937106165952 724 343934378542810 725 353167122775872 726 362641341171852 727 372363189604202 728 382338976866693 729 392575163788448 730 403078371364618 731 413855389375108 732 424913175837607 733 436258856265228 734 447899732382290 735 459843291360600 736 472097205449551 737 484669331344788 738 497567719589408 739 510800624431000 740 524376503679051 741 538304018207132 742 552592042070302 743 567249673073688 744 582286232827408 745 597711266474690 746 613534553520660 747 629766119222624 748 646416234831645 749 663495417599932 750 681014442377538 751 698984353867864 752 717416467126491 753 736322367824800 754 755713924747002 755 775603302908832 756 796002964416043 757 816925668973452 758 838384487374446 759 860392815556120 760 882964375835379 761 906113217748830 762 929853732547802 763 954200668335410 764 979169131661313 765 1004774588804496 766 1031032881300172 767 1057960242272744 768 1085573298436352 769 1113889071851316 770 1142924996616692 771 1172698936416896 772 1203229187067337 773 1234534478726136 774 1266633993915664 775 1299547386327974 776 1333294784003943 777 1367896792064828 778 1403374512141468 779 1439749562588184 780 1477044082296122 781 1515280734096952 782 1554482725628922 783 1594673831152288 784 1635878396010199 785 1678121340815356 786 1721428183872392 787 1765825064687978 788 1811338749219386 789 1857996634849648 790 1905826774584304 791 1954857902306904 792 2005119438986512 793 2056641498472716 794 2109454913642137 795 2163591263538608 796 2219082880617047 797 2275962857516436 798 2334265075221704 799 2394024232345370 800 2455275853424373 801 2518056296873836 802 2582402785261946 803 2648353436933544 804 2715947275486559 805 2785224238999586 806 2856225212655246 807 2928992062803304 808 3003567647851332 809 3079995828806700 810 3158321504537264 811 3238590648393266 812 3320850320704712 813 3405148680784928 814 3491535025002766 815 3580059826246900 816 3670774748091161 817 3763732658538816 818 3858987671028240 819 3956595187067864 820 4056611912174232 821 4159095871577188 822 4264106454401002 823 4371704459690976 824 4481952114384125 825 4594913091072648 826 4710652555746686 827 4829237217367080 828 4950735348195753 829 5075216803748090 830 5202753074427382 831 5333417338941776 832 5467284487186939 833 5604431142701136 834 5744935718393896 835 5888878474249730 836 6036341542902585 837 6187408954968576 838 6342166699112452 839 6500702784437096 840 6663107269024080 841 6829472288390299 842 6999892120339776 843 7174463252288928 844 7353284413222340 845 7536456605452740 846 7724083174775000 847 7916269883041670 848 8113124943914499 849 8314759058268852 850 8521285490038336 851 8732820144558916 852 8949481608360753 853 9171391188733200 854 9398672995582446 855 9631454026159152 856 9869864209179804 857 10114036449016132 858 10364106714069220 859 10620214128344304 860 10882501020434958 861 11151112972640524 862 11426198916556972 863 11707911231913248 864 11996405801030623 865 12291842063243312 866 12594383118356600 867 12904195833342432 868 13221450902749023 869 13546322909047204 870 13878990434446712 871 14219636176279550 872 14568447013760289 873 14925614074988320 874 15291332857697854 875 15665803354094904 876 16049230124588933 877 16441822372023266 878 16843794072209736 879 17255364108837200 880 17676756355020604 881 18108199755274260 882 18549928466809632 883 19002182005212048 884 19465205334613081 885 19939248958146960 886 20424569070830688 887 20921427717028272 888 21430092889868962 889 21950838631193714 890 22483945196790318 891 23029699226786408 892 23588393855052757 893 24160328819591184 894 24745810641150726 895 25345152807551726 896 25958675894130302 897 26586707685353808 898 27229583368143378 899 27887645731068528 900 28561245297055020 901 29250740457124058 902 29956497679704110 903 30678891725937760 904 31418305795698809 905 32175131674724620 906 32949769961037064 907 33742630297913934 908 34554131534229177 909 35384701886412608 910 36234779183237556 911 37104811117994836 912 37995255424469217 913 38906580055005782 914 39839263445337978 915 40793794787320592 916 41770674222222313 917 42770413036135824 918 43793533946715262 919 44840571398007120 920 45912071772700769 921 47008593606472608 922 48130707898359932 923 49278998429664192 924 50454061996645923 925 51656508645779685 926 52886962009465500 927 54146059651229128 928 55434453320517975 929 56752809210840676 930 58101808322922190 931 59482146838263686 932 60894536398206618 933 62339704386757728 934 63818394323730100 935 65331366268744296 936 66879397126967650 937 68463280958652554 938 70083829404830227 939 71741872124260048 940 73438257128128300 941 75173851118864400 942 76949539950800778 943 78766229103090264 944 80624844045643536 945 82526330610095404 946 84471655488114536 947 86461806743333908 948 88497794211311764 949 90580649905383448 950 92711428555915046 951 94891208164176784 952 97121090439639729 953 99402201243496200 954 101735691172513000 955 104122736158069440 956 106564537944181815 957 109062324572016300 958 111617351011890324 959 114230899811403504 960 116904281617441808 961 119638835705624940 962 122435930664097944 963 125296965095071728 964 128223368184430278 965 131216600280145636 966 134278153632119528 967 137409553151401622 968 140612357031758574 969 143888157381002512 970 147238581021852470 971 150665290313201136 972 154169983828489361 973 157754397044296980 974 161420303207338614 975 165169514222883424 976 169003881394707205 977 172925296176152816 978 176935691108335800 979 181037040781587256 980 185231362641944367 981 189520717810412720 982 193907212097946338 983 198392997046016664 984 202980270805370773 985 207671279029234632 986 212468315971605638 987 217373725613027912 988 222389902618246708 989 227519293309308300 990 232764396854332022 991 238127766485177224 992 243612010540866149 993 249219793527443232 994 254953837404469396 995 260816922902331288 996 266811890658368147 997 272941642371339506 998 279209142193190232 999 285617418154517488 1000 292169563400985775