1 0 2 0 3 0 4 2 5 1 6 4 7 2 8 6 9 5 10 8 11 7 12 14 13 10 14 19 15 17 16 26 17 24 18 37 19 32 20 50 21 47 22 65 23 63 24 87 25 83 26 112 27 110 28 143 29 143 30 183 31 182 32 229 33 233 34 285 35 291 36 356 37 363 38 435 39 451 40 531 41 551 42 649 43 671 44 782 45 818 46 937 47 982 48 1126 49 1175 50 1338 51 1406 52 1583 53 1667 54 1873 55 1965 56 2201 57 2318 58 2576 59 2714 60 3010 61 3167 62 3500 63 3688 64 4057 65 4276 66 4695 67 4941 68 5407 69 5700 70 6216 71 6546 72 7132 73 7503 74 8150 75 8584 76 9295 77 9783 78 10587 79 11129 80 12015 81 12641 82 13609 83 14311 84 15396 85 16171 86 17367 87 18250 88 19553 89 20539 90 21986 91 23074 92 24663 93 25888 94 27621 95 28979 96 30890 97 32388 98 34477 99 36149 100 38425 101 40268 102 42770 103 44795 104 47514 105 49766 106 52723 107 55190 108 58431 109 61131 110 64646 111 67632 112 71440 113 74700 114 78863 115 82417 116 86924 117 90831 118 95701 119 99960 120 105261 121 109886 122 115618 123 120680 124 126864 125 132360 126 139065 127 145026 128 152261 129 158751 130 166548 131 173576 132 182004 133 189608 134 198677 135 206931 136 216690 137 225599 138 236125 139 245741 140 257040 141 267451 142 279583 143 290792 144 303853 145 315921 146 329914 147 342945 148 357937 149 371940 150 388044 151 403084 152 420318 153 436510 154 454936 155 472309 156 492058 157 510678 158 531779 159 551776 160 574309 161 595720 162 619811 163 642726 164 668431 165 692977 166 720390 167 746620 168 775880 169 803905 170 835067 171 865029 172 898221 173 930179 174 965552 175 999634 176 1037249 177 1073630 178 1113632 179 1152366 180 1194941 181 1236182 182 1281396 183 1325337 184 1373348 185 1420074 186 1471095 187 1520758 188 1574886 189 1627712 190 1685107 191 1741205 192 1802107 193 1861651 194 1926186 195 1989414 196 2057771 197 2124826 198 2197247 199 2268336 200 2344985 201 2420359 202 2501460 203 2581285 204 2667102 205 2751627 206 2842339 207 2931840 208 3027717 209 3122381 210 3223724 211 3323830 212 3430827 213 3536708 214 3649667 215 3761519 216 3880788 217 3998930 218 4124733 219 4249531 220 4382190 221 4513896 222 4653816 223 4792757 224 4940208 225 5086804 226 5242135 227 5396685 228 5560335 229 5723208 230 5895507 231 6067154 232 6248499 233 6429268 234 6620125 235 6810450 236 7011202 237 7211563 238 7422671 239 7633468 240 7855444 241 8077166 242 8310428 243 8543624 244 8788701 245 9033799 246 9291277 247 9548829 248 9819159 249 10089793 250 10373562 251 10657756 252 10955628 253 11253987 254 11566481 255 11879706 256 12207446 257 12536100 258 12879837 259 13224565 260 13584902 261 13946483 262 14324102 263 14703182 264 15098901 265 15496203 266 15910711 267 16327081 268 16761154 269 17197316 270 17651827 271 18108613 272 18584344 273 19062664 274 19560485 275 20061152 276 20582040 277 21105971 278 21650765 279 22198996 280 22768681 281 23342085 282 23937752 283 24537351 284 25159924 285 25786876 286 26437428 287 27092705 288 27772461 289 28457178 290 29167176 291 29882609 292 30624006 293 31371270 294 32145419 295 32925712 296 33733790 297 34548523 298 35391799 299 36242208 300 37122153 301 38009583 302 38927512 303 39853482 304 40810821 305 41776707 306 42775035 307 43782344 308 44823120 309 45873508 310 46958311 311 48053290 312 49183875 313 50325102 314 51503037 315 52692361 316 53919406 317 55158458 318 56436553 319 57727161 320 59058023 321 60402228 322 61787770 323 63187376 324 64629741 325 66086737 326 67587836 327 69104450 328 70666346 329 72244604 330 73869649 331 75511697 332 77202009 333 78910292 334 80668140 335 82444875 336 84272794 337 86120373 338 88020707 339 89941752 340 91917014 341 93913969 342 95966895 343 98042399 344 100175554 345 102332465 346 104548612 347 106789592 348 109091737 349 111419672 350 113810575 351 116228620 352 118711324 353 121222348 354 123800145 355 126407310 356 129083217 357 131789960 358 134567272 359 137376755 360 140259070 361 143174711 362 146165353 363 149190892 364 152293413 365 155432342 366 158650659 367 161906678 368 165244434 369 168621607 370 172082692 371 175584815 372 179173439 373 182804593 374 186524745 375 190289288 376 194145233 377 198047318 378 202043597 379 206087674 380 210228624 381 214419434 382 218709697 383 223051734 384 227496274 385 231994374 386 236597850 387 241257194 388 246024674 389 250850115 390 255786983 391 260783776 392 265895116 393 271068864 394 276360133 395 281716147 396 287193194 397 292737135 398 298405513 399 304143442 400 310009032 401 315946753 402 322015877 403 328159509 404 334438201 405 340794297 406 347288963 407 353863792 408 360581209 409 367381463 410 374328197 411 381360890 412 388543898 413 395815851 414 403242441 415 410760879 416 418438143 417 426210681 418 434146145 419 442180126 420 450381720 421 458684960 422 467160305 423 475741052 424 484498296 425 493364475 426 502412173 427 511572223 428 520918646 429 530381442 430 540035338 431 549809501 432 559780104 433 569874691 434 580170978 435 590595556 436 601226925 437 611990825 438 622967222 439 634080218 440 645411326 441 656883702 442 668579706 443 680421517 444 692493046 445 704714882 446 717172420 447 729785291 448 742639812 449 755654580 450 768917532 451 782345577 452 796028224 453 809881434 454 823995599 455 838285633 456 852843663 457 867582767 458 882596739 459 897797725 460 913280371 461 928955771 462 944920348 463 961083334 464 977542889 465 994207184 466 1011175334 467 1028354497 468 1045845506 469 1063553613 470 1081581537 471 1099833350 472 1118412794 473 1137222875 474 1156369130 475 1175752634 476 1195480805 477 1215453525 478 1235779338 479 1256356921 480 1277296701 481 1298495452 482 1320065451 483 1341902262 484 1364119352 485 1386611036 486 1409492733 487 1432656743 488 1456220450 489 1480074948 490 1504338756 491 1528901717 492 1553884445 493 1579174590 494 1604894831 495 1630931626 496 1657408791 497 1684211512 498 1711465715 499 1739054400 500 1767105647 501 1795501105 502 1824370075 503 1853593027 504 1883301305 505 1913373126 506 1943942134 507 1974885114 508 2006336993 509 2038173293 510 2070531086 511 2103283620 512 2136570270 513 2170262825 514 2204502053 515 2239158339 516 2274374705 517 2310019270 518 2346237344 519 2382895561 520 2420140689 521 2457837944 522 2496136403 523 2534898861 524 2574276858 525 2614131718 526 2654616350 527 2695590640 528 2737210005 529 2779331725 530 2822113773 531 2865411922 532 2909385597 533 2953889100 534 2999084355 535 3044823048 536 3091269806 537 3138274632 538 3186003676 539 3234305557 540 3283348891 541 3332979611 542 3383369160 543 3434361730 544 3486130349 545 3538517726 546 3591699492 547 3645515630 548 3700144596 549 3755424619 550 3811535873 551 3868314933 552 3925944692 553 3984259011 554 4043443628 555 4103330597 556 4164107409 557 4225604512 558 4288012177 559 4351157935 560 4415235078 561 4480069404 562 4545855856 563 4612418570 564 4679955477 565 4748287658 566 4817616151 567 4887760216 568 4958922672 569 5030921092 570 5103961277 571 5177857708 572 5252819466 573 5328659033 574 5405587357 575 5483415301 576 5562356782 577 5642219491 578 5723220754 579 5805166238 580 5888275176 581 5972351482 582 6057617558 583 6143874113 584 6231346923 585 6319834637 586 6409565147 587 6500335159 588 6592375835 589 6685480650 590 6779884250 591 6875377980 592 6972198599 593 7070135556 594 7169429009 595 7269864948 596 7371687154 597 7474679598 598 7579088089 599 7684694635 600 7791748642 601 7900028545 602 8009787458 603 8120801701 604 8233326566 605 8347136381 606 8462490030 607 8579158228 608 8697403780 609 8816995077 610 8938197178 611 9060776584 612 9185001955 613 9310636068 614 9437951608 615 9566709077 616 9697183451 617 9829133160 618 9962836978 619 10098049662 620 10235053947 621 10373602232 622 10513979790 623 10655936795 624 10799762410 625 10945203058 626 11092552024 627 11241553322 628 11392502763 629 11545142151 630 11699771367 631 11856128225 632 12014516864 633 12174672814 634 12336902659 635 12500939643 636 12667094631 637 12835096791 638 13005261316 639 13177314959 640 13351575566 641 13527767597 642 13706213130 643 13886632481 644 14069352376 645 14254090464 646 14441176185 647 14630324979 648 14821870609 649 15015524241 650 15211624351 651 15409879496 652 15610630978 653 15813584926 654 16019087117 655 16226839529 656 16437192589 657 16649845560 658 16865151949 659 17082808465 660 17303173186 661 17525938561 662 17751467524 663 17979449755 664 18210251249 665 18443559143 666 18679744240 667 18918489139 668 19160169625 669 19404465695 670 19651756127 671 19901718286 672 20154735929 673 20410481884 674 20669344961 675 20930995188 676 21195824594 677 21463500661 678 21734420299 679 22008246344 680 22285381140 681 22565484492 682 22848962013 683 23135470997 684 23425422095 685 23718467846 686 24015024367 687 24314741213 688 24618037951 689 24924561374 690 25234736227 691 25548204715 692 25865396983 693 26185952137 694 26510304028 695 26838088925 696 27169745936 697 27504906583 698 27844015654 699 28186701542 700 28533412682 701 28883774606 702 29238241363 703 29596433404 704 29958810586 705 30324990373 706 30695436290 707 31069762835 708 31448439261 709 31831075034 710 32218145348 711 32609256422 712 33004887329 713 33404641493 714 33809003601 715 34217571897 716 34630837436 717 35048394997 718 35470739579 719 35897463138 720 36329066530 721 36765136423 722 37206180042 723 37651780636 724 38102449636 725 38557767174 726 39018250657 727 39483475147 728 39953964380 729 40429289860 730 40909979746 731 41395602450 732 41886692189 733 42382812065 734 42884502944 735 43391324436 736 43903821703 737 44421551210 738 44945064616 739 45473912739 740 46008654018 741 46548835871 742 47095021136 743 47646753994 744 48204603851 745 48768109294 746 49337846732 747 49913351038 748 50495203200 749 51082935132 750 51677134241 751 52277326675 752 52884107297 753 53496998384 754 54116599427 755 54742429640 756 55375095283 757 56014109713 758 56660086619 759 57312535473 760 57972075002 761 58638211268 762 59311569872 763 59991651232 764 60679088420 765 61373377828 766 62075157710 767 62783921145 768 63500313405 769 64223821596 770 64955098801 771 65693628256 772 66440068065 773 67193898056 774 67955783875 775 68725199036 776 69502817134 777 70288107848 778 71081749998 779 71883209779 780 72693173558 781 73511101282 782 74337687613 783 75172388271 784 76015903290 785 76867685278 786 77728441682 787 78597618667 788 79475932382 789 80362824728 790 81259017275 791 82163948629 792 83078348155 793 84001648042 794 84934586265 795 85876590686 796 86828405232 797 87789454092 798 88760489111 799 89740928227 800 90731532031 801 91731714001 802 92742240759 803 93762522267 804 94793333277 805 95834077100 806 96885537555 807 97947113794 808 99019595452 809 100102378020 810 101196259855 811 102300629508 812 103416294551 813 104542639277 814 105680477440 815 106829189625 816 107989598252 817 109161076981 818 110344457963 819 111539110159 820 112745872020 821 113964109180 822 115194668711 823 116436909124 824 117691687554 825 118958357863 826 120237783599 827 121529315008 828 122833824694 829 124150655902 830 125480691138 831 126823268923 832 128179278806 833 129548055304 834 130930497143 835 132325931949 836 133735268630 837 135157829954 838 136594531850 839 138044693295 840 139509239754 841 140987482813 842 142480358373 843 143987173630 844 145508871277 845 147044754565 846 148595776234 847 150161232029 848 151742085273 849 153337627110 850 154948828090 851 156574975472 852 158217049749 853 159874330629 854 161547809840 855 163236762017 856 164942186245 857 166663353635 858 168401273250 859 170155208478 860 171926179848 861 173713445859 862 175518034548 863 177339200494 864 179177982185 865 181033626745 866 182907183908 867 184797895757 868 186706820278 869 188633195308 870 190578089394 871 192540732873 872 194522206038 873 196521734086 874 198540405431 875 200577441218 876 202633940979 877 204709117788 878 206804083151 879 208918045483 880 211052124296 881 213205523793 882 215379375019 883 217572874121 884 219787164314 885 222021436768 886 224276843205 887 226552570755 888 228849782486 889 231167657414 890 233507371573 891 235868098483 892 238251022830 893 240655314396 894 243082169434 895 245530749415 896 248002263661 897 250495868458 898 253012782053 899 255552156501 900 258115221994 901 260701122783 902 263311101878 903 265944298147 904 268601964225 905 271283234615 906 273989374017 907 276719508913 908 279474917468 909 282254720774 910 285060206431 911 287890491311 912 290746875779 913 293628468109 914 296536582340 915 299470321847 916 302431010077 917 305417746045 918 308431866271 919 311472461357 920 314540881733 921 317636212637 922 320759814499 923 323910768528 924 327090447947 925 330297925424 926 333534589042 927 336799505650 928 340094073441 929 343417355387 930 346770762964 931 350153350425 932 353566544083 933 357009392672 934 360483333141 935 363987409760 936 367523073071 937 371089359222 938 374687733440 939 378317226147 940 381979313792 941 385673022390 942 389399842131 943 393158790568 944 396951373329 945 400776602330 946 404635994182 947 408528556482 948 412455820489 949 416416784693 950 420412996007 951 424443447745 952 428509697969 953 432610735515 954 436748133231 955 440920871246 956 445130538394 957 449376109032 958 453659183675 959 457978732804 960 462336371414 961 466731061038 962 471164433647 963 475635444738 964 480145738077 965 484694265227 966 489282685140 967 493909940350 968 498577706672 969 503284920867 970 508033271251 971 512821690052 972 517651881054 973 522522768072 974 527436071731 975 532390709854 976 537388416050 977 542428103886 978 547511522604 979 552637576856 980 557808033611 981 563021791796 982 568280631004 983 573583445920 984 578932032895 985 584325277089 986 589764992772 987 595250059665 988 600782305177 989 606360604618 990 611986802131 991 617659763951 992 623381352734 993 629150428588 994 634968867717 995 640835526612 996 646752297979 997 652718028956 998 658734631663 999 664800947075 1000 670918901003