1 -2 2 7 3 33 4 82 5 160 6 273 7 427 8 628 9 882 10 1195 11 1573 12 2022 13 2548 14 3157 15 3855 16 4648 17 5542 18 6543 19 7657 20 8890 21 10248 22 11737 23 13363 24 15132 25 17050 26 19123 27 21357 28 23758 29 26332 30 29085 31 32023 32 35152 33 38478 34 42007 35 45745 36 49698 37 53872 38 58273 39 62907 40 67780 41 72898 42 78267 43 83893 44 89782 45 95940 46 102373 47 109087 48 116088 49 123382 50 130975 51 138873 52 147082 53 155608 54 164457 55 173635 56 183148 57 193002 58 203203 59 213757 60 224670 61 235948 62 247597 63 259623 64 272032 65 284830 66 298023 67 311617 68 325618 69 340032 70 354865 71 370123 72 385812 73 401938 74 418507 75 435525 76 452998 77 470932 78 489333 79 508207 80 527560 81 547398 82 567727 83 588553 84 609882 85 631720 86 654073 87 676947 88 700348 89 724282 90 748755 91 773773 92 799342 93 825468 94 852157 95 879415 96 907248 97 935662 98 964663 99 994257 100 1024450 101 1055248 102 1086657 103 1118683 104 1151332 105 1184610 106 1218523 107 1253077 108 1288278 109 1324132 110 1360645 111 1397823 112 1435672 113 1474198 114 1513407 115 1553305 116 1593898 117 1635192 118 1677193 119 1719907 120 1763340 121 1807498 122 1852387 123 1898013 124 1944382 125 1991500 126 2039373 127 2088007 128 2137408 129 2187582 130 2238535 131 2290273 132 2342802 133 2396128 134 2450257 135 2505195 136 2560948 137 2617522 138 2674923 139 2733157 140 2792230 141 2852148 142 2912917 143 2974543 144 3037032 145 3100390 146 3164623 147 3229737 148 3295738 149 3362632 150 3430425 151 3499123 152 3568732 153 3639258 154 3710707 155 3783085 156 3856398 157 3930652 158 4005853 159 4082007 160 4159120 161 4237198 162 4316247 163 4396273 164 4477282 165 4559280 166 4642273 167 4726267 168 4811268 169 4897282 170 4984315 171 5072373 172 5161462 173 5251588 174 5342757 175 5434975 176 5528248 177 5622582 178 5717983 179 5814457 180 5912010 181 6010648 182 6110377 183 6211203 184 6313132 185 6416170 186 6520323 187 6625597 188 6731998 189 6839532 190 6948205 191 7058023 192 7168992 193 7281118 194 7394407 195 7508865 196 7624498 197 7741312 198 7859313 199 7978507 200 8098900 201 8220498 202 8343307 203 8467333 204 8592582 205 8719060 206 8846773 207 8975727 208 9105928 209 9237382 210 9370095 211 9504073 212 9639322 213 9775848 214 9913657 215 10052755 216 10193148 217 10334842 218 10477843 219 10622157 220 10767790 221 10914748 222 11063037 223 11212663 224 11363632 225 11515950 226 11669623 227 11824657 228 11981058 229 12138832 230 12297985 231 12458523 232 12620452 233 12783778 234 12948507 235 13114645 236 13282198 237 13451172 238 13621573 239 13793407 240 13966680 241 14141398 242 14317567 243 14495193 244 14674282 245 14854840 246 15036873 247 15220387 248 15405388 249 15591882 250 15779875 251 15969373 252 16160382 253 16352908 254 16546957 255 16742535 256 16939648 257 17138302 258 17338503 259 17540257 260 17743570 261 17948448 262 18154897 263 18362923 264 18572532 265 18783730 266 18996523 267 19210917 268 19426918 269 19644532 270 19863765 271 20084623 272 20307112 273 20531238 274 20757007 275 20984425 276 21213498 277 21444232 278 21676633 279 21910707 280 22146460 281 22383898 282 22623027 283 22863853 284 23106382 285 23350620 286 23596573 287 23844247 288 24093648 289 24344782 290 24597655 291 24852273 292 25108642 293 25366768 294 25626657 295 25888315 296 26151748 297 26416962 298 26683963 299 26952757 300 27223350 301 27495748 302 27769957 303 28045983 304 28323832 305 28603510 306 28885023 307 29168377 308 29453578 309 29740632 310 30029545 311 30320323 312 30612972 313 30907498 314 31203907 315 31502205 316 31802398 317 32104492 318 32408493 319 32714407 320 33022240 321 33331998 322 33643687 323 33957313 324 34272882 325 34590400 326 34909873 327 35231307 328 35554708 329 35880082 330 36207435 331 36536773 332 36868102 333 37201428 334 37536757 335 37874095 336 38213448 337 38554822 338 38898223 339 39243657 340 39591130 341 39940648 342 40292217 343 40645843 344 41001532 345 41359290 346 41719123 347 42081037 348 42445038 349 42811132 350 43179325 351 43549623 352 43922032 353 44296558 354 44673207 355 45051985 356 45432898 357 45815952 358 46201153 359 46588507 360 46978020 361 47369698 362 47763547 363 48159573 364 48557782 365 48958180 366 49360773 367 49765567 368 50172568 369 50581782 370 50993215 371 51406873 372 51822762 373 52240888 374 52661257 375 53083875 376 53508748 377 53935882 378 54365283 379 54796957 380 55230910 381 55667148 382 56105677 383 56546503 384 56989632 385 57435070 386 57882823 387 58332897 388 58785298 389 59240032 390 59697105 391 60156523 392 60618292 393 61082418 394 61548907 395 62017765 396 62488998 397 62962612 398 63438613 399 63917007 400 64397800 401 64880998 402 65366607 403 65854633 404 66345082 405 66837960 406 67333273 407 67831027 408 68331228 409 68833882 410 69338995 411 69846573 412 70356622 413 70869148 414 71384157 415 71901655 416 72421648 417 72944142 418 73469143 419 73996657 420 74526690 421 75059248 422 75594337 423 76131963 424 76672132 425 77214850 426 77760123 427 78307957 428 78858358 429 79411332 430 79966885 431 80525023 432 81085752 433 81649078 434 82215007 435 82783545 436 83354698 437 83928472 438 84504873 439 85083907 440 85665580 441 86249898 442 86836867 443 87426493 444 88018782 445 88613740 446 89211373 447 89811687 448 90414688 449 91020382 450 91628775 451 92239873 452 92853682 453 93470208 454 94089457 455 94711435 456 95336148 457 95963602 458 96593803 459 97226757 460 97862470 461 98500948 462 99142197 463 99786223 464 100433032 465 101082630 466 101735023 467 102390217 468 103048218 469 103709032 470 104372665 471 105039123 472 105708412 473 106380538 474 107055507 475 107733325 476 108413998 477 109097532 478 109783933 479 110473207 480 111165360 481 111860398 482 112558327 483 113259153 484 113962882 485 114669520 486 115379073 487 116091547 488 116806948 489 117525282 490 118246555 491 118970773 492 119697942 493 120428068 494 121161157 495 121897215 496 122636248 497 123378262 498 124123263 499 124871257 500 125622250 501 126376248 502 127133257 503 127893283 504 128656332 505 129422410 506 130191523 507 130963677 508 131738878 509 132517132 510 133298445 511 134082823 512 134870272 513 135660798 514 136454407 515 137251105 516 138050898 517 138853792 518 139659793 519 140468907 520 141281140 521 142096498 522 142914987 523 143736613 524 144561382 525 145389300 526 146220373 527 147054607 528 147892008 529 148732582 530 149576335 531 150423273 532 151273402 533 152126728 534 152983257 535 153842995 536 154705948 537 155572122 538 156441523 539 157314157 540 158190030 541 159069148 542 159951517 543 160837143 544 161726032 545 162618190 546 163513623 547 164412337 548 165314338 549 166219632 550 167128225 551 168040123 552 168955332 553 169873858 554 170795707 555 171720885 556 172649398 557 173581252 558 174516453 559 175455007 560 176396920 561 177342198 562 178290847 563 179242873 564 180198282 565 181157080 566 182119273 567 183084867 568 184053868 569 185026282 570 186002115 571 186981373 572 187964062 573 188950188 574 189939757 575 190932775 576 191929248 577 192929182 578 193932583 579 194939457 580 195949810 581 196963648 582 197980977 583 199001803 584 200026132 585 201053970 586 202085323 587 203120197 588 204158598 589 205200532 590 206246005 591 207295023 592 208347592 593 209403718 594 210463407 595 211526665 596 212593498 597 213663912 598 214737913 599 215815507 600 216896700 601 217981498 602 219069907 603 220161933 604 221257582 605 222356860 606 223459773 607 224566327 608 225676528 609 226790382 610 227907895 611 229029073 612 230153922 613 231282448 614 232414657 615 233550555 616 234690148 617 235833442 618 236980443 619 238131157 620 239285590 621 240443748 622 241605637 623 242771263 624 243940632 625 245113750 626 246290623 627 247471257 628 248655658 629 249843832 630 251035785 631 252231523 632 253431052 633 254634378 634 255841507 635 257052445 636 258267198 637 259485772 638 260708173 639 261934407 640 263164480 641 264398398 642 265636167 643 266877793 644 268123282 645 269372640 646 270625873 647 271882987 648 273143988 649 274408882 650 275677675 651 276950373 652 278226982 653 279507508 654 280791957 655 282080335 656 283372648 657 284668902 658 285969103 659 287273257 660 288581370 661 289893448 662 291209497 663 292529523 664 293853532 665 295181530 666 296513523 667 297849517 668 299189518 669 300533532 670 301881565 671 303233623 672 304589712 673 305949838 674 307314007 675 308682225 676 310054498 677 311430832 678 312811233 679 314195707 680 315584260 681 316976898 682 318373627 683 319774453 684 321179382 685 322588420 686 324001573 687 325418847 688 326840248 689 328265782 690 329695455 691 331129273 692 332567242 693 334009368 694 335455657 695 336906115 696 338360748 697 339819562 698 341282563 699 342749757 700 344221150 701 345696748 702 347176557 703 348660583 704 350148832 705 351641310 706 353138023 707 354638977 708 356144178 709 357653632 710 359167345 711 360685323 712 362207572 713 363734098 714 365264907 715 366800005 716 368339398 717 369883092 718 371431093 719 372983407 720 374540040 721 376100998 722 377666287 723 379235913 724 380809882 725 382388200 726 383970873 727 385557907 728 387149308 729 388745082 730 390345235 731 391949773 732 393558702 733 395172028 734 396789757 735 398411895 736 400038448 737 401669422 738 403304823 739 404944657 740 406588930 741 408237648 742 409890817 743 411548443 744 413210532 745 414877090 746 416548123 747 418223637 748 419903638 749 421588132 750 423277125 751 424970623 752 426668632 753 428371158 754 430078207 755 431789785 756 433505898 757 435226552 758 436951753 759 438681507 760 440415820 761 442154698 762 443898147 763 445646173 764 447398782 765 449155980 766 450917773 767 452684167 768 454455168 769 456230782 770 458011015 771 459795873 772 461585362 773 463379488 774 465178257 775 466981675 776 468789748 777 470602482 778 472419883 779 474241957 780 476068710 781 477900148 782 479736277 783 481577103 784 483422632 785 485272870 786 487127823 787 488987497 788 490851898 789 492721032 790 494594905 791 496473523 792 498356892 793 500245018 794 502137907 795 504035565 796 505937998 797 507845212 798 509757213 799 511674007 800 513595600 801 515521998 802 517453207 803 519389233 804 521330082 805 523275760 806 525226273 807 527181627 808 529141828 809 531106882 810 533076795 811 535051573 812 537031222 813 539015748 814 541005157 815 542999455 816 544998648 817 547002742 818 549011743 819 551025657 820 553044490 821 555068248 822 557096937 823 559130563 824 561169132 825 563212650 826 565261123 827 567314557 828 569372958 829 571436332 830 573504685 831 575578023 832 577656352 833 579739678 834 581828007 835 583921345 836 586019698 837 588123072 838 590231473 839 592344907 840 594463380 841 596586898 842 598715467 843 600849093 844 602987782 845 605131540 846 607280373 847 609434287 848 611593288 849 613757382 850 615926575 851 618100873 852 620280282 853 622464808 854 624654457 855 626849235 856 629049148 857 631254202 858 633464403 859 635679757 860 637900270 861 640125948 862 642356797 863 644592823 864 646834032 865 649080430 866 651332023 867 653588817 868 655850818 869 658118032 870 660390465 871 662668123 872 664951012 873 667239138 874 669532507 875 671831125 876 674134998 877 676444132 878 678758533 879 681078207 880 683403160 881 685733398 882 688068927 883 690409753 884 692755882 885 695107320 886 697464073 887 699826147 888 702193548 889 704566282 890 706944355 891 709327773 892 711716542 893 714110668 894 716510157 895 718915015 896 721325248 897 723740862 898 726161863 899 728588257 900 731020050 901 733457248 902 735899857 903 738347883 904 740801332 905 743260210 906 745724523 907 748194277 908 750669478 909 753150132 910 755636245 911 758127823 912 760624872 913 763127398 914 765635407 915 768148905 916 770667898 917 773192392 918 775722393 919 778257907 920 780798940 921 783345498 922 785897587 923 788455213 924 791018382 925 793587100 926 796161373 927 798741207 928 801326608 929 803917582 930 806514135 931 809116273 932 811724002 933 814337328 934 816956257 935 819580795 936 822210948 937 824846722 938 827488123 939 830135157 940 832787830 941 835446148 942 838110117 943 840779743 944 843455032 945 846135990 946 848822623 947 851514937 948 854212938 949 856916632 950 859626025 951 862341123 952 865061932 953 867788458 954 870520707 955 873258685 956 876002398 957 878751852 958 881507053 959 884268007 960 887034720 961 889807198 962 892585447 963 895369473 964 898159282 965 900954880 966 903756273 967 906563467 968 909376468 969 912195282 970 915019915 971 917850373 972 920686662 973 923528788 974 926376757 975 929230575 976 932090248 977 934955782 978 937827183 979 940704457 980 943587610 981 946476648 982 949371577 983 952272403 984 955179132 985 958091770 986 961010323 987 963934797 988 966865198 989 969801532 990 972743805 991 975692023 992 978646192 993 981606318 994 984572407 995 987544465 996 990522498 997 993506512 998 996496513 999 999492507 1000 1002494500