0 1 1 16 2 104 3 344 4 792 5 1528 6 2632 7 4152 8 6200 9 8792 10 12072 11 16024 12 20824 13 26424 14 33032 15 40568 16 49272 17 59032 18 70120 19 82392 20 96152 21 111224 22 127944 23 146104 24 166072 25 187608 26 211112 27 236312 28 263640 29 292792 30 324232 31 357624 32 393464 33 431384 34 471912 35 514648 36 560152 37 607992 38 658760 39 711992 40 768312 41 827224 42 889384 43 954264 44 1022552 45 1093688 46 1168392 47 1246072 48 1327480 49 1411992 50 1500392 51 1592024 52 1687704 53 1786744 54 1889992 55 1996728 56 2107832 57 2222552 58 2341800 59 2464792 60 2592472 61 2724024 62 2860424 63 3000824 64 3146232 65 3295768 66 3450472 67 3609432 68 3773720 69 3942392 70 4116552 71 4295224 72 4479544 73 4668504 74 4863272 75 5062808 76 5268312 77 5478712 78 5695240 79 5916792 80 6144632 81 6377624 82 6617064 83 6861784 84 7113112 85 7369848 86 7633352 87 7902392 88 8178360 89 8459992 90 8748712 91 9043224 92 9344984 93 9652664 94 9967752 95 10288888 96 10617592 97 10952472 98 11295080 99 11643992 100 12000792 101 12364024 102 12735304 103 13113144 104 13499192 105 13891928 106 14293032 107 14700952 108 15117400 109 15540792 110 15972872 111 16412024 112 16860024 113 17315224 114 17779432 115 18250968 116 18731672 117 19219832 118 19717320 119 20222392 120 20736952 121 21259224 122 21791144 123 22330904 124 22880472 125 23438008 126 24005512 127 24581112 128 25166840 129 25760792 130 26365032 131 26977624 132 27600664 133 28232184 134 28874312 135 29525048 136 30186552 137 30856792 138 31537960 139 32227992 140 32929112 141 33639224 142 34360584 143 35091064 144 35832952 145 36584088 146 37346792 147 38118872 148 38902680 149 39695992 150 40501192 151 41316024 152 42142904 153 42979544 154 43828392 155 44687128 156 45558232 157 46439352 158 47333000 159 48236792 160 49153272 161 50080024 162 51019624 163 51969624 164 52932632 165 53906168 166 54892872 167 55890232 168 56900920 169 57922392 170 58957352 171 60003224 172 61062744 173 62133304 174 63217672 175 64313208 176 65422712 177 66543512 178 67678440 179 68824792 180 69985432 181 71157624 182 72344264 183 73542584 184 74755512 185 75980248 186 77219752 187 78471192 188 79737560 189 81015992 190 82309512 191 83615224 192 84936184 193 86269464 194 87618152 195 88979288 196 90355992 197 91745272 198 93150280 199 94567992 200 96001592 201 97448024 202 98910504 203 100385944 204 101877592 205 103382328 206 104903432 207 106437752 208 107988600 209 109552792 210 111133672 211 112728024 212 114339224 213 115964024 214 117605832 215 119261368 216 120934072 217 122620632 218 124324520 219 126042392 220 127777752 221 129527224 222 131294344 223 133075704 224 134874872 225 136688408 226 138519912 227 140365912 228 142230040 229 144108792 230 146005832 231 147917624 232 149847864 233 151792984 234 153756712 235 155735448 236 157732952 237 159745592 238 161777160 239 163823992 240 165889912 241 167971224 242 170071784 243 172187864 244 174323352 245 176474488 246 178645192 247 180831672 248 183037880 249 185259992 250 187501992 251 189760024 252 192038104 253 194332344 254 196646792 255 198977528 256 201328632 257 203696152 258 206084200 259 208488792 260 210914072 261 213356024 262 215818824 263 218298424 264 220799032 265 223316568 266 225855272 267 228411032 268 230988120 269 233582392 270 236198152 271 238831224 272 241485944 273 244158104 274 246852072 275 249563608 276 252297112 277 255048312 278 257821640 279 260612792 280 263426232 281 266257624 282 269111464 283 271983384 284 274877912 285 277790648 286 280726152 287 283679992 288 286656760 289 289651992 290 292670312 291 295707224 292 298767384 293 301846264 294 304948552 295 308069688 296 311214392 297 314378072 298 317565480 299 320771992 300 324002392 301 327252024 302 330525704 303 333818744 304 337135992 305 340472728 306 343833832 307 347214552 308 350619800 309 354044792 310 357494472 311 360964024 312 364458424 313 367972824 314 371512232 315 375071768 316 378656472 317 382261432 318 385891720 319 389542392 320 393218552 321 396915224 322 400637544 323 404380504 324 408149272 325 411938808 326 415754312 327 419590712 328 423453240 329 427336792 330 431246632 331 435177624 332 439135064 333 443113784 334 447119112 335 451145848 336 455199352 337 459274392 338 463376360 339 467499992 340 471650712 341 475823224 342 480022984 343 484244664 344 488493752 345 492764888 346 497063592 347 501384472 348 505733080 349 510103992 350 514502792 351 518924024 352 523373304 353 527845144 354 532345192 355 536867928 356 541419032 357 545992952 358 550595400 359 555220792 360 559874872 361 564552024 362 569258024 363 573987224 364 578745432 365 583526968 366 588337672 367 593171832 368 598035320 369 602922392 370 607838952 371 612779224 372 617749144 373 622742904 374 627766472 375 632814008 376 637891512 377 642993112 378 648124840 379 653280792 380 658467032 381 663677624 382 668918664 383 674184184 384 679480312 385 684801048 386 690152552 387 695528792 388 700935960 389 706367992 390 711831112 391 717319224 392 722838584 393 728383064 394 733958952 395 739560088 396 745192792 397 750850872 398 756540680 399 762255992 400 768003192 401 773776024 402 779580904 403 785411544 404 791274392 405 797163128 406 803084232 407 809031352 408 815011000 409 821016792 410 827055272 411 833120024 412 839217624 413 845341624 414 851498632 415 857682168 416 863898872 417 870142232 418 876418920 419 882722392 420 889059352 421 895423224 422 901820744 423 908245304 424 914703672 425 921189208 426 927708712 427 934255512 428 940836440 429 947444792 430 954087432 431 960757624 432 967462264 433 974194584 434 980961512 435 987756248 436 994585752 437 1001443192 438 1008335560 439 1015255992 440 1022211512 441 1029195224 442 1036214184 443 1043261464 444 1050344152 445 1057455288 446 1064601992 447 1071777272 448 1078988280 449 1086227992 450 1093503592 451 1100808024 452 1108148504 453 1115517944 454 1122923592 455 1130358328 456 1137829432 457 1145329752 458 1152866600 459 1160432792 460 1168035672 461 1175668024 462 1183337224 463 1191036024 464 1198771832 465 1206537368 466 1214340072 467 1222172632 468 1230042520 469 1237942392 470 1245879752 471 1253847224 472 1261852344 473 1269887704 474 1277960872 475 1286064408 476 1294205912 477 1302377912 478 1310588040 479 1318828792 480 1327107832 481 1335417624 482 1343765864 483 1352144984 484 1360562712 485 1369011448 486 1377498952 487 1386017592 488 1394575160 489 1403163992 490 1411791912 491 1420451224 492 1429149784 493 1437879864 494 1446649352 495 1455450488 496 1464291192 497 1473163672 498 1482075880 499 1491019992 500 1500003992 501 1509020024 502 1518076104 503 1527164344 504 1536292792 505 1545453528 506 1554654632 507 1563888152 508 1573162200 509 1582468792 510 1591816072 511 1601196024 512 1610616824 513 1620070424 514 1629565032 515 1639092568 516 1648661272 517 1658263032 518 1667906120 519 1677582392 520 1687300152 521 1697051224 522 1706843944 523 1716670104 524 1726538072 525 1736439608 526 1746383112 527 1756360312 528 1766379640 529 1776432792 530 1786528232 531 1796657624 532 1806829464 533 1817035384 534 1827283912 535 1837566648 536 1847892152 537 1858251992 538 1868654760 539 1879091992 540 1889572312 541 1900087224 542 1910645384 543 1921238264 544 1931874552 545 1942545688 546 1953260392 547 1964010072 548 1974803480 549 1985631992 550 1996504392 551 2007412024 552 2018363704 553 2029350744 554 2040381992 555 2051448728 556 2062559832 557 2073706552 558 2084897800 559 2096124792 560 2107396472 561 2118704024 562 2130056424 563 2141444824 564 2152878232 565 2164347768 566 2175862472 567 2187413432 568 2199009720 569 2210642392 570 2222320552 571 2234035224 572 2245795544 573 2257592504 574 2269435272 575 2281314808 576 2293240312 577 2305202712 578 2317211240 579 2329256792 580 2341348632 581 2353477624 582 2365653064 583 2377865784 584 2390125112 585 2402421848 586 2414765352 587 2427146392 588 2439574360 589 2452039992 590 2464552712 591 2477103224 592 2489700984 593 2502336664 594 2515019752 595 2527740888 596 2540509592 597 2553316472 598 2566171080 599 2579063992 600 2592004792 601 2604984024 602 2618011304 603 2631077144 604 2644191192 605 2657343928 606 2670545032 607 2683784952 608 2697073400 609 2710400792 610 2723776872 611 2737192024 612 2750656024 613 2764159224 614 2777711432 615 2791302968 616 2804943672 617 2818623832 618 2832353320 619 2846122392 620 2859940952 621 2873799224 622 2887707144 623 2901654904 624 2915652472 625 2929690008 626 2943777512 627 2957905112 628 2972082840 629 2986300792 630 3000569032 631 3014877624 632 3029236664 633 3043636184 634 3058086312 635 3072577048 636 3087118552 637 3101700792 638 3116333960 639 3131007992 640 3145733112 641 3160499224 642 3175316584 643 3190175064 644 3205084952 645 3220036088 646 3235038792 647 3250082872 648 3265178680 649 3280315992 650 3295505192 651 3310736024 652 3326018904 653 3341343544 654 3356720392 655 3372139128 656 3387610232 657 3403123352 658 3418689000 659 3434296792 660 3449957272 661 3465660024 662 3481415624 663 3497213624 664 3513064632 665 3528958168 666 3544904872 667 3560894232 668 3576936920 669 3593022392 670 3609161352 671 3625343224 672 3641578744 673 3657857304 674 3674189672 675 3690565208 676 3706994712 677 3723467512 678 3739994440 679 3756564792 680 3773189432 681 3789857624 682 3806580264 683 3823346584 684 3840167512 685 3857032248 686 3873951752 687 3890915192 688 3907933560 689 3924995992 690 3942113512 691 3959275224 692 3976492184 693 3993753464 694 4011070152 695 4028431288 696 4045847992 697 4063309272 698 4080826280 699 4098387992 700 4116005592 701 4133668024 702 4151386504 703 4169149944 704 4186969592 705 4204834328 706 4222755432 707 4240721752 708 4258744600 709 4276812792 710 4294937672 711 4313108024 712 4331335224 713 4349608024 714 4367937832 715 4386313368 716 4404746072 717 4423224632 718 4441760520 719 4460342392 720 4478981752 721 4497667224 722 4516410344 723 4535199704 724 4554046872 725 4572940408 726 4591891912 727 4610889912 728 4629946040 729 4649048792 730 4668209832 731 4687417624 732 4706683864 733 4725996984 734 4745368712 735 4764787448 736 4784264952 737 4803789592 738 4823373160 739 4843003992 740 4862693912 741 4882431224 742 4902227784 743 4922071864 744 4941975352 745 4961926488 746 4981937192 747 5001995672 748 5022113880 749 5042279992 750 5062505992 751 5082780024 752 5103114104 753 5123496344 754 5143938792 755 5164429528 756 5184980632 757 5205580152 758 5226240200 759 5246948792 760 5267718072 761 5288536024 762 5309414824 763 5330342424 764 5351331032 765 5372368568 766 5393467272 767 5414615032 768 5435824120 769 5457082392 770 5478402152 771 5499771224 772 5521201944 773 5542682104 774 5564224072 775 5585815608 776 5607469112 777 5629172312 778 5650937640 779 5672752792 780 5694630232 781 5716557624 782 5738547464 783 5760587384 784 5782689912 785 5804842648 786 5827058152 787 5849323992 788 5871652760 789 5894031992 790 5916474312 791 5938967224 792 5961523384 793 5984130264 794 6006800552 795 6029521688 796 6052306392 797 6075142072 798 6098041480 799 6120991992 800 6144006392 801 6167072024 802 6190201704 803 6213382744 804 6236627992 805 6259924728 806 6283285832 807 6306698552 808 6330175800 809 6353704792 810 6377298472 811 6400944024 812 6424654424 813 6448416824 814 6472244232 815 6496123768 816 6520068472 817 6544065432 818 6568127720 819 6592242392 820 6616422552 821 6640655224 822 6664953544 823 6689304504 824 6713721272 825 6738190808 826 6762726312 827 6787314712 828 6811969240 829 6836676792 830 6861450632 831 6886277624 832 6911171064 833 6936117784 834 6961131112 835 6986197848 836 7011331352 837 7036518392 838 7061772360 839 7087079992 840 7112454712 841 7137883224 842 7163378984 843 7188928664 844 7214545752 845 7240216888 846 7265955592 847 7291748472 848 7317609080 849 7343523992 850 7369506792 851 7395544024 852 7421649304 853 7447809144 854 7474037192 855 7500319928 856 7526671032 857 7553076952 858 7579551400 859 7606080792 860 7632678872 861 7659332024 862 7686054024 863 7712831224 864 7739677432 865 7766578968 866 7793549672 867 7820575832 868 7847671320 869 7874822392 870 7902042952 871 7929319224 872 7956665144 873 7984066904 874 8011538472 875 8039066008 876 8066663512 877 8094317112 878 8122040840 879 8149820792 880 8177671032 881 8205577624 882 8233554664 883 8261588184 884 8289692312 885 8317853048 886 8346084552 887 8374372792 888 8402731960 889 8431147992 890 8459635112 891 8488179224 892 8516794584 893 8545467064 894 8574210952 895 8603012088 896 8631884792 897 8660814872 898 8689816680 899 8718875992 900 8748007192 901 8777196024 902 8806456904 903 8835775544 904 8865166392 905 8894615128 906 8924136232 907 8953715352 908 8983367000 909 9013076792 910 9042859272 911 9072700024 912 9102613624 913 9132585624 914 9162630632 915 9192734168 916 9222910872 917 9253146232 918 9283454920 919 9313822392 920 9344263352 921 9374763224 922 9405336744 923 9435969304 924 9466675672 925 9497441208 926 9528280712 927 9559179512 928 9590152440 929 9621184792 930 9652291432 931 9683457624 932 9714698264 933 9745998584 934 9777373512 935 9808808248 936 9840317752 937 9871887192 938 9903531560 939 9935235992 940 9967015512 941 9998855224 942 10030770184 943 10062745464 944 10094796152 945 10126907288 946 10159093992 947 10191341272 948 10223664280 949 10256047992 950 10288507592 951 10321028024 952 10353624504 953 10386281944 954 10419015592 955 10451810328 956 10484681432 957 10517613752 958 10550622600 959 10583692792 960 10616839672 961 10650048024 962 10683333224 963 10716680024 964 10750103832 965 10783589368 966 10817152072 967 10850776632 968 10884478520 969 10918242392 970 10952083752 971 10985987224 972 11019968344 973 11054011704 974 11088132872 975 11122316408 976 11156577912 977 11190901912 978 11225304040 979 11259768792 980 11294311832 981 11328917624 982 11363601864 983 11398348984 984 11433174712 985 11468063448 986 11503030952 987 11538061592 988 11573171160 989 11608343992 990 11643595912 991 11678911224 992 11714305784 993 11749763864 994 11785301352 995 11820902488 996 11856583192 997 11892327672 998 11928151880 999 11964039992 1000 12000007992