1 1 2 4 3 13 4 22 5 55 6 64 7 133 8 172 9 247 10 280 11 469 12 508 13 781 14 868 15 997 16 1144 17 1621 18 1714 19 2323 20 2488 21 2785 22 3010 23 3907 24 4078 25 4837 26 5176 27 5833 28 6178 29 7627 30 7798 31 9463 32 10102 33 10927 34 11530 35 12631 36 13006 37 15379 38 16150 39 17311 40 17926 41 20863 42 21256 43 24505 44 25498 45 26719 46 27856 47 31753 48 32452 49 35761 50 36784 51 38869 52 40258 53 45235 54 46120 55 49159 56 50566 57 53173 58 55018 59 61183 60 61900 61 68509 62 70696 63 73399 64 75874 65 80239 66 81322 67 89287 68 91780 69 95731 70 97192 71 106153 72 107722 73 117247 74 120406 75 123841 76 126976 77 133717 78 135286 79 146419 80 149032 81 155017 82 158848 83 171205 84 172816 85 180595 86 184852 87 191239 88 195118 89 209323 90 210958 91 220639 92 225352 93 232681 94 237742 95 247531 96 250276 97 267109 98 271444 99 278839 100 282814 101 301075 102 303862 103 322915 104 328576 105 333583 106 340042 107 360595 108 364144 109 385549 110 389734 111 400363 112 406108 113 429121 114 432712 115 447457 116 455122 117 465823 118 473920 119 491113 120 494014 121 516223 122 524926 123 537991 124 546694 125 565675 126 569248 127 598237 128 608218 129 622651 130 628504 131 659425 132 663832 133 685561 134 696112 135 707143 136 717034 137 750835 138 756130 139 791011 140 796972 141 814285 142 826126 143 852727 144 859018 145 882769 146 895294 147 909985 148 922474 149 962491 150 967018 151 1008163 152 1020826 153 1039825 154 1048804 155 1076041 156 1082362 157 1126783 158 1141534 159 1163653 160 1173934 161 1206331 162 1214260 163 1262209 164 1277818 165 1291573 166 1307734 167 1358107 168 1364524 169 1409197 170 1419712 171 1443703 172 1460806 173 1514935 174 1523560 175 1551469 176 1567186 177 1594657 178 1613296 179 1671217 180 1677772 181 1737049 182 1750030 183 1779535 184 1798378 185 1837747 186 1847578 187 1894729 188 1915318 189 1939735 190 1952854 191 2018707 192 2029888 193 2097265 194 2119672 195 2139523 196 2157010 197 2227195 198 2237152 199 2308873 200 2325232 201 2361001 202 2385250 203 2437897 204 2449204 205 2497753 206 2522974 207 2558755 208 2581276 209 2640889 210 2647570 211 2728051 212 2754406 213 2794579 214 2821762 215 2875309 216 2889436 217 2949685 218 2977900 219 3020281 220 3036376 221 3103993 222 3118084 223 3208021 224 3230836 225 3261469 226 3291694 227 3384931 228 3399148 229 3494173 230 3514000 231 3544375 232 3574762 233 3673075 234 3687370 235 3751519 236 3784222 237 3834043 238 3856936 239 3960385 240 3972046 241 4077307 242 4107166 243 4161133 244 4196188 245 4250953 246 4268434 247 4354003 248 4389016 249 4444003 250 4469194 251 4583335 252 4597834 253 4686883 254 4725436 255 4760581 256 4800274 257 4919959 258 4939276 259 5026177 260 5049604 261 5107441 262 5148274 263 5273659 264 5291272 265 5373319 266 5402320 267 5465587 268 5507818 269 5638999 270 5653744 271 5786965 272 5827222 273 5870995 274 5915776 275 5992345 276 6013534 277 6152551 278 6198748 279 6265303 280 6289168 281 6432325 282 6455512 283 6600901 284 6648748 285 6693415 286 6729016 287 6836299 288 6861526 289 6996973 290 7029034 291 7104535 292 7154890 293 7310731 294 7330522 295 7432729 296 7483222 297 7550275 298 7603294 299 7731307 300 7749532 301 7867627 302 7922182 303 8004109 304 8054668 305 8163853 306 8189026 307 8359903 308 8395930 309 8481061 310 8517514 311 8692891 312 8718178 313 8895991 314 8955226 315 9000547 316 9059590 317 9242011 318 9271702 319 9416107 320 9457780 321 9549955 322 9593374 323 9745423 324 9777382 325 9887413 326 9951052 327 10046479 328 10108546 329 10250275 330 10268602 331 10467235 332 10532668 333 10628371 334 10695100 335 10827343 336 10852936 337 11058985 338 11118532 339 11221291 340 11262652 341 11428123 342 11460052 343 11620783 344 11689408 345 11755609 346 11827084 347 12045505 348 12079834 349 12301003 350 12338254 351 12434455 352 12496978 353 12723211 354 12760078 355 12908899 356 12984268 357 13061635 358 13138276 359 13372273 360 13398502 361 13612399 362 13691128 363 13791319 364 13843114 365 14000395 366 14039764 367 14284249 368 14359954 369 14478235 370 14530762 371 14711791 372 14751238 373 15003871 374 15067168 375 15152551 376 15234688 377 15441739 378 15474220 379 15735013 380 15787636 381 15917761 382 16005322 383 16271899 384 16316854 385 16429525 386 16518940 387 16649065 388 16738468 389 17013361 390 17039806 391 17266873 392 17337004 393 17475469 394 17568616 395 17753461 396 17793184 397 18079429 398 18174688 399 18272791 400 18337426 401 18629491 402 18677194 403 18915049 404 19012420 405 19112233 406 19182352 407 19420687 408 19465576 409 19769425 410 19834642 411 19986277 412 20087380 413 20312845 414 20360620 415 20564617 416 20654536 417 20810419 418 20890060 419 21208909 420 21235660 421 21557593 422 21664846 423 21821239 424 21926428 425 22121713 426 22175254 427 22416391 428 22525648 429 22645423 430 22716778 431 23054035 432 23110666 433 23451367 434 23531884 435 23639287 436 23752486 437 24039415 438 24096142 439 24446395 440 24512134 441 24645049 442 24735520 443 25092025 444 25148974 445 25383991 446 25503658 447 25683199 448 25774600 449 26140993 450 26182066 451 26476411 452 26598598 453 26783161 454 26907136 455 27068935 456 27125584 457 27504877 458 27631072 459 27801799 460 27880060 461 28266241 462 28306834 463 28696495 464 28819126 465 28942693 466 29073214 467 29469823 468 29527138 469 29819347 470 29905642 471 30105289 472 30236098 473 30560689 474 30627340 475 30874363 476 30966250 477 31165741 478 31303024 479 31720105 480 31766848 481 32109433 482 32249434 483 32395873 484 32514178 485 32793919 486 32865568 487 33296497 488 33436552 489 33651769 490 33724756 491 34162993 492 34233160 493 34600909 494 34715686 495 34839877 496 34980070 497 35308267 498 35381830 499 35834335 500 35935894 501 36161761 502 36313360 503 36773545 504 36831574 505 37135441 506 37254946 507 37455853 508 37610074 509 38081239 510 38128216 511 38475511 512 38635072 513 38851219 514 39010216 515 39326239 516 39403474 517 39792415 518 39908110 519 40150507 520 40244380 521 40737697 522 40815010 523 41312455 524 41477146 525 41602861 526 41769304 527 42191227 528 42261850 529 42729853 530 42839992 531 43088611 532 43204930 533 43627561 534 43712428 535 44053573 536 44223034 537 44482663 538 44656852 539 44987635 540 45046552 541 45578401 542 45755458 543 46021039 544 46180492 545 46534621 546 46592680 547 47136541 548 47316508 549 47582371 550 47684110 551 48148747 552 48233464 553 48640957 554 48825988 555 49003201 556 49187992 557 49752049 558 49840732 559 50306659 560 50401870 561 50614225 562 50804236 563 51380485 564 51473224 565 51853999 566 52047028 567 52266709 568 52456822 569 53045551 570 53104732 571 53697733 572 53839846 573 54136081 574 54279124 575 54647389 576 54748126 577 55353499 578 55534186 579 55836505 580 55963258 581 56413543 582 56514340 583 57011365 584 57213100 585 57391165 586 57597760 587 58224301 588 58303006 589 58836337 590 58973044 591 59287981 592 59489890 593 60129667 594 60219082 595 60505957 596 60718822 597 61039969 598 61210726 599 61863175 600 61936036 601 62593033 602 62750908 603 63072601 604 63291400 605 63662425 606 63771652 607 64441777 608 64643866 609 64880725 610 65026690 611 65585257 612 65686492 613 66369901 614 66597502 615 66816751 616 66960916 617 67653193 618 67767142 619 68464339 620 68610682 621 68933197 622 69166624 623 69685723 624 69787180 625 70262185 626 70498684 627 70767643 628 71003974 629 71611477 630 71671702 631 72395827 632 72632668 633 72994609 634 73237042 635 73719523 636 73837936 637 74313355 638 74506372 639 74868037 640 75033562 641 75780787 642 75903652 643 76655989 644 76829542 645 77070985 646 77273908 647 78035425 648 78163156 649 78781915 650 78928744 651 79200505 652 79455490 653 80231203 654 80359060 655 80872273 656 81121798 657 81504649 658 81693742 659 82483951 660 82557556 661 83352673 662 83617684 663 83923783 664 84185380 665 84548587 666 84676282 667 85369855 668 85637818 669 86041975 670 86218552 671 86880223 672 86983264 673 87807169 674 88081588 675 88358743 676 88596706 677 89430691 678 89568136 679 90186097 680 90353320 681 90772183 682 90993118 683 91842007 684 91970350 685 92532307 686 92746984 687 93173089 688 93447940 689 94162063 690 94250566 691 95119423 692 95407594 693 95681515 694 95972134 695 96550513 696 96687850 697 97437595 698 97731778 699 98173327 700 98322208 701 99216313 702 99344698 703 100113139 704 100364674 705 100654483 706 100955182 707 101625325 708 101772736 709 102687457 710 102886630 711 103336087 712 103637206 713 104433925 714 104537398 715 104981437 716 105289432 717 105753667 718 106064506 719 107005207 720 107110276 721 107807317 722 108092506 723 108564823 724 108879640 725 109476265 726 109609600 727 110571205 728 110778334 729 111262711 730 111472846 731 112299175 732 112456684 733 113434489 734 113760238 735 114006631 736 114307702 737 115108651 738 115266262 739 116260183 740 116470600 741 116857477 742 117099220 743 118103761 744 118261582 745 118927015 746 119263228 747 119759785 748 120011194 749 120763957 750 120877864 751 121903969 752 122233996 753 122746615 754 123023662 755 123707083 756 123837154 757 124879879 758 125227258 759 125628535 760 125839336 761 126893233 762 127067092 763 127848523 764 128199910 765 128516077 766 128870128 767 129758653 768 129937924 769 131014369 770 131164666 771 131702107 772 132060538 773 133148407 774 133322530 775 134007655 776 134366380 777 134757661 778 135123016 779 136071379 780 136177066 781 137078197 782 137381794 783 137903899 784 138183958 785 138922999 786 139107832 787 140234797 788 140608558 789 141171649 790 141418222 791 142258345 792 142417120 793 143367757 794 143748814 795 144118807 796 144499528 797 145655617 798 145786066 799 146777503 800 147037072 801 147609103 802 147997564 803 148950769 804 149141614 805 149683003 806 150000040 807 150588445 808 150976684 809 152167597 810 152300404 811 153497461 812 153778294 813 154376077 814 154694152 815 155491345 816 155670832 817 156715603 818 157120054 819 157513039 820 157771660 821 158997913 822 159200212 823 160433017 824 160837996 825 161182789 826 161483296 827 162727969 828 162919366 829 164170579 830 164444062 831 165069229 832 165430210 833 166273699 834 166482244 835 167319145 836 167637706 837 168236371 838 168660430 839 169941775 840 170048884 841 171252877 842 171681874 843 172325233 844 172754230 845 173498641 846 173707054 847 174524725 848 174945904 849 175597711 850 175857202 851 177003649 852 177217972 853 178542361 854 178864234 855 179263795 856 179700310 857 181037107 858 181196950 859 182540323 860 182826688 861 183309685 862 183758656 863 185114653 864 185341822 865 186240769 866 186694378 867 187303849 868 187626148 869 188744893 870 188888092 871 190038577 872 190492504 873 191173297 874 191556826 875 192254827 876 192481558 877 193881127 878 194347204 879 195046351 880 195307294 881 196720171 882 196897630 883 198317299 884 198679834 885 199140433 886 199614916 887 201047617 888 201274864 889 202339411 890 202654324 891 203257591 892 203736832 893 204990793 894 205230694 895 206193469 896 206559610 897 207136117 898 207623314 899 208912519 900 209076646 901 210343177 902 210736660 903 211269121 904 211756600 905 212740285 906 212986366 907 214483543 908 214980310 909 215719003 910 215934820 911 217445473 912 217672990 913 218908915 914 219414460 915 219907309 916 220412470 917 221544847 918 221772382 919 223309903 920 223625098 921 224393179 922 224907070 923 226201741 924 226363900 925 227349193 926 227867752 927 228636001 928 229123690 929 230695195 930 230859604 931 231926131 932 232449706 933 233238025 934 233765308 935 234552697 936 234780388 937 236378305 938 236767276 939 237565315 940 237907576 941 239519437 942 239785564 943 241201339 944 241725760 945 242132905 946 242565598 947 244198147 948 244464616 949 245833699 950 246163018 951 246981949 952 247349542 953 249003079 954 249269686 955 250366693 956 250917826 957 251567203 958 252121912 959 253361221 960 253547788 961 255126451 962 255583276 963 256412941 964 256972864 965 258092815 966 258287434 967 259989691 968 260464864 969 261150463 970 261523894 971 263240347 972 263527552 973 264803431 974 265377562 975 265872493 976 266432674 977 268170535 978 268457842 979 269881609 980 270173380 981 271034731 982 271617790 983 273377575 984 273658012 985 274825495 986 275316826 987 275955235 988 276412960 989 277973125 990 278138416 991 279926293 992 280486960 993 281380651 994 281818600 995 283009501 996 283303996 997 285113893 998 285716944 999 286579633 1000 286984546 1001 287963365 1002 288264730 1003 289840429 1004 290448352 1005 291043939 1006 291655438 1007 293256925 1008 293488354 1009 295341907 1010 295747768 1011 296673751 1012 297148588 1013 299017261 1014 299285380 1015 300162235 1016 300779596 1017 301705375 1018 302331754 1019 304222507 1020 304409728 1021 306308125 1022 306772000 1023 307517707 1024 308155048 1025 309371725 1026 309659296 1027 311266045 1028 311903470 1029 312627889 1030 313049254 1031 314984443 1032 315293314 1033 317236699 1034 317757256 1035 318354367 1036 318818356 1037 320504671 1038 320828602 1039 322794523 1040 323170534 1041 324152785 1042 324809818 1043 326277955 1044 326587678 1045 327583867 1046 328245712 1047 329238523 1048 329895220 1049 331899037 1050 332066524 1051 334078069 1052 334746184 1053 335613367 1054 336176032 1055 337516405 1056 337799164 1057 339306649 1058 339930736 1059 340946953 1060 341384530 1061 343434403 1062 343765792 1063 345824113 1064 346289236 1065 346959895 1066 347524258 1067 349219225 1068 349558468 1069 351639865 1070 352096510 1071 352793881 1072 353472232 1073 355328899 1074 355675978 1075 357017185 1076 357715858 1077 358767229 1078 359209090 1079 360984493 1080 361220818 1081 363091969 1082 363800902 1083 364764037 1084 365472862 1085 366479413 1086 366833572 1087 368984569 1088 369624388 1089 370525645 1090 370998292 1091 373165429 1092 373398376 1093 375573781 1094 376298674 1095 377008477 1096 377727526 1097 379919479 1098 380274502 1099 381906289 1100 382316128 1101 383415163 1102 384035986 1103 386252107 1104 386591884 1105 387723829 1106 388267612 1107 389331565 1108 390072004 1109 392311897 1110 392548864 1111 394387921 1112 395129188 1113 395945521 1114 396696340 1115 398194033 1116 398549098 1117 400821247 1118 401443498 1119 402578893 1120 402960454 1121 404953447 1122 405237268 1123 407534089 1124 408297382 1125 409067479 1126 409834804 1127 411427177 1128 411797764 1129 414119401 1130 414629116 1131 415563229 1132 416336458 1133 418249597 1134 418543030 1135 420094867 1136 420858142 1137 422030317 1138 422813818 1139 424855387 1140 425092438 1141 426850879 1142 427640452 1143 428813233 1144 429381142 1145 430960285 1146 431354956 1147 433485319 1148 434057530 1149 435254101 1150 435744376 1151 438156745 1152 438559978 1153 440981551 1154 441788530 1155 442295773 1156 443017258 1157 445062355 1158 445465852 1159 447598633 1160 448108858 1161 449282377 1162 449883496 1163 452346877 1164 452750776 1165 454386433 1166 455051266 1167 456285925 1168 457093102 1169 458939725 1170 459177310 1171 461674471 1172 462504274 1173 463527007 1174 464361250 1175 465970267 1176 466285246 1177 468350935 1178 469062580 1179 470310493 1180 470854984 1181 473395009 1182 473815414 1183 475455937 1184 476262808 1185 477094753 1186 477945460 1187 480511285 1188 480868594 1189 483160135 1190 483542884 1191 484828867 1192 485680612 1193 488273041 1194 488702266 1195 490423669 1196 491107270 1197 491988871 1198 492857212 1199 495001081 1200 495292624 1201 497919337 1202 498794506 1203 500107375 1204 500738800 1205 502488667 1206 502917652 1207 505213369 1208 506088808 1209 507160393 1210 507653356 1211 509634991 1212 510072634 1213 512751979 1214 513644644 1215 514541647 1216 515350162 1217 518047759 1218 518363266 1219 520754839 1220 521338438 1221 522411583 1222 523157662 1223 525881947 1224 526287112 1225 527654923 1226 528564922 1227 529930099 1228 530840098 1229 533591299 1230 533883418 1231 536643907 1232 537220876 1233 538587247 1234 539509492 1235 540940897 1236 541396276 1237 544183249 1238 545111782 1239 546127243 1240 546711640 1241 549139759 1242 549569338 1243 551875165 1244 552810106 1245 553730521 1246 554422408 1247 556947811 1248 557354104 1249 560195449 1250 560829334 1251 562236037 1252 563182666 1253 565306069 1254 565664470 1255 567562999 1256 568509628 1257 569942719 1258 570752338 1259 573639667 1260 573880792 1261 576315331 1262 577280362 1263 578727883 1264 579675406 1265 581161939 1266 581644096 1267 583814521 1268 584785408 1269 586192363 1270 586835542 1271 589465039 1272 589937986 1273 592518919 1274 593153218 1275 594030703 1276 594798730 1277 597767923 1278 598250410 1279 601229779 1280 601894468 1281 602980105 1282 603974866 1283 606973135 1284 607465348 1285 609456655 1286 610458322 1287 611537527 1288 612230434 1289 615256423 1290 615578596 1291 618614329 1292 619426828 1293 620944207 1294 621958324 1295 623407459 1296 623917690 1297 626981431 1298 627807862 1299 629338753 1300 629926360 1301 633009421 1302 633371878 1303 636464899 1304 637486840 1305 638453983 1306 639486958 1307 642599623 1308 643111000 1309 644848267 1310 645534628 1311 646828621 1312 647824132 1313 650465935 1314 650976808 1315 653062525 1316 653819572 1317 655392787 1318 656444272 1319 659613433 1320 659907904 1321 663086893 1322 664146280 1323 665344363 1324 666403378 1325 668459527 1326 668866846 1327 672074755 1328 673122436 1329 674726137 1330 675210598 1331 677903947 1332 678415516 1333 681315247 1334 682243228 1335 683303599 1336 684375244 1337 686795113 1338 687334588 1339 690082819 1340 690789184 1341 692406997 1342 693290374 1343 696141097 1344 696553120 1345 698735227 1346 699832798 1347 701479057 1348 702576628 1349 705480433 1350 705849682 1351 708319999 1352 709272136 1353 710596807 1354 711706678 1355 713921047 1356 714469810 1357 717444679 1358 718267678 1359 719928811 1360 720593620 1361 723967225 1362 724525966 1363 727555735 1364 728439544 1365 729167575 1366 730296850 1367 733700203 1368 734212222 1369 737450989 1370 738201868 1371 739907971 1372 740766538 1373 744200935 1374 744770344 1375 746686237 1376 747784444 1377 749321227 1378 750274732 1379 752848759 1380 753202342 1381 756675835 1382 757833268 1383 759569305 1384 760719916 1385 763034965 1386 763399840 1387 766470433 1388 767635042 1389 769386163 1390 770158126 1391 773126011 1392 773675320 1393 776302129 1394 777303436 1395 778411909 1396 779588794 1397 782507593 1398 783096274 1399 786661531