0 1 1 0 2 5 3 22 4 57 5 116 6 205 7 330 8 497 9 712 10 981 11 1310 12 1705 13 2172 14 2717 15 3346 16 4065 17 4880 18 5797 19 6822 20 7961 21 9220 22 10605 23 12122 24 13777 25 15576 26 17525 27 19630 28 21897 29 24332 30 26941 31 29730 32 32705 33 35872 34 39237 35 42806 36 46585 37 50580 38 54797 39 59242 40 63921 41 68840 42 74005 43 79422 44 85097 45 91036 46 97245 47 103730 48 110497 49 117552 50 124901 51 132550 52 140505 53 148772 54 157357 55 166266 56 175505 57 185080 58 194997 59 205262 60 215881 61 226860 62 238205 63 249922 64 262017 65 274496 66 287365 67 300630 68 314297 69 328372 70 342861 71 357770 72 373105 73 388872 74 405077 75 421726 76 438825 77 456380 78 474397 79 492882 80 511841 81 531280 82 551205 83 571622 84 592537 85 613956 86 635885 87 658330 88 681297 89 704792 90 728821 91 753390 92 778505 93 804172 94 830397 95 857186 96 884545 97 912480 98 940997 99 970102 100 999801 101 1030100 102 1061005 103 1092522 104 1124657 105 1157416 106 1190805 107 1224830 108 1259497 109 1294812 110 1330781 111 1367410 112 1404705 113 1442672 114 1481317 115 1520646 116 1560665 117 1601380 118 1642797 119 1684922 120 1727761 121 1771320 122 1815605 123 1860622 124 1906377 125 1952876 126 2000125 127 2048130 128 2096897 129 2146432 130 2196741 131 2247830 132 2299705 133 2352372 134 2405837 135 2460106 136 2515185 137 2571080 138 2627797 139 2685342 140 2743721 141 2802940 142 2863005 143 2923922 144 2985697 145 3048336 146 3111845 147 3176230 148 3241497 149 3307652 150 3374701 151 3442650 152 3511505 153 3581272 154 3651957 155 3723566 156 3796105 157 3869580 158 3943997 159 4019362 160 4095681 161 4172960 162 4251205 163 4330422 164 4410617 165 4491796 166 4573965 167 4657130 168 4741297 169 4826472 170 4912661 171 4999870 172 5088105 173 5177372 174 5267677 175 5359026 176 5451425 177 5544880 178 5639397 179 5734982 180 5831641 181 5929380 182 6028205 183 6128122 184 6229137 185 6331256 186 6434485 187 6538830 188 6644297 189 6750892 190 6858621 191 6967490 192 7077505 193 7188672 194 7300997 195 7414486 196 7529145 197 7644980 198 7761997 199 7880202 200 7999601 201 8120200 202 8242005 203 8365022 204 8489257 205 8614716 206 8741405 207 8869330 208 8998497 209 9128912 210 9260581 211 9393510 212 9527705 213 9663172 214 9799917 215 9937946 216 10077265 217 10217880 218 10359797 219 10503022 220 10647561 221 10793420 222 10940605 223 11089122 224 11238977 225 11390176 226 11542725 227 11696630 228 11851897 229 12008532 230 12166541 231 12325930 232 12486705 233 12648872 234 12812437 235 12977406 236 13143785 237 13311580 238 13480797 239 13651442 240 13823521 241 13997040 242 14172005 243 14348422 244 14526297 245 14705636 246 14886445 247 15068730 248 15252497 249 15437752 250 15624501 251 15812750 252 16002505 253 16193772 254 16386557 255 16580866 256 16776705 257 16974080 258 17172997 259 17373462 260 17575481 261 17779060 262 17984205 263 18190922 264 18399217 265 18609096 266 18820565 267 19033630 268 19248297 269 19464572 270 19682461 271 19901970 272 20123105 273 20345872 274 20570277 275 20796326 276 21024025 277 21253380 278 21484397 279 21717082 280 21951441 281 22187480 282 22425205 283 22664622 284 22905737 285 23148556 286 23393085 287 23639330 288 23887297 289 24136992 290 24388421 291 24641590 292 24896505 293 25153172 294 25411597 295 25671786 296 25933745 297 26197480 298 26462997 299 26730302 300 26999401 301 27270300 302 27543005 303 27817522 304 28093857 305 28372016 306 28652005 307 28933830 308 29217497 309 29503012 310 29790381 311 30079610 312 30370705 313 30663672 314 30958517 315 31255246 316 31553865 317 31854380 318 32156797 319 32461122 320 32767361 321 33075520 322 33385605 323 33697622 324 34011577 325 34327476 326 34645325 327 34965130 328 35286897 329 35610632 330 35936341 331 36264030 332 36593705 333 36925372 334 37259037 335 37594706 336 37932385 337 38272080 338 38613797 339 38957542 340 39303321 341 39651140 342 40001005 343 40352922 344 40706897 345 41062936 346 41421045 347 41781230 348 42143497 349 42507852 350 42874301 351 43242850 352 43613505 353 43986272 354 44361157 355 44738166 356 45117305 357 45498580 358 45881997 359 46267562 360 46655281 361 47045160 362 47437205 363 47831422 364 48227817 365 48626396 366 49027165 367 49430130 368 49835297 369 50242672 370 50652261 371 51064070 372 51478105 373 51894372 374 52312877 375 52733626 376 53156625 377 53581880 378 54009397 379 54439182 380 54871241 381 55305580 382 55742205 383 56181122 384 56622337 385 57065856 386 57511685 387 57959830 388 58410297 389 58863092 390 59318221 391 59775690 392 60235505 393 60697672 394 61162197 395 61629086 396 62098345 397 62569980 398 63043997 399 63520402 400 63999201 401 64480400 402 64964005 403 65450022 404 65938457 405 66429316 406 66922605 407 67418330 408 67916497 409 68417112 410 68920181 411 69425710 412 69933705 413 70444172 414 70957117 415 71472546 416 71990465 417 72510880 418 73033797 419 73559222 420 74087161 421 74617620 422 75150605 423 75686122 424 76224177 425 76764776 426 77307925 427 77853630 428 78401897 429 78952732 430 79506141 431 80062130 432 80620705 433 81181872 434 81745637 435 82312006 436 82880985 437 83452580 438 84026797 439 84603642 440 85183121 441 85765240 442 86350005 443 86937422 444 87527497 445 88120236 446 88715645 447 89313730 448 89914497 449 90517952 450 91124101 451 91732950 452 92344505 453 92958772 454 93575757 455 94195466 456 94817905 457 95443080 458 96070997 459 96701662 460 97335081 461 97971260 462 98610205 463 99251922 464 99896417 465 100543696 466 101193765 467 101846630 468 102502297 469 103160772 470 103822061 471 104486170 472 105153105 473 105822872 474 106495477 475 107170926 476 107849225 477 108530380 478 109214397 479 109901282 480 110591041 481 111283680 482 111979205 483 112677622 484 113378937 485 114083156 486 114790285 487 115500330 488 116213297 489 116929192 490 117648021 491 118369790 492 119094505 493 119822172 494 120552797 495 121286386 496 122022945 497 122762480 498 123504997 499 124250502 500 124999001 501 125750500 502 126505005 503 127262522 504 128023057 505 128786616 506 129553205 507 130322830 508 131095497 509 131871212 510 132649981 511 133431810 512 134216705 513 135004672 514 135795717 515 136589846 516 137387065 517 138187380 518 138990797 519 139797322 520 140606961 521 141419720 522 142235605 523 143054622 524 143876777 525 144702076 526 145530525 527 146362130 528 147196897 529 148034832 530 148875941 531 149720230 532 150567705 533 151418372 534 152272237 535 153129306 536 153989585 537 154853080 538 155719797 539 156589742 540 157462921 541 158339340 542 159219005 543 160101922 544 160988097 545 161877536 546 162770245 547 163666230 548 164565497 549 165468052 550 166373901 551 167283050 552 168195505 553 169111272 554 170030357 555 170952766 556 171878505 557 172807580 558 173739997 559 174675762 560 175614881 561 176557360 562 177503205 563 178452422 564 179405017 565 180360996 566 181320365 567 182283130 568 183249297 569 184218872 570 185191861 571 186168270 572 187148105 573 188131372 574 189118077 575 190108226 576 191101825 577 192098880 578 193099397 579 194103382 580 195110841 581 196121780 582 197136205 583 198154122 584 199175537 585 200200456 586 201228885 587 202260830 588 203296297 589 204335292 590 205377821 591 206423890 592 207473505 593 208526672 594 209583397 595 210643686 596 211707545 597 212774980 598 213845997 599 214920602 600 215998801 601 217080600 602 218166005 603 219255022 604 220347657 605 221443916 606 222543805 607 223647330 608 224754497 609 225865312 610 226979781 611 228097910 612 229219705 613 230345172 614 231474317 615 232607146 616 233743665 617 234883880 618 236027797 619 237175422 620 238326761 621 239481820 622 240640605 623 241803122 624 242969377 625 244139376 626 245313125 627 246490630 628 247671897 629 248856932 630 250045741 631 251238330 632 252434705 633 253634872 634 254838837 635 256046606 636 257258185 637 258473580 638 259692797 639 260915842 640 262142721 641 263373440 642 264608005 643 265846422 644 267088697 645 268334836 646 269584845 647 270838730 648 272096497 649 273358152 650 274623701 651 275893150 652 277166505 653 278443772 654 279724957 655 281010066 656 282299105 657 283592080 658 284888997 659 286189862 660 287494681 661 288803460 662 290116205 663 291432922 664 292753617 665 294078296 666 295406965 667 296739630 668 298076297 669 299416972 670 300761661 671 302110370 672 303463105 673 304819872 674 306180677 675 307545526 676 308914425 677 310287380 678 311664397 679 313045482 680 314430641 681 315819880 682 317213205 683 318610622 684 320012137 685 321417756 686 322827485 687 324241330 688 325659297 689 327081392 690 328507621 691 329937990 692 331372505 693 332811172 694 334253997 695 335700986 696 337152145 697 338607480 698 340066997 699 341530702 700 342998601 701 344470700 702 345947005 703 347427522 704 348912257 705 350401216 706 351894405 707 353391830 708 354893497 709 356399412 710 357909581 711 359424010 712 360942705 713 362465672 714 363992917 715 365524446 716 367060265 717 368600380 718 370144797 719 371693522 720 373246561 721 374803920 722 376365605 723 377931622 724 379501977 725 381076676 726 382655725 727 384239130 728 385826897 729 387419032 730 389015541 731 390616430 732 392221705 733 393831372 734 395445437 735 397063906 736 398686785 737 400314080 738 401945797 739 403581942 740 405222521 741 406867540 742 408517005 743 410170922 744 411829297 745 413492136 746 415159445 747 416831230 748 418507497 749 420188252 750 421873501 751 423563250 752 425257505 753 426956272 754 428659557 755 430367366 756 432079705 757 433796580 758 435517997 759 437243962 760 438974481 761 440709560 762 442449205 763 444193422 764 445942217 765 447695596 766 449453565 767 451216130 768 452983297 769 454755072 770 456531461 771 458312470 772 460098105 773 461888372 774 463683277 775 465482826 776 467287025 777 469095880 778 470909397 779 472727582 780 474550441