1 1 2 1 3 2 4 6 5 4 6 32 7 6 8 56 9 24 10 94 11 10 12 1686 13 12 14 188 15 218 16 960 17 16 18 5772 19 18 20 7894 21 432 22 472 23 22 24 329992 25 120 26 662 27 702 28 21750 29 28 30 809648 31 30 32 31744 33 1076 34 1138 35 1214 36 10070172 37 36 38 1424 39 1506 40 2551944 41 40 42 3111034 43 42 44 84694 45 90876 46 2092 47 46 48 254471232 49 336 50 124780 51 2582 52 139926 53 52 54 8496522 55 3010 56 9812488 57 3228 58 3334 59 58 60 46655180414 61 60 62 3812 63 249582 64 2064384 65 4208 66 18973142 67 66 68 313270 69 4736 70 24008492 71 70 72 139303661760 73 72 74 5438 75 421530 76 437526 77 5912 78 37012840 79 78 80 3274239040 81 58320 82 6682 83 82 84 351294896478 85 7204 86 7352 87 7538 88 59884296 89 88 90 531440093328 91 8262 92 776566 93 8616 94 8788 95 9002 96 782502953984 97 96 98 940660 99 969186 100 999867100 101 100 102 108239444 103 102 104 116845192 105 121548748 106 11182 107 106 108 1586855748024 109 108 110 146406408 111 12282 112 17613581376 113 112 114 168891310 115 13198 116 1557526 117 1600068 118 13864 119 14138 120 42998122941118008 121 1320 122 14822 123 15086 124 1902774 125 15500 126 4001500774302 127 126 128 266338304 129 16596 130 285605018 131 130 132 5289833739902 133 17664 134 17888 135 332058798 136 341787528 137 136 138 362667050 139 138 140 7529511960350 141 19832 142 20092 143 20426 144 15406882006044672 145 20992 146 21242 147 3175746 148 3236310 149 148 150 11390623643570 151 150 152 533355784 153 3578952 154 562442066 155 23990 156 14412737288382 157 156 158 24884 159 25226 160 16773939168256 161 25892 162 111568539456 163 162 164 4404214 165 741196304 166 27472 167 166 168 634561929928944824 169 2184 170 835201542 171 4996938 172 5081046 173 172 174 916625240 175 5358030 176 168814242880 177 31268 178 31594 179 178 180 198359289789893739828 181 180 182 1097190244 183 33426 184 1145449992 185 34184 186 1196870722 187 34942 188 6635830 189 1275739092 190 1303199456 191 190 192 9617744959930368 193 192 194 37538 195 1445894674 196 20660083836 197 196 198 60254709611946 199 198 200 63998997448000 201 40332 202 40702 203 41174 204 72074286274718 205 41980 206 42332 207 8864958 208 389211941952 209 43652 210 3782285935950519886 211 210 212 9516886 213 45296 214 45688 215 46178 216 4738379612143302144 217 47052 218 47414 219 47886 220 113379757497406 221 48812 222 2428894864 223 222 224 126307028403200 225 38442846600 226 50962 227 226 228 140478078596670 229 228 230 2798394588 231 2847388882 232 2895462024 233 232 234 164170470292296 235 55174 236 13130326 237 56088 238 3208527248 239 238 240 634033766655586871288768 241 240 242 14170684 243 14289858 244 14511894 245 14704564 246 3662164412 247 60978 248 3780835336 249 61916 250 3906109500 251 250 252 4098310573981479445044 253 63976 254 64388 255 4228240598 256 68451041280 257 256 258 4430742070 259 67038 260 308915490242174 261 17771988 262 68512 263 262 264 23595615882577781688 265 70168 266 5006392234 267 71198 268 19230870 269 268 270 28242953116318443978 271 270 272 1488485870656 273 5554561620 274 74938 275 20793730 276 442032432527582 277 276 278 77144 279 21708966 280 37780192304051635512 281 280 282 6324037874 283 282 284 22886134 285 6597488152 286 6690564032 287 82322 288 13631131232009167306752 289 4896 290 7072785546 291 84582 292 24875766 293 292 294 645779088421418 295 86962 296 7673321608 297 7779856680 298 88654 299 89366 300 19682999988561719942900 301 90552 302 91052 303 91706 304 2595844189248 305 92960 306 820972291815492 307 306 308 853697506289438 309 95376 310 9235182068 311 310 312 89791800984198380600 313 312 314 98438 315 976929600124518 316 31529526 317 316 318 10226026880 319 101722 320 343580606461935616 321 102932 322 10750343654 323 104294 324 6746638918034537712 325 34323780 326 106112 327 106818 328 11569906056 329 108188 330 140640861823192609578 331 330 332 36566806 333 36913692 334 111388 335 112154 336 18339722450889421576938432 337 336 338 38611612 339 114806 340 1544803580468830 341 116240 342 1600134868950594 343 117306 344 13998320392 345 14166932444 346 119542 347 346 348 1776132001137470 349 348 350 1838265595507070 351 15176884086 352 1902030265222144 353 352 354 15704054630 355 125950 356 45086326 357 16243230424 358 127984 359 358 360 4738381338123214607369752338240 361 6840 362 130862 363 47829738 364 2325991358998878 365 133148 366 17944161592 367 366 368 6747848567872 369 50228256 370 18741570242 371 137582 372 2650070592619422 373 372 374 19565258796 375 19774953250 376 19980528648 377 142088 378 416806415027024174244 379 378 380 3010935080344574 381 145032 382 145732 383 382 384 472760255954859065344 385 21970640468 386 148802 387 57943938 388 58373430 389 388 390 535200926046330671080 391 152842 392 3628389721159616 393 154316 394 155038 395 155942 396 239473065258806986369332 397 396 398 158204 399 25344937050 400 32767935996725760000 401 400 402 26115794494 403 162366 404 65898454 405 10895869044180 406 27170862164 407 165602 408 767858619858907833144 409 408 410 28257561198 411 168782 412 69892086 413 170504 414 5035029445162446 415 172138 416 5182357370799104 417 173748 418 30528430598 419 418 420 30129469486635899242136437931422 421 420 422 177872 423 75667062 424 32309881992 425 76758280 426 32933473082 427 182262 428 78356950 429 33871066648 430 34187956328 431 430 432 226379689040242737907236864 433 432 434 35477931646 435 35806071842 436 82834326 437 190928 438 36804051100 439 438 440 1404822249141633563704 441 794276620452 442 38167041854 443 442 444 7661215573500798 445 197932 446 198692 447 199658 448 3621854093240205312 449 448 450 756680642566164491963400 451 203350 452 92294326 453 205056 454 205888 455 42859336918 456 1869470897087195351480 457 456 458 209534 459 44382901482 460 9474294096805534 461 460 462 2075562447060717847240 463 462 464 21504601549888 465 46753217764 466 216922 467 466 468 1076992496633541384489780 469 219888 470 48796745892 471 221682 472 49619566344 473 223676 474 50479223890 475 107162730 476 11631657254353214 477 108506028 478 228244 479 478 480 149587342464053925624683557846016 481 231312 482 232082 483 54423726430 484 1207254960604 485 235124 486 13176920862666846 487 486 488 56698037896 489 238956 490 13841287161344440 491 490 492 14183731595365982 493 243004 494 59553506200 495 14710626592129914 496 30016057896000 497 246932 498 61505894510 499 498 500 15624995093875000 501 250832 502 251752 503 502 504 268637376391444593605883155275584 505 254920 506 65554366722 507 130320138 508 131031990 509 508 510 4576794457034927497476 511 261042 512 35115652612096 513 69252921648 514 263938 515 265118 516 18875484486656382 517 267232 518 71997696268 519 269186 520 5345972544229704602808 521 520 522 20231263099861944 523 522 524 143809174 525 20938994257435320 526 276412 527 277682 528 1683988879560007296254223296 529 12144 530 78904728498 531 149689938 532 22670948890167006 533 284036 534 81313841420 535 286114 536 82519742728 537 288188 538 289174 539 156584554 540 614787626176281797370928485251976 541 540 542 293492 543 294666 544 25916028536980480 545 296912 546 7898436694221821209094 547 546 548 164491510 549 165435636 550 27680640457671370 551 303554 552 8620105866204244883640 553 305724 554 306638 555 94879353898 556 171802326 557 556 558 30185972780398566 559 312426 560 3033054853180941905512178624 561 99049269212 562 315562 563 562 564 32186558174244638 565 319108 566 320072 567 58601109379446 568 104063339016 569 568 570 11142915711192029597410 571 570 572 35024834336155262 573 328136 574 108554345336 575 190096030 576 96479715597018230610852839424 577 576 578 193094500 579 335046 580 38068685469624574 581 337472 582 114733825924 583 339826 584 116294297992 585 40080689205049032 586 343102 587 586 588 8402256486781811955044436 589 346872 590 121173509016 591 349082 592 72704732490816 593 592 594 15498567466499936551248 595 125333678042 596 211619926 597 356208 598 127880528660 599 598 600 2176782335980316956937878058552000 601 600 602 131336561074 603 219215802 604 220257654 605 221440780 606 134862147152 607 606 608 50512533698610176 609 137552666980 610 138458302058 611 373262 612 12043779597541741488315444 613 612 614 376688 615 143054093294 616 20732213828636279894712 617 616 618 145865803930 619 618 620 56800226346879326 621 148710110436 622 386572 623 388034 624 8950471055694857157797094336 625 9750000 626 391562 627 154550362654 628 247574550 629 395588 630 3909188328478824096413601358661598 631 630 632 159507977224 633 400476 634 401638 635 403094 636 66182417465833982 637 258466236 638 165684712368 639 260871726 640 28147154073681653661696 641 640 642 169879014134 643 642 644 71337048801950078 645 173076737584 646 174152536964 647 646 648 13054193874104563682699120640 649 421132 650 75418890304941320 651 179607231462 652 277061526 653 652 654 182940822280 655 428890 656 121472457501760 657 283545408 658 187457708078 659 658 660 6831675453247285759275459653487998 661 660 662 437912 663 193220852830 664 194352688392 665 195562922716 666 87266058879791472 667 444838 668 297966070 669 447336 670 201511079792 671 450170 672 8480691703716601862911842444147712 673 672 674 453938 675 94585041546846750 676 5429464924572 677 676 678 211309213940 679 460938 680 45716322420532839660472 681 463532 682 216340214810 683 682 684 32772148602125544790692660 685 469084 686 221459536718 687 471738 688 154135521717312 689 474656 690 51379837442846771175870 691 690 692 331254166 693 110764195248263136 694 481288 695 482882 696 55064779295963298310200 697 485752 698 486854 699 488366 700 40353606998154203863142900 701 700 702 58978930888701840502530 703 494154 704 85703582228695515136 705 247033775348 706 498082 707 499742 708 125950382846255870 709 708 710 254116663788 711 359369238 712 256947101064 713 508316 714 67543831712592854204770 715 261350972954 716 366933526 717 513848 718 515164 719 718 720 7244150201404252289687504569041527593955328 721 519732 722 376358764 723 522486 724 379372374 725 381056980 726 146426514263318498 727 726 728 78895279977461133527864 729 10446004296 730 283982255438 731 534302 732 153838995557232702 733 732 734 538388 735 157660911884459354 736 158945576477492224 737 543092 738 161561605755821676 739 738 740 164206471431145790 741 301489878816 742 303120569084 743 742 744 93882246254137081491128 745 554872 746 556142 747 416770698 748 175149756819162718 749 560888 750 100112915027648193921750 751 750 752 240465682885696 753 566756 754 323210296130 755 569870 756 34854715807862685511634284681551240 757 756 758 574184 759 331869248738 760 111303475734560680092216 761 760 762 337147245154 763 582054 764 445797814 765 200432711501345148 766 586372 767 588218 768 92949866712448675444948992 769 768 770 123573629154745396491654 771 594182 772 459950646 773 772 774 215003611519195146 775 465460230 776 362557523848 777 364488625644 778 604894 779 606782 780 50714860157240502094366577017139518 781 609880 782 373961446464 783 375860341638 784 5097651726810385354752 785 616064 786 381671674622 787 786 788 489148630 789 622256 790 389500628996 791 625562 792 60911904570799393837260516571668288 793 628776 794 630038 795 399455504954 796 504199926 797 796 798 164445930585165118706432 799 638338 800 134217695231983226060800000 801 513851088 802 642802 803 644726 804 270107255687433918 805 419936360288 806 422026765612 807 650978 808 426165463176 809 808 810 121576654562326323354462358044 811 810 812 286639563810493406 813 660696 814 439033287656 815 664058 816 130888528429240565723705189312 817 667428 818 668714 819 301788997617499566 820 304006643161977886 821 820 822 456548623964 823 822 824 460938473992 825 315299796356724620 826 465500355554 827 826 828 182924986245907370732369460 829 828 830 474583010208 831 690282 832 275965713522098208768 833 577995040 834 483797898070 835 697054 836 341379647639028734 837 490775205420 838 701824 839 838 840 61442457392708782983035689222020711643065607176 841 24360 842 708542 843 710366 844 601033494 845 603344716 846 366625079914442262 847 607638174 848 438477437856832 849 720516 850 377149514712906820 851 724142 852 382505365227136862 853 852 854 531901630516 855 390657962843052162 856 536823642888 857 856 858 293696183341615620889954 859 858 860 404567200942901054 861 549556727152 862 742612 863 862 864 173047332533638863888541012293844992 865 748048 866 749522 867 651706866 868 427679383158301758 869 755072 870 328211671543668303675480 871 758562 872 578100945544 873 665253912 874 583506348890 875 586176265750 876 451881541522335582 877 876 878 770444 879 772346 880 278500974604579759546311517120 881 880 882 323010965706467776378955244 883 882 884 477214416769321118 885 613441282112 886 784552 887 886 888 386637271765873310780984 889 790188 890 627422180286 891 561542333679450 892 709533366 893 797384 894 638777895200 895 800842 896 415394068187022842920960 897 647395547236 898 805954 899 808142 900 7625597484986999223437998143475721190000 901 811732 902 661951258260 903 664891729650 904 667749645192 905 818840 906 673771442602 907 906 908 748407190 909 750997596 910 470252527615107833844676 911 910 912 398059855709863602598524101568 913 833476 914 834938 915 700945573954 916 768365526 917 840752 918 504360943989355481468814 919 918 920 513218863663263555998008 921 847932 922 849622 923 851846 924 387314409522868101901230176997671326 925 791418780 926 857012 927 796502478 928 638665170149671936 929 928 930 559581809664982913882998 931 806936466 932 809340406 933 870176 934 871888 935 764269305438 936 452178787380140084987066983323524928 937 936 938 774125226298 939 881406 940 689869732252546270 941 940 942 787414548184 943 889186 944 749602829036608 945 635996121810258233076408 946 800874415502 947 946 948 725855202275581470 949 900516 950 735091889214502370 951 904082 952 674676494254296719422008 953 952 954 753859205201865696 955 911830 956 873494326 957 838779280424 958 917284 959 919538 960 564673312205526259354570497105648576069632 961 29760 962 856446359674 963 892953282 964 895609014 965 931028 966 758258017972313100871324 967 966 968 822718961058047680 969 881647649380 970 885292537142 971 970 972 774455343386244211742655456 973 946584 974 948188 975 859068299544744570 976 885566698351680 977 976 978 914861296990 979 958342 980 833747762116301050626926164 981 943969188 982 963832 983 982 984 878943139083616027125048 985 970024 986 945164814894 987 949005112054 988 930125689995847230 989 978056 990 886384871716129140003167763157098954 991 990 992 952919801402983424 993 985716 994 976214870006 995 989822 996 976238662291307582 997 996 998 995504 999 995969069262 1000 999999984311001000000000