0 1 1 1 2 1 3 2 4 3 5 5 6 6 7 9 8 11 9 14 10 17 11 22 12 26 13 32 14 37 15 42 16 50 17 59 18 69 19 80 20 91 21 101 22 115 23 133 24 152 25 170 26 190 27 210 28 235 29 265 30 300 31 334 32 366 33 398 34 441 35 484 36 541 37 597 38 648 39 703 40 770 41 848 42 935 43 1022 44 1102 45 1184 46 1281 47 1406 48 1534 49 1661 50 1789 51 1916 52 2062 53 2244 54 2435 55 2620 56 2804 57 2997 58 3210 59 3473 60 3763 61 4042 62 4300 63 4571 64 4883 65 5237 66 5641 67 6043 68 6409 69 6799 70 7257 71 7777 72 8322 73 8887 74 9406 75 9936 76 10553 77 11258 78 12027 79 12800 80 13535 81 14286 82 15115 83 16102 84 17164 85 18170 86 19164 87 20194 88 21327 89 22655 90 24103 91 25474 92 26806 93 28188 94 29715 95 31444 96 33317 97 35195 98 36989 99 38812 100 40889 101 43221 102 45687 103 48172 104 50530 105 52892 106 55580 107 58672 108 61894 109 65129 110 68287 111 71458 112 74969 113 78968 114 83181 115 87315 116 91354 117 95508 118 100054 119 105147 120 110691 121 116107 122 121281 123 126658 124 132517 125 139002 126 146060 127 153017 128 159681 129 166547 130 174181 131 182577 132 191455 133 200276 134 208837 135 217495 136 227062 137 237796 138 249004 139 260232 140 271276 141 282353 142 294407 143 307897 144 322062 145 336053 146 349781 147 363790 148 378982 149 395902 150 413859 151 431562 152 448741 153 466364 154 485556 155 506434 156 528608 157 550845 158 572297 159 594327 160 618332 161 644460 162 671937 163 699526 164 726282 165 753402 166 782940 167 815517 168 849639 169 883623 170 917087 171 950996 172 987375 173 1027562 174 1069561 175 1110997 176 1152059 177 1194026 178 1238869 179 1288096 180 1340017 181 1391444 182 1441882 183 1493361 184 1548532 185 1608328 186 1671394 187 1734489 188 1796078 189 1858919 190 1926883 191 2000336 192 2076891 193 2153889 194 2229155 195 2305469 196 2387950 197 2477380 198 2570520 199 2663972 200 2756109 201 2849587 202 2949318 203 3057486 204 3170564 205 3283036 206 3394187 207 3507746 208 3628491 209 3759177 210 3896707 211 4033198 212 4167281 213 4304634 214 4450538 215 4607380 216 4771749 217 4936195 218 5098144 219 5263367 220 5439956 221 5629284 222 5826219 223 6024107 224 6219241 225 6416927 226 6627801 227 6855277 228 7091191 229 7327999 230 7562827 231 7800448 232 8052744 233 8324578 234 8606757 235 8888535 236 9168061 237 9453203 238 9755003 239 10078544 240 10416291 241 10753659 242 11086796 243 11427020 244 11786682 245 12169665 246 12570026 247 12971709 248 13368130 249 13772686 250 14201688 251 14658562 252 15133292 253 15609624 254 16080976 255 16559697 256 17066806 257 17608900 258 18170221 259 18733442 260 19294206 261 19863236 262 20462804 263 21103340 264 21767094 265 22431208 266 23092791 267 23766172 268 24474524 269 25229625 270 26014600 271 26800334 272 27579448 273 28373224 274 29209407 275 30095523 276 31016301 277 31942338 278 32859735 279 33794713 280 34781766 281 35825877 282 36906434 283 37994298 284 39073625 285 40169907 286 41325521 287 42550522 288 43817852 289 45092400 290 46361913 291 47651746 292 49004304 293 50439726 294 51925052 295 53412598 296 54896462 297 56408156 298 57991199 299 59667838 300 61406091 301 63147631 302 64881367 303 66648808 304 68499175 305 70451516 306 72474204 307 74509020 308 76534299 309 78595257 310 80758180 311 83037810 312 85391504 313 87762153 314 90122131 315 92517792 316 95031519 317 97684986 318 100421455 319 103176215 320 105927256 321 108721173 322 111643069 323 114723871 324 117902787 325 121096105 326 124286035 327 127534467 328 130924755 329 134494262 330 138187480 331 141896278 332 145593906 333 149361667 334 153293058 335 157421606 336 161690582 337 165986809 338 170270877 339 174632533 340 179190565 341 183973268 342 188902812 343 193868098 344 198826562 345 203863094 346 209122361 347 214649201 348 220339483 349 226072290 350 231810592 351 237635365 352 243703678 353 250078130 354 256641732 355 263242931 356 269849908 357 276570788 358 283566980 359 290905157 360 298473110 361 306085308 362 313692185 363 321436100 364 329496592 365 337925276 366 346617157 367 355377700 368 364129570 369 373037182 370 382313974 371 392008441 372 401988423 373 412050663 374 422112471 375 432335042 376 442974324 377 454107375 378 465559318 379 477099007 380 488661603 381 500408837 382 512607447 383 525369538 384 538493217 385 551698479 386 564940538 387 578410984 388 592387144 389 606993163 390 622029638 391 637167510 392 652327013 393 667749218 394 683750225 395 700436934 396 717610167 397 734928238 398 752263773 399 769892535 400 788204690 401 807287095 402 826890335 403 846670146 404 866481359 405 886606500 406 907500269 407 929280930 408 951647009 409 974209731 410 996842352 411 1019833801 412 1043653134 413 1068479325 414 1093978827 415 1119669788 416 1145450014 417 1171669792 418 1198812018 419 1227082098 420 1256143919 421 1285419920 422 1314772921 423 1344634605 424 1375539747 425 1407676508 426 1440696491 427 1474003532 428 1507404733 429 1541366909 430 1576540730 431 1613096317 432 1650602132 433 1688459321 434 1726439848 435 1765009752 436 1804940706 437 1846461812 438 1889039953 439 1932010083 440 1975167577 441 2018992728 442 2064308240 443 2111408301 444 2159707499 445 2208410822 446 2257333223 447 2307072539 448 2358464878 449 2411830899 450 2466601608 451 2521830313 452 2577268223 453 2633644493 454 2691874804 455 2752255386 456 2814221573 457 2876767439 458 2939546453 459 3003371443 460 3069325268 461 3137694267 462 3207776039 463 3278523006 464 3349572052 465 3421736911 466 3496278833 467 3573584592 468 3652774676 469 3732711525 470 3813084040 471 3894706736 472 3978918198 473 4066226295 474 4155660234 475 4245886441 476 4336622046 477 4428825225 478 4523904008 479 4622416255 480 4723379378 481 4825247138 482 4927612286 483 5031653233 484 5138938788 485 5249954945 486 5363709631 487 5478582265 488 5594007686 489 5711315232 490 5832317910 491 5957458440 492 6085574825 493 6214981343 494 6345059569 495 6477158350 496 6613356053 497 6754255335 498 6898465578 499 7044104412 500 7190620934 501 7339412854 502 7492657813 503 7651173798 504 7813406616 505 7977130029 506 8141884324 507 8309291813 508 8481625550 509 8659788585 510 8842183707 511 9026273799 512 9211446225 513 9399619002 514 9593297779 515 9793325359 516 9998063649 517 10204865768 518 10412879527 519 10624198555 520 10841776518 521 11066396395 522 11296118517 523 11528218689 524 11761715737 525 11998785747 526 12242823644 527 12494794725 528 12752412387 529 13012669956 530 13274675770 531 13540700905 532 13814304583 533 14096715162 534 14385448165 535 14677003813 536 14970557940 537 15268769216 538 15575313394 539 15891571404 540 16215048259 541 16541684178 542 16870439060 543 17204439535 544 17547711612 545 17901597118 546 18263486431 547 18629085640 548 18997071178 549 19370859633 550 19755106686 551 20151095673 552 20555737234 553 20964609596 554 21376280462 555 21794212161 556 22223718914 557 22666419672 558 23118650550 559 23575614607 560 24035967884 561 24503259568 562 24983169273 563 25477709896 564 25982868673 565 26493123926 566 27007179571 567 27529210861 568 28065165165 569 28617194384 570 29181233642 571 29750979595 572 30324792326 573 30907584489 574 31505818370 575 32121506799 576 32750511821 577 33386176834 578 34026361184 579 34676486695 580 35343890563 581 36030560811 582 36731731696 583 37440397941 584 38154264361 585 38878897055 586 39622604496 587 40387897713 588 41169132230 589 41958642660 590 42754346229 591 43562008319 592 44390413705 593 45242697111 594 46112640564 595 46991511919 596 47877422239 597 48776907048 598 49699194770 599 50647708737 600 51616048525 601 52594430969 602 53580368681 603 54581421553 604 55607732307 605 56662550513 606 57739272240 607 58827575708 608 59924231027 609 61037571606 610 62179170346 611 63352122434 612 64548856137 613 65758616585 614 66977856875 615 68215258039 616 69483780233 617 70787147956 618 72116671754 619 73460589708 620 74815587848 621 76190717591 622 77599594642 623 79046932072 624 80523287206 625 82015175649 626 83519509907 627 85046585812 628 86610674550 629 88216989657 630 89855746005 631 91511727893 632 93181198635 633 94875978021 634 96611581969 635 98393090891 636 100210259397 637 102047118942 638 103899027897 639 105778746370 640 107703895967 641 109679456269 642 111693711972 643 113730102960 644 115783430560 645 117866881906 646 120000315677 647 122189642703 648 124421408847 649 126677607187 650 128953257499 651 131262209279 652 133625535692 653 136050318536 654 138521945770 655 141020077859 656 143539902972 657 146097257153 658 148714120535 659 151398130881 660 154134400131 661 156900030077 662 159689191271 663 162519963877 664 165416132731 665 168385251909 666 171411879079 667 174471747393 668 177557662346 669 180689317653 670 183893441201 671 187177602993 672 190524175639 673 193907685090 674 197320476694 675 200782906837 676 204324818634 677 207955254192 678 211653864078 679 215393202120 680 219166071712 681 222993576714 682 226907404963 683 230918386650 684 235004425211 685 239134765392 686 243302374727 687 247530979598 688 251853980032 689 256283093386 690 260795495408 691 265356912451 692 269958667412 693 274627873764 694 279400841939 695 284288881890 696 289268304722 697 294302907950 698 299382016360 699 304535281247 700 309803132774 701 315196725782 702 320689545339 703 326243581648 704 331847311802 705 337531550427 706 343341075404 707 349289226297 708 355345945246 709 361469911309 710 367650134558 711 373918896466 712 380323560875 713 386880224131 714 393556107073 715 400304809330 716 407115997895 717 414025706565 718 421083722780 719 428307536820 720 435662985239 721 443098847990 722 450602724804 723 458215110434 724 465990013550 725 473944648166 726 482043405443 727 490232351573 728 498496171297 729 506878657123 730 515440260127 731 524198074198 732 533112137238 733 542126035788 734 551222911588 735 560448645210 736 569870264817 737 579507412347 738 589315129049 739 599232375537 740 609242927423 741 619395052648 742 629759458286 743 640359347583 744 651146237294 745 662052022268 746 673060908817 747 684226793171 748 695623782322 749 707277210729 750 719137000500