1 1 2 144 3 112 4 340 5 696 6 1468 7 2528 8 4388 9 6760 10 10444 11 14928 12 21364 13 28952 14 39260 15 51136 16 66628 17 84168 18 106348 19 131120 20 161684 21 195448 22 236284 23 280992 24 334180 25 391976 26 459788 27 533008 28 617908 29 709080 30 813724 31 925568 32 1052804 33 1188232 34 1341100 35 1503216 36 1684948 37 1877048 38 2091068 39 2316640 40 2566564 41 2829288 42 3118924 43 3422672 44 3756020 45 4104856 46 4486108 47 4884288 48 5317828 49 5769800 50 6260204 51 6770608 52 7322644 53 7896312 54 8514940 55 9156896 56 9847268 57 10562728 58 11330188 59 12124560 60 12974644 61 13853528 62 14791964 63 15761152 64 16793860 65 17859336 66 18992428 67 20160368 68 21400148 69 22676920 70 24029884 71 25422048 72 26894884 73 28409192 74 30008780 75 31652176 76 33385588 77 35165208 78 37039708 79 38962880 80 40985924 81 43060168 82 45239404 83 47472432 84 49815700 85 52215416 86 54730748 87 57305248 88 60000868 89 62758440 90 65642764 91 68591888 92 71673524 93 74822872 94 78110620 95 81469056 96 84971908 97 88548488 98 92275628 99 96079600 100 100040404 101 104081208 102 108285244 103 112572512 104 117029540 105 121573096 106 126293068 107 131102928 108 136095988 109 141182360 110 146458844 111 151832128 112 157402564 113 163073352 114 168948460 115 174927536 116 181118228 117 187416568 118 193933948 119 200562720 120 207418084 121 214388648 122 221593484 123 228917392 124 236483380 125 244172376 126 252111388 127 260177408 128 268501508 129 276956680 130 285678124 131 294534768 132 303666004 133 312936632 134 322490300 135 332187616 136 342176548 137 352313448 138 362750668 139 373340240 140 384238964 141 395294488 142 406668124 143 418203072 144 430065220 145 442093256 146 454457708 147 466992688 148 479873428 149 492929400 150 506340604 151 519931808 152 533887844 153 548028712 154 562544140 155 577249296 156 592338868 157 607623128 158 623301788 159 639180160 160 655463044 161 671950728 162 688853164 163 705965552 164 723503060 165 741255736 166 759444028 167 777852768 168 796707748 169 815788520 170 835326284 171 855095248 172 875332084 173 895805592 174 916757980 175 937952576 176 959637188 177 981569608 178 1004003308 179 1026690480 180 1049890324 181 1073349368 182 1097332604 183 1121580832 184 1146364900 185 1171419816 186 1197022348 187 1222901648 188 1249340468 189 1276062040 190 1303355164 191 1330937088 192 1359102724 193 1387563272 194 1416619820 195 1445977456 196 1475943508 197 1506216888 198 1537111228 199 1568319200 200 1600160804 201 1632322408 202 1665130444 203 1698264912 204 1732058740 205 1766185496 206 1800984668 207 1836123328 208 1871947588 209 1908117960 210 1944987244 211 1982209328 212 2020143764 213 2058437752 214 2097457660 215 2136843936 216 2176969828 217 2217468968 218 2258721548 219 2300354320 220 2342754484 221 2385541848 222 2429110684 223 2473073792 224 2517832580 225 2562992776 226 2608962988 227 2655341808 228 2702545108 229 2750164280 230 2798622524 231 2847503968 232 2897239204 233 2947405032 234 2998439500 235 3049912016 236 3102268148 237 3155069848 238 3208770268 239 3262923840 240 3317991364 241 3373519688 242 3429977324 243 3486903472 244 3544774420 245 3603121656 246 3662429308 247 3722221088 248 3782989028 249 3844249000 250 3906501004 251 3969253008 252 4033013044 253 4097281112 254 4162573340 255 4228381696 256 4295230468 257 4362603528 258 4431033388 259 4499995760 260 4570031444 261 4640607928 262 4712274364 263 4784489952 264 4857812260 265 4931692136 266 5006695628 267 5082265168 268 5158975348 269 5236260120 270 5314702684 271 5393728448 272 5473929284 273 5554721992 274 5636707180 275 5719292976 276 5803088788 277 5887494008 278 5973126908 279 6059378080 280 6146874724 281 6234998568 282 6324385804 283 6414409232 284 6505714100 285 6597664216 286 6690913948 287 6784818048 288 6880040068 289 6975925640 290 7073147564 291 7171042288 292 7270291924 293 7370223672 294 7471529020 295 7573525856 296 7676915108 297 7781005288 298 7886506828 299 7992718800 300 8100361204 301 8208723608 302 8318535644 303 8429077312 304 8541087940 305 8653837896 306 8768076268 307 8883063728 308 8999559188 309 9116813560 310 9235595644 311 9355146528 312 9476244964 313 9598122152 314 9721566860 315 9845800336 316 9971621428 317 10098241368 318 10226469148 319 10355505920 320 10486170884 321 10617655048 322 10750787884 323 10884750192 324 11020381780 325 11156853176 326 11295014588 327 11434026208 328 11574748708 329 11716331880 330 11859646924 331 12003833168 332 12149772404 333 12296593432 334 12445188700 335 12594676416 336 12745959748 337 12898146248 338 13052149868 339 13207067440 340 13363823764 341 13521504888 342 13681046524 343 13841523872 344 14003883620 345 14167190056 346 14332400908 347 14498569488 348 14666664628 349 14835728600 350 15006741404 351 15178734208 352 15352698244 353 15527653512 354 15704602540 355 15882554096 356 16062522068 357 16243503928 358 16426524988 359 16610571360 360 16796679844 361 16983825128 362 17173055564 363 17363334352 364 17555721460 365 17749168536 366 17944747228 367 18141397568 368 18340202948 369 18540091720 370 18742159084 371 18945321648 372 19150686484 373 19357158392 374 19565856380 375 19775673376 376 19987740388 377 20200938408 378 20416410508 379 20633025680 380 20851939124 381 21072007768 382 21294399004 383 21517957632 384 21743863300 385 21970948616 386 22200405548 387 22431054448 388 22664099668 389 22898349240 390 23135019964 391 23372907488 392 23613241124 393 23854804072 394 24098838220 395 24344114256 396 24591886708 397 24840913688 398 25092462428 399 25345278400 400 25600641604 401 25857284808 402 26116500844 403 26377009712 404 26640117140 405 26904530296 406 27171567868 407 27439924128 408 27710930788 409 27983269160 410 28258284044 411 28534643728 412 28813706164 413 29094126552 414 29377276060 415 29661796736 416 29949073028 417 30237733768 418 30529176748 419 30822017520 420 31117667284 421 31414728248 422 31714625084 423 32015946592 424 32320130980 425 32625753576 426 32934266188 427 33244230608 428 33557112308 429 33871459480 430 34188751324 431 34507522368 432 34829265604 433 35152501832 434 35478737900 435 35806480816 436 36137251348 437 36469542648 438 36804889468 439 37141771040 440 37481736164 441 37823250088 442 38167875724 443 38514064272 444 38863392820 445 39214298456 446 39568372508 447 39924037888 448 40282900228 449 40643368200 450 41007061804 451 41372375408 452 41740943444 453 42111145912 454 42484631740 455 42859766496 456 43238213668 457 43618324328 458 44001776588 459 44386906960 460 44775408244 461 45165602328 462 45559196764 463 45954498752 464 46353230660 465 46753684936 466 47157598828 467 47563249968 468 47972390548 469 48383283320 470 48797695484 471 49213874848 472 49633603684 473 50055114792 474 50480205580 475 50907093776 476 51337591988 477 51769902808 478 52205854108 479 52643633280 480 53085083524 481 53528376968 482 53975372204 483 54424226032 484 54876812500 485 55331273016 486 55789497148 487 56249610848 488 56713519268 489 57179332840 490 57648972364 491 58120532688 492 58595950324 493 59073304472 494 59554547420 495 60037742656 496 60524858308 497 61013942088 498 61506978028 499 62001998000 500 62501002004 501 63002006008 502 63507026044 503 64014062112 504 64525146340 505 65038262696 506 65555459468 507 66074704528 508 66598062388 509 67123484760 510 67653052444 511 68184700928 512 68720527364 513 69258450952 514 69800585260 515 70344833136 516 70893324628 517 71443946168 518 71998844348 519 72555889120 520 73117243684 521 73680761448 522 74248622284 523 74818662992 524 75393080180 525 75969693976 526 76550717788 527 77133955008 528 77721635908 529 78311547080 530 78905935724 531 79502571568 532 80103718804 533 80707130232 534 81315087100 535 81925325216 536 82540142948 537 83157259048 538 83778989068 539 84403034640 540 85031728564 541 85662755288 542 86298464924 543 86936524672 544 87579302020 545 88224446856 546 88874344108 547 89526626288 548 90183695828 549 90843167800 550 91507462204 551 92174176608 552 92845748644 553 93519758312 554 94198660940 555 94880018896 556 95566305268 557 96255064728 558 96948788188 559 97645002560 560 98346216644 561 99049939528 562 99758697964 563 100469983152 564 101186339860 565 101905241336 566 102629250428 567 103355822368 568 104087538148 569 104821834920 570 105561311884 571 106303388048 572 107050680884 573 107800591192 574 108555754780 575 109313554176 576 110076643588 577 110842387208 578 111613457708 579 112387200880 580 113166307924 581 113948106168 582 114735305404 583 115525214432 584 116320561700 585 117118637416 586 117922188748 587 118728487248 588 119540298868 589 120354876440 590 121175004764 591 121997917888 592 122826419524 593 123657724872 594 124494656620 595 125334411056 596 126179829908 597 127028090488 598 127882053628 599 128738877600 600 129601442404 601 130466887208 602 131338111244 603 132212234512 604 133092175540 605 133975035096 606 134863751068 607 135755404928 608 136652953988 609 137553460360 610 138459900844 611 139369318128 612 140284708564 613 141203095352 614 142127494460 615 143054909536 616 143988376228 617 144924878568 618 145867471948 619 146813120720 620 147764900084 621 148719754648 622 149680779484 623 150644899392 624 151615229380 625 152588674376 626 153568369388 627 154551199408 628 155540319508 629 156532594680 630 157531200124 631 158532980768 632 159541132004 633 160552478632 634 161570236300 635 162591209616 636 163618634548 637 164649295448 638 165686448668 639 166726858240 640 167773800964 641 168824020488 642 169880814124 643 170940905072 644 172007611220 645 173077635256 646 174154315708 647 175234334688 648 176321051428 649 177411127400 650 178507942604 651 179608137808 652 180715113844 653 181825490712 654 182942690140 655 184063311296 656 185190796868 657 186321725128 658 187459559788 659 188600858160 660 189749105044 661 190900836728 662 192059559164 663 193221787552 664 194391049060 665 195563837736 666 196743702028 667 197927114768 668 199117645748 669 200311746520 670 201513008284 671 202717861248 672 203929918084 673 205145587592 674 206368503980 675 207595054576 676 208828895188 677 210066391608 678 211311221308 679 212559728480 680 213815612324 681 215075195368 682 216342198604 683 217612922832 684 218891110900 685 220173041816 686 221462480348 687 222755683648 688 224056438468 689 225360980040 690 226673117164 691 227989063088 692 229312648724 693 230640065272 694 231975165820 695 233314119456 696 234660801508 697 236011358888 698 237369689228 699 238731917200 700 240101962804 701 241475928408 702 242857756444 703 244243526912 704 245637204740 705 247034847496 706 248440442668 707 249850025328 708 251267605588 709 252689195960 710 254118829244 711 255552495328 712 256994249764 713 258440059752 714 259894003660 715 261352025936 716 262818227828 717 264288530968 718 265767059548 719 267249712320 720 268740636484 721 270235707848 722 271739096684 723 273246655792 724 274762578580 725 276282694776 726 277811220988 727 279343963808 728 280885163108 729 282430602280 730 283984544524 731 285542749968 732 287109505204 733 288680547032 734 290260185500 735 291844134016 736 293436726148 737 295033651848 738 296639268268 739 298249241840 740 299867953364 741 301491045688 742 303122923324 743 304759205472 744 306404320420 745 308053863656 746 309712287308 747 311375163088 748 313046967028 749 314723247000 750 316408503004 751 318098259008 752 319797039044 753 321500343112 754 323212719340 755 324929643696 756 326655688468 757 328386305528 758 330126091388 759 331870473760 760 333624073444 761 335382293928 762 337149780364 763 338921911952 764 340703358260 765 342489474136 766 344284953628 767 346085127168 768 347894713348 769 349709018120 770 351532784684 771 353361294448 772 355199315284 773 357042103992 774 358894453180 775 360751594976 776 362618346788 777 364489916008 778 366371144908 779 368257216080 780 370152996724 781 372053644568 782 373964051804 783 375879351232 784 377804460100 785 379734486216 786 381674371948 787 383619200048 788 385573938068 789 387533643640 790 389503309564 791 391477968288 792 393462637924 793 395452325672 794 397452075020 795 399456867856 796 401471773108 797 403491747288 798 405521884828 799 407557116800 800 409602563204 801 411653129608 802 413713961644 803 415779939312 804 417856233940 805 419937699896 806 422029534268 807 424126565728 808 426234017188 809 428346691560 810 430469837644 811 432598232528 812 434737150964 813 436881344152 814 439036112860 815 441196182336 816 443366879428 817 445542903368 818 447729607148 819 449921663920 820 452124452884 821 454332621048 822 456551573884 823 458775932192 824 461011127780 825 463251755176 826 465503272588 827 467760248208 828 470028166708 829 472301569880 830 474585968924 831 476875879168 832 479176838404 833 481483335432 834 483800934700 835 486124098416 836 488458417748 837 490798328248 838 493149447868 839 495506185440 840 497874185764 841 500247830888 842 502632792524 843 505023425872 844 507425429620 845 509833132056 846 512252258908 847 514677111488 848 517113442628 849 519555526600 850 522009143404 851 524468540208 852 526939524244 853 529416315512 854 531904748540 855 534399016096 856 536904980068 857 539416805928 858 541940382988 859 544469849360 860 547011121844 861 549558311128 862 552117361564 863 554682356352 864 557259267460 865 559842150536 866 562437005228 867 565037859568 868 567650740948 869 570269649720 870 572900641084 871 575537687648 872 578186872484 873 580842140392 874 583509602380 875 586183175376 876 588868998388 877 591560960408 878 594265228508 879 596975663680 880 599698461124 881 602427453768 882 605168865004 883 607916499632 884 610676609300 885 613442970616 886 616221863548 887 619007036448 888 621804797668 889 624608867240 890 627425581964 891 630248633488 892 633084387124 893 635926506072 894 638781384220 895 641642656256 896 644516744708 897 647397255688 898 650290640428 899 653190476400 900 656103243604 901 659022490808 902 661954726844 903 664893471712 904 667845263140 905 670803592296 906 673775025868 907 676753026128 908 679744188788 909 682741947160 910 685752926044 911 688770529728 912 691801412164 913 694838948552 914 697889822060 915 700947378736 916 704018331028 917 707095995768 918 710187114748 919 713284975520 920 716396349284 921 719514494248 922 722646211084 923 725784728592 924 728936876980 925 732095855576 926 735268524188 927 738448052608 928 741641330308 929 744841497480 930 748055473324 931 751276368368 932 754511131604 933 757752843832 934 761008483900 935 764271102816 936 767547709348 937 770831324648 938 774128987468 939 777433689040 940 780752498164 941 784078376088 942 787418421724 943 790765566272 944 794126938820 945 797495440456 946 800878230508 947 804268179888 948 807672478228 949 811083966200 950 814509863804 951 817942981408 952 821390569444 953 824845407912 954 828314777740 955 831791428496 956 835282671668 957 838781226328 958 842294434588 959 845814984960 960 849350250244 961 852892888328 962 856450302764 963 860015120752 964 863594776660 965 867181866936 966 870783856828 967 874393311968 968 878017728548 969 881649641320 970 885296577484 971 888951040848 972 892620589684 973 896297696792 974 899989951580 975 903689795776 976 907404849988 977 911127524808 978 914865472108 979 918611071280 980 922372005524 981 926140622968 982 929924638204 983 933716368032 984 937523558500 985 941338495016 986 945168955148 987 949007192848 988 952861017268 989 956722650840 990 960599934364 991 964485058688 992 968385896324 993 972294606472 994 976219093420 995 980151484656 996 984099716308 997 988055884088 998 992027956028 999 996007996000 1000 1000004004004