0 1 1 9 2 39 3 107 4 233 5 413 6 699 7 1047 8 1557 9 2129 10 2927 11 3779 12 4929 13 6117 14 7683 15 9263 16 11309 17 13337 18 15927 19 18459 20 21657 21 24749 22 28619 23 32327 24 36933 25 41313 26 46719 27 51827 28 58097 29 63989 30 71187 31 77919 32 86109 33 93737 34 102983 35 111563 36 121929 37 131517 38 143067 39 153719 40 166517 41 178289 42 192399 43 205347 44 220833 45 235013 46 251939 47 267407 48 285837 49 302649 50 322647 51 340859 52 362489 53 382157 54 405483 55 426663 56 451749 57 474497 58 501407 59 525779 60 554577 61 580629 62 611379 63 639167 64 671933 65 701513 66 736359 67 767787 68 804777 69 838109 70 877307 71 912599 72 954069 73 991377 74 1035183 75 1074563 76 1120769 77 1162277 78 1210947 79 1254639 80 1305837 81 1351769 82 1405559 83 1453787 84 1510233 85 1560813 86 1619979 87 1672967 88 1734917 89 1790369 90 1855167 91 1913139 92 1980849 93 2041397 94 2112083 95 2175263 96 2248989 97 2314857 98 2391687 99 2460299 100 2540297 101 2611709 102 2694939 103 2769207 104 2855733 105 2932913 106 3022799 107 3102947 108 3196257 109 3279429 110 3376227 111 3462479 112 3562829 113 3652217 114 3756183 115 3848763 116 3956409 117 4052237 118 4163627 119 4262759 120 4377957 121 4480449 122 4599519 123 4705427 124 4828433 125 4937813 126 5064819 127 5177727 128 5308797 129 5425289 130 5560487 131 5680619 132 5820009 133 5943837 134 6087483 135 6215063 136 6363029 137 6494417 138 6646767 139 6782019 140 6938817 141 7077989 142 7239299 143 7382447 144 7548333 145 7695513 146 7866039 147 8017307 148 8192537 149 8347949 150 8527947 151 8687559 152 8872389 153 9036257 154 9225983 155 9394163 156 9588849 157 9761397 158 9961107 159 10138079 160 10342877 161 10524329 162 10734279 163 10920267 164 11135433 165 11326013 166 11546459 167 11741687 168 11967477 169 12167409 170 12398607 171 12603299 172 12839969 173 13049477 174 13291683 175 13506063 176 13753869 177 13973177 178 14226647 179 14450939 180 14710137 181 14939469 182 15204459 183 15438887 184 15709733 185 15949313 186 16226079 187 16470867 188 16753617 189 17003669 190 17292467 191 17547839 192 17842749 193 18103497 194 18404583 195 18670763 196 18978089 197 19249757 198 19563387 199 19840599 200 20160597 201 20443409 202 20769839 203 21058307 204 21391233 205 21685413 206 22024899 207 22324847 208 22670957 209 22976729 210 23329527 211 23641179 212 24000729 213 24318317 214 24684683 215 25008263 216 25381509 217 25711137 218 26091327 219 26427059 220 26814257 221 27156149 222 27550419 223 27898527 224 28299933 225 28654313 226 29062919 227 29423627 228 29839497 229 30206589 230 30629787 231 31003319 232 31433909 233 31813937 234 32251983 235 32638563 236 33084129 237 33477317 238 33930467 239 34330319 240 34791117 241 35197689 242 35666199 243 36079547 244 36555833 245 36976013 246 37460139 247 37887207 248 38379237 249 38813249 250 39313247 251 39754259 252 40262289 253 40710357 254 41226483 255 41681663 256 42205949 257 42668297 258 43200807 259 43670379 260 44211177 261 44688029 262 45237179 263 45721367 264 46278933 265 46770513 266 47336559 267 47835587 268 48410177 269 48916709 270 49499907 271 50013999 272 50605869 273 51127577 274 51728183 275 52257563 276 52866969 277 53404077 278 54022347 279 54567239 280 55194437 281 55747169 282 56383359 283 56943987 284 57589233 285 58157813 286 58812179 287 59388767 288 60052317 289 60636969 290 61309767 291 61902539 292 62584649 293 63185597 294 63877083 295 64486263 296 65187189 297 65804657 298 66515087 299 67140899 300 67860897 301 68495109 302 69224739 303 69867407 304 70606733 305 71257913 306 72006999 307 72666747 308 73425657 309 74094029 310 74862827 311 75539879 312 76318629 313 77004417 314 77793183 315 78487763 316 79286609 317 79990037 318 80799027 319 81511359 320 82330557 321 83051849 322 83881319 323 84611627 324 85451433 325 86190813 326 87041019 327 87789527 328 88650197 329 89407889 330 90279087 331 91046019 332 91927809 333 92704037 334 93596483 335 94382063 336 95285229 337 96080217 338 96994167 339 97798619 340 98723417 341 99537389 342 100473099 343 101296647 344 102243333 345 103076513 346 104034239 347 104877107 348 105845937 349 106698549 350 107678547 351 108540959 352 109532189 353 110404457 354 111406983 355 112289163 356 113303049 357 114195197 358 115220507 359 116122679 360 117159477 361 118071729 362 119120079 363 120042467 364 121102433 365 122035013 366 123106659 367 124049487 368 125132877 369 126086009 370 127181207 371 128144699 372 129251769 373 130225677 374 131344683 375 132329063 376 133460069 377 134454977 378 135598047 379 136603539 380 137758737 381 138774869 382 139942259 383 140969087 384 142148733 385 143186313 386 144378279 387 145426667 388 146631017 389 147690269 390 148907067 391 149977239 392 151206549 393 152287697 394 153529583 395 154621763 396 155876289 397 156979557 398 158246787 399 159361199 400 160641197 401 161766809 402 163059639 403 164196507 404 165502233 405 166650413 406 167969099 407 169128647 408 170460357 409 171631329 410 172976127 411 174158579 412 175516529 413 176710517 414 178081683 415 179287263 416 180671709 417 181888937 418 183286727 419 184515659 420 185926857 421 187167549 422 188592219 423 189844727 424 191282933 425 192547313 426 193999119 427 195275427 428 196740897 429 198029189 430 199508387 431 200808719 432 202301709 433 203614137 434 205120983 435 206445563 436 207966329 437 209303117 438 210837867 439 212186919 440 213735717 441 215097089 442 216659999 443 218033747 444 219610833 445 220997013 446 222588339 447 223987007 448 225592637 449 227003849 450 228623847 451 230047659 452 231682089 453 233118557 454 234767483 455 236216663 456 237880149 457 239342097 458 241020207 459 242494979 460 244187777 461 245675429 462 247382979 463 248883567 464 250605933 465 252119513 466 253856759 467 255383387 468 257135577 469 258675309 470 260442507 471 261995399 472 263777669 473 265343777 474 267141183 475 268720563 476 270533169 477 272125877 478 273953747 479 275559839 480 277403037 481 279022569 482 280881159 483 282514187 484 284388233 485 286034813 486 287924379 487 289584567 488 291489717 489 293163569 490 295084367 491 296771939 492 298708449 493 300409797 494 302362083 495 304077263 496 306045389 497 307774457 498 309758487 499 311501499 500 313501497 501 315258509 502 317274539 503 319045607 504 321077733 505 322862913 506 324911199 507 326710547 508 328775057 509 330588629 510 332669427 511 334497279 512 336594429 513 338436617 514 340550183 515 342406763 516 344536809 517 346407837 518 348554427 519 350439959 520 352603157 521 354503249 522 356683119 523 358597827 524 360794433 525 362723813 526 364937219 527 366881327 528 369111597 529 371070489 530 373317687 531 375291419 532 377555609 533 379544237 534 381825483 535 383829063 536 386127429 537 388146017 538 390461567 539 392495219 540 394828017 541 396876789 542 399226899 543 401290847 544 403658333 545 405737513 546 408122439 547 410216907 548 412619337 549 414729149 550 417149147 551 419274359 552 421711989 553 423852657 554 426307983 555 428464163 556 430937249 557 433108997 558 435599907 559 437787279 560 440296077 561 442499129 562 445025879 563 447244667 564 449789433 565 452024013 566 454586859 567 456837287 568 459418277 569 461684609 570 464283807 571 466566099 572 469183569 573 471481877 574 474117683 575 476432063 576 479086269 577 481416777 578 484089447 579 486436139 580 489127337 581 491490269 582 494200059 583 496579287 584 499307733 585 501703313 586 504450479 587 506862467 588 509628417 589 512056869 590 514841667 591 517286639 592 520090349 593 522551897 594 525374583 595 527852763 596 530694489 597 533189357 598 536050187 599 538561799 600 541441797 601 543970209 602 546869439 603 549414707 604 552333233 605 554895413 606 557833299 607 560412447 608 563369757 609 565965929 610 568942727 611 571555979 612 574552329 613 577182717 614 580198683 615 582846263 616 585881909 617 588546737 618 591602127 619 594284259 620 597359457 621 600058949 622 603154019 623 605870927 624 608985933 625 611720313 626 614855319 627 617607227 628 620762297 629 623531789 630 626706987 631 629494119 632 632689509 633 635494337 634 638709983 635 641532563 636 644768529 637 647608917 638 650865267 639 653723519 640 657000317 641 659876489 642 663173799 643 666067947 644 669385833 645 672298013 646 675636539 647 678566807 648 681926037 649 684874449 650 688254447 651 691221059 652 694621889 653 697606757 654 701028483 655 704031663 656 707474349 657 710495897 658 713959607 659 716999579 660 720484377 661 723542829 662 727048779 663 730125767 664 733652933 665 736748513 666 740296959 667 743411187 668 746980977 669 750113909 670 753705107 671 756856799 672 760469469 673 763639977 674 767274183 675 770463563 676 774119369 677 777327677 678 781005147 679 784232439 680 787931637 681 791177969 682 794898959 683 798164387 684 801907233 685 805191813 686 808956579 687 812260367 688 816047117 689 819370169 690 823178967 691 826521339 692 830352249 693 833713997 694 837567083 695 840948263 696 844823589 697 848224257 698 852121887 699 855542099 700 859462097 701 862901909 702 866844339 703 870303807 704 874268733 705 877747913 706 881735399 707 885234347 708 889244457 709 892763229 710 896796027 711 900334679 712 904390229 713 907948817 714 912027183 715 915605763 716 919707009 717 923305637 718 927429827 719 931048559 720 935195757 721 938834649 722 943004919 723 946664027 724 950857433 725 954536813 726 958753419 727 962453127 728 966692997 729 970413089 730 974676287 731 978416819 732 982703409 733 986464437 734 990774483 735 994556063 736 998889629 737 1002691817 738 1007048967 739 1010871819 740 1015252617 741 1019096189 742 1023500699 743 1027365047 744 1031793333 745 1035678513 746 1040130639 747 1044036707 748 1048512737 749 1052439749 750 1056939747 751 1060887759 752 1065411789 753 1069380857 754 1073928983 755 1077919163 756 1082491449 757 1086502797 758 1091099307 759 1095131879 760 1099752677 761 1103806529 762 1108451679 763 1112526867 764 1117196433 765 1121293013 766 1125987059 767 1130105087 768 1134823677 769 1138963209 770 1143706407 771 1147867499 772 1152635369 773 1156818077 774 1161610683 775 1165815063 776 1170632469 777 1174858577 778 1179700847 779 1183948739 780 1188815937 781 1193085669 782 1197977859 783 1202269487 784 1207186733 785 1211500313 786 1216442679 787 1220778267 788 1225745817 789 1230103469 790 1235096267 791 1239476039 792 1244494149 793 1248896097 794 1253939583 795 1258363763 796 1263432689 797 1267879157 798 1272973587 799 1277442399 800 1282562397 801 1287053609 802 1292199239 803 1296712907 804 1301884233 805 1306420413 806 1311617499 807 1316176247 808 1321399157 809 1325980529 810 1331229327 811 1335833379 812 1341108129 813 1345734917 814 1351035683 815 1355685263 816 1361012109 817 1365684537 818 1371037527 819 1375732859 820 1381112057 821 1385830349 822 1391235819 823 1395977127 824 1401408933 825 1406173313 826 1411631519 827 1416419027 828 1421903697 829 1426714389 830 1432225587 831 1437059519 832 1442597309 833 1447454537 834 1453018983 835 1457899563 836 1463490729 837 1468394717 838 1474012667 839 1478940119 840 1484584917 841 1489535889 842 1495207599 843 1500182147 844 1505880833 845 1510879013 846 1516604739 847 1521626607 848 1527379437 849 1532425049 850 1538205047 851 1543274459 852 1549081689 853 1554174957 854 1560009483 855 1565126663 856 1570988549 857 1576129697 858 1582019007 859 1587184179 860 1593100977 861 1598290229 862 1604234579 863 1609447967 864 1615419933 865 1620657513 866 1626657159 867 1631918987 868 1637946377 869 1643232509 870 1649287707 871 1654598199 872 1660681269 873 1666016177 874 1672127183 875 1677486563 876 1683625569 877 1689009477 878 1695176547 879 1700585039 880 1706780237 881 1712213369 882 1718436759 883 1723894587 884 1730146233 885 1735628813 886 1741908779 887 1747416167 888 1753724517 889 1759256769 890 1765593567 891 1771150739 892 1777516049 893 1783098197 894 1789492083 895 1795099263 896 1801521789 897 1807154057 898 1813605287 899 1819262699 900 1825742697 901 1831425309 902 1837934139 903 1843642007 904 1850179733 905 1855912913 906 1862479599 907 1868238147 908 1874833857 909 1880617829 910 1887242627 911 1893052079 912 1899706029 913 1905541017 914 1912224183 915 1918084763 916 1924797209 917 1930683437 918 1937425227 919 1943337159 920 1950108357 921 1956046049 922 1962846719 923 1968810227 924 1975640433 925 1981629813 926 1988489619 927 1994504927 928 2001394397 929 2007435689 930 2014354887 931 2020422219 932 2027371209 933 2033464637 934 2040443483 935 2046563063 936 2053571829 937 2059717617 938 2066756367 939 2072928419 940 2079997217 941 2086195589 942 2093294499 943 2099519247 944 2106648333 945 2112899513 946 2120058839 947 2126336507 948 2133526137 949 2139830349 950 2147050347 951 2153381159 952 2160631589 953 2166989057 954 2174269983 955 2180654163 956 2187965649 957 2194376597 958 2201718707 959 2208156479 960 2215529277 961 2221993929 962 2229397479 963 2235889067 964 2243323433 965 2249842013 966 2257307259 967 2263852887 968 2271349077 969 2277921809 970 2285449007 971 2292048899 972 2299607169 973 2306234277 974 2313823683 975 2320478063 976 2328098669 977 2334780377 978 2342432247 979 2349141339 980 2356824537 981 2363561069 982 2371275659 983 2378039687 984 2385785733 985 2392577313 986 2400354879 987 2407174067 988 2414983217 989 2421830069 990 2429670867 991 2436545439 992 2444417949 993 2451320297 994 2459224583 995 2466154763 996 2474090889 997 2481048957 998 2489016987 999 2496002999 1000 2504002997