0 1 1 0 2 918 3 6624 4 36450 5 120096 6 322436 7 764640 8 1637766 9 2912544 10 5591592 11 9160992 12 14668002 13 22913280 14 35544420 15 48529440 16 74114514 17 100230912 18 136486530 19 184801824 20 252809100 21 308852640 22 426995388 23 528491520 24 664053284 25 836215488 26 1070501400 27 1229873472 28 1608774372 29 1891550880 30 2265420636 31 2729881440 32 3353520582 33 3708510624 34 4681187316 35 5320804032 36 6175193382 37 7222374720 38 8629121484 39 9296582400 40 11442594600 41 12704306112 42 14415241536 43 16506180000 44 19327875264 45 20421248544 46 24681274776 47 26923285440 48 30048784146 49 33861758400 50 39039332130 51 40650746688 52 48435780924 53 52130023200 54 57437195384 55 63915443712 56 72818187300 57 74941661088 58 88308248328 59 94041332640 60 102517750944 61 112966747200 62 127442694276 63 129944505312 64 151774045650 65 160188034752 66 173192922108 67 189226909728 68 211813352244 69 214338843072 70 248439398184 71 260347360896 72 279438374034 73 303292698624 74 337266639000 75 339063886944 76 390555137808 77 406701435456 78 433973969568 79 468360094752 80 517822096428 81 517736387520 82 593099132148 83 614483538336 84 652495925160 85 700495511616 86 770812019316 87 766886122656 88 874590032124 89 902153785536 90 953509310712 91 1019439250560 92 1116804289464 93 1106792616672 94 1257234618888 95 1291467388608 96 1359871163876 97 1448193401280 98 1580849971434 99 1561124481120 100 1766731151538 101 1808862502176 102 1897963968888 103 2014584423840 104 2192276762712 105 2157436166976 106 2434348452600 107 2484194212512 108 2598930199926 109 2750907381120 110 2984320876248 111 2929197665664 112 3294999181764 113 3353558080896 114 3499183603296 115 3693584515392 116 3996861393204 117 3912163994304 118 4390446199500 119 4458018513600 120 4639917244572 121 4885956427968 122 5273883578664 123 5150427650496 124 5768005394988 125 5842725383232 126 6068206625580 127 6375215463264 128 6867618484806 129 6694489392480 130 7479294297192 131 7561873251360 132 7836072912288 133 8217928369152 134 8836548548436 135 8595100199520 136 9586877302548 137 9672449568192 138 10007435713680 139 10476566083296 140 11242937844936 141 10917555050880 142 12154474786680 143 12244189065408 144 12647761675254 145 13217037603264 146 14162746400568 147 13729651643808 148 15261003049860 149 15351648886368 150 15829912900388 151 16519748510880 152 17672463214092 153 17107973024832 154 18991848937392 155 19073319616512 156 19643591385540 157 20465821454400 158 21865742534700 159 21140341999200 160 23433978132648 161 23505865476480 162 24170760044262 163 25153965496224 164 26844074616924 165 25917878213568 166 28695108105252 167 28742405363136 168 29521957224960 169 30690672785280 170 32706988584768 171 31544942698080 172 34877941412976 173 34900830890208 174 35815418636580 175 37180521900576 176 39584582442432 177 38125687635936 178 42117399705924 179 42103800413856 180 43151035674276 181 44757885896064 182 47593457615880 183 45802713091968 184 50548041251352 185 50472373620672 186 51678661778496 187 53544013936128 188 56887831957320 189 54700000253280 190 60300800168832 191 60160762350720 192 61538976558738 193 63700118050176 194 67626447102648 195 64951706835648 196 71550287886366 197 71308173596256 198 72882375339060 199 75392621551008 200 79954627502322 201 76745277057888 202 84446881612056 203 84101936705280 204 85892730866496 205 88766382544704 206 94077012953484 207 90203722038144 208 99198787987548 209 98728352058816 210 100743568483032 211 104036042560608 212 110151628611876 213 105550463434176 214 116006376097404 215 115351052280768 216 117631239887576 217 121368711441600 218 128426440659912 219 123001125134976 220 135052917863544 221 134210726997120 222 136738226023200 223 141012771854112 224 149132942710308 225 142698401347680 226 156601646466156 227 155497826757600 228 158351408349444 229 163204581974400 230 172460275295256 231 164926394513280 232 180856574869896 233 179486635665600 234 182686867001928 235 188137432475712 236 198711414921240 237 189903789855648 238 208126592963784 239 206451918039168 240 209957093038368 241 216138252901248 242 228101744871270 243 217885955783328 244 238699335265812 245 236602576398240 246 240538561127712 247 247404509218944 248 261001156083012 249 249182451824544 250 272803176509616 251 270297839642976 252 274577004021420 253 282317194101888 254 297708522353172 255 284064335829504 256 310831877935314 257 307761075500544 258 312500201068512 259 321205200660288 260 338474125011888 261 322824285167904 262 353032796258964 263 349406754459840 264 354708026648604 265 364302274655808 266 383753841515424 267 365743772819712 268 399839121849816 269 395616708080928 270 401321289717108 271 412067936561184 272 433797504936084 273 413340864254208 274 451676826885564 275 446613819796512 276 452894687386560 277 464743535886720 278 489107354009796 279 465879554931168 280 508804669749672 281 502938760163904 282 509741756456544 283 522886439464416 284 550110899727144 285 523657447457472 286 571776929951040 287 564843712996800 288 572298733893330 289 586905119708544 290 617117467053096 291 587323314588096 292 640851438453912 293 632927731044960 294 641078614565444 295 657087185937024 296 690733894329432 297 656985158274528 298 716692913135352 299 707667399308160 300 716442908327622 301 734090087205504 302 771237731611404 303 733330468556640 304 799868352879504 305 789317562582720 306 798891778926684 307 818169462849888 308 859362896919960 309 817028646382368 310 890569981225440 311 878656754488896 312 888773850914976 313 910071201670848 314 955697325671592 315 908086775534784 316 989643468399444 317 975888494903520 318 987059171455380 319 1010366432654400 320 1060499471251500 321 1007409093499872 322 1097373984636744 323 1081902654992448 324 1093981535767890 325 1119356428182912 326 1174635856996956 327 1115400228810624 328 1214685351372564 329 1197323127533952 330 1210010659661952 331 1237895231849568 332 1298408030352288 333 1232624617943040 334 1342204450481952 335 1322378539227072 336 1336324537935720 337 1366278089393088 338 1432801758358566 339 1359959901300864 340 1480151522948112 341 1458096940886400 342 1472700660095844 343 1505553524385408 344 1578619232178228 345 1497762584750016 346 1629766576545480 347 1604674047247776 348 1620421665159456 349 1656447349280832 350 1736024577785604 351 1646768909828160 352 1791162989344764 353 1763366528022912 354 1780547516735220 355 1819136178988416 356 1906258678602228 357 1807356291497856 358 1965656542173876 359 1934861321370240 360 1952823197658744 361 1994891603669568 362 2089531271610360 363 1981089340807392 364 2154074431533048 365 2119401248897088 366 2138663651829984 367 2183961028866336 368 2287247715316728 369 2168183836604160 370 2356617060958248 371 2318411908638720 372 2338653802617936 373 2387663884042560 374 2500387468448112 375 2368997964545472 376 2574819511366536 377 2531972994341184 378 2553673881396672 379 2607027165938016 380 2728863182957184 381 2585597424335136 382 2808660500550288 383 2761689883264128 384 2785006409314916 385 2842104827136384 386 2974606082306784 387 2817073702554336 388 3060030181352832 389 3008517526913760 390 3033030712431744 391 3094637451585984 392 3237635252912634 393 3065662073335392 394 3329879475659976 395 3272608159981056 396 3298652233459776 397 3364569632407104 398 3519776438691948 399 3332883741933312 400 3618328319647650 401 3555690550751232 402 3582493873973856 403 3653865023211648 404 3822123048247620 405 3617639858745504 406 3927382815866976 407 3857834441630016 408 3887023334642424 409 3963838461307776 410 4144602204874224 411 3922454544176448 412 4256824514858892 413 4181225809518720 414 4212321635687112 415 4294048981243968 416 4489795766208600 417 4247748017517024 418 4609152471571704 419 4527039574728288 420 4558661985531456 421 4647093753194496 422 4857010406239212 423 4594804320024000 424 4985614355585400 425 4894957533764736 426 4929419364612624 427 5022631575709056 428 5249100673979640 429 4965188493510720 430 5385943483061472 431 5287560999854400 432 5322692824240518 433 5423316217661376 434 5667566970275568 435 5359563296121024 436 5812669426661316 437 5704664366076480 438 5741805701612736 439 5850493316092512 440 6111889779922776 441 5779083144105504 442 6265659171775824 443 6148860808202784 444 6189406450117452 445 6303503567733696 446 6584992549594380 447 6223922837762400 448 6748133791377348 449 6621933386612736 450 6662761203527334 451 6785913564494208 452 7086064283595828 453 6698201585766624 454 7261402557075804 455 7123088796619392 456 7166433082231584 457 7296488431371648 458 7619240038561560 459 7201337255234496 460 7804536315303168 461 7655840217160416 462 7700536326186000 463 7839163982748960 464 8185688538114708 465 7733768805525888 466 8381505039169140 467 8219101531692960 468 8266412853723060 469 8415589972134528 470 8784498722429448 471 8300048089388544 472 8991643408827660 473 8816797871881920 474 8867032843654080 475 9024534685887264 476 9419793872169816 477 8896895329592736 478 9638368081292880 479 9451117163492928 480 9502572271501980 481 9670203590103936 482 10090433233630008 483 9529680389454720 484 10324023780321918 485 10120021838642880 486 10174818519893684 487 10351031530695840 488 10801070208977256 489 10201683420039456 490 11047248194850216 491 10828752320857824 492 10882859364994752 493 11072344082853312 494 11553258115103688 495 10908158554841472 496 11813065125169356 497 11575465093272960 498 11634318930899556 499 11835400146202080 500 12345653675202408 501 11655435800188224 502 12619111187305332 503 12365336628703872 504 12427698550079340 505 12638781801548352 506 13183397061106320 507 12444035986147104 508 13470836968889388 509 13200338796056352 510 13262087096702784 511 13488025119264576 512 14064867511890246 513 13274969024653344 514 14371578669154860 515 14078029970525760 516 14145437679972300 517 14380691981572224 518 14995738642191552 519 14152764347564832 520 15317803750004136 521 15005297545088832 522 15071099540082840 523 15322910660823456 524 15978251722571352 525 15077117432725920 526 16316516840431824 527 15978396169293120 528 16048527521126688 529 16316834960763648 530 17009700496429320 531 16049828562832224 532 17364463626251088 533 17004893207169600 534 17081230380191064 535 17360241814057536 536 18097251364688148 537 17069890733921376 538 18469463963658696 539 18087231310566624 540 18161448436450368 541 18459306810224640 542 19237717723343148 543 18147175754049792 544 19633933123575444 545 19221645025213632 546 19299837702792384 547 19611234599952096 548 20437931446922916 549 19279633924237824 550 20853222292088820 551 20416020816303936 552 20495524218097680 553 20824098915453120 554 21702171128180040 555 20464635282537024 556 22136988761282376 557 21665981814709536 558 21750005978309772 559 22100501125991232 560 23025885250153608 561 21715095499353792 562 23479746341469804 563 22981488270197472 564 23068808068680576 565 23435591849235648 566 24417648821481012 567 23019640046287200 568 24892388539647480 569 24363947514602304 570 24452687516769648 571 24838698546068256 572 25871973828546240 573 24390604361395584 574 26377003790770680 575 25809234767661312 576 25902562336991478 577 26305627697011008 578 27399804215554242 579 25834838850035712 580 27927590468268528 581 27327642927495552 582 27416866958625600 583 27845283677265792 584 29005733456470008 585 27338397474920256 586 29555854818053256 587 28912873590310176 588 29010722502738114 589 29462145382483200 590 30680656992702504 591 28917418771352736 592 31255019971550820 593 30576163531349376 594 30679304396651604 595 31149347070015360 596 32438022154480116 597 30568125019572000 598 33038043643973808 599 32320437145880832 600 32419670242632644 601 32919043861374336 602 34271142307725168 603 32294812737240288 604 34906241717624988 605 34140063716398944 606 34248472959855780 607 34763206540894560 608 36193223658031884 609 34105103206018560 610 36854077717765008 611 36045988785835200 612 36149114303713692 613 36695042914934592 614 38206682192854188 615 35996380648801920 616 38895897954212784 617 38031439131524160 618 38139201503419968 619 38720047494954528 620 40301920432757736 621 37971177174368064 622 41020910626093632 623 40110916836719808 624 40230693372685860 625 40826488586483520 626 42497772654844080 627 40025471402172672 628 43244322863708628 629 42287920508548800 630 42400231963475832 631 43031983992334560 632 44781057782848620 633 42183078481926432 634 45571226425692120 635 44551824005238336 636 44669536281706464 637 45325779000425856 638 47169804683026080 639 44432209406771712 640 47992761902920104 641 46919016657183744 642 47035930287391668 643 47724577104958560 644 49667911464802968 645 46770459377871168 646 50522549130812232 647 49380452076275712 648 49502434891572054 649 50232316262829120 650 52263972914791896 651 49222677164717376 652 53150294320555680 653 51951330402159456 654 52081235643534048 655 52835976437622912 656 54977498429155452 657 51761282861743488 658 55897190719229232 659 54638650754839008 660 54764513998062264 661 55557832403206080 662 57792267255246948 663 54412245954974592 664 58767550950536676 665 57428151364259712 666 57560070281307336 667 58380349345799040 668 60732659052330624 669 57188597730887520 670 61744374910174464 671 60340847571063360 672 60461025886329984 673 61327815625735488 674 63801209891203128 675 60061097663350272 676 64849434641094726 677 63360661599840096 678 63497630327977584 679 64404712976908608 680 66984917594825664 681 63056536838060256 682 68071534839855360 683 66510193576864032 684 66654447754424112 685 67593897961204032 686 70305942494565216 687 66171691170224640 688 71431060698377712 689 69798067404683328 690 69925024197938880 691 70919651051486496 692 73745426597317812 693 69410333019806784 694 74934735468672060 695 73201337800713792 696 73349983802856420 697 74362604685905664 698 77331399851630952 699 72786806079291648 700 78562463543125740 701 76750164156912480 702 76880730800396736 703 77953626588143232 704 81069198057349056 705 76293105536362176 706 82344193433479116 707 80423839251984960 708 80559622785415392 709 81692883668657664 710 84938985544273200 711 79933036153871520 712 86257733055915492 713 84250810309749120 714 84407201596137312 715 85562897120029440 716 88965346502510856 717 83700525195296640 718 90330522178576680 719 88236046830989376 720 88374626696024964 721 89593821974589120 722 93131999172705546 723 87633732623122944 724 94573350833927220 725 92355227761158432 726 92502989425494884 727 93760684703897184 728 97471375996385160 729 91715833008291168 730 98957192555343312 731 96645737626280640 732 96781189390886844 733 98096620054555008 734 101986358666374620 735 95934928439234016 736 103522430159611416 737 101075425098677568 738 101221871375889756 739 102606484840693920 740 106648143151943952 741 100339798754127744 742 108236941800582816 743 105684985369564992 744 105839562478170240 745 107267791115931840 746 111496951225427544 747 104871809563418592 748 113138467544553264 749 110479977114550848 750 110624469090816456 751 112111299606042720 752 116508038868981000 753 109581472374617952 754 118235980406148624 755 115429827429183744 756 115581057722439480 757 117112019003766144 758 121711456891421964 759 114499391702686848 760 123496022621361024 761 120573923807483712 762 120696371780541120 763 122310225797658048 764 127119664403916768 765 119551154729950656 766 128964980064113424 767 125877824474028480 768 126031810368076434 769 127712274510830976 770 132701067873407088 771 124801399767552768 772 134598283204409640 773 131391991653959520 774 131551139119033692 775 133281196549074144 776 138501080940185208 777 130235632442074944 778 140453352657048024 779 137115251612888832 780 137243048582471616 781 139062692736025344 782 144475700455093752 783 135857893337037792 784 146537180202333870 785 143016207237357120 786 143172401854570236 787 145025119292075424 788 150674091170218236 789 141694091208998208 790 152803916928758304 791 149143636115931456 792 149263023819274740 793 151208696338917120 794 157115822323911048 795 147726080639070912 796 159304688882584380 797 155454130665441504 798 155582582076055872 799 157629571841629440 800 163747088740220850 801 153967612979592576 802 165998142216212508 803 162000836795054016 804 162162710318765844 805 164241723072693888 806 170627385415674024 807 160387009552491552 808 172949869323541656 809 168790158488501568 810 168911858223912168 811 171100978626342240 812 177707473992558792 813 167073929432276832 814 180152520960596400 815 175782709835188416 816 175910903028081216 817 178157047039602624 818 185052190847211432 819 173983576214654208 820 187563415017874536 821 183028111480198944 822 183142470830545152 823 185469825808480608 824 192669739214940108 825 181091078493580512 826 195251074396593408 827 190482516894346272 828 190600415252775720 829 193057646233576320 830 200496873108908304 831 188485985992429440 832 203159177570673756 833 198210125021682816 834 198336819634701984 835 200852857478487744 836 208613041715585160 837 196054815551327136 838 211349135160389916 839 206218717853455872 840 206325945588698136 841 208933318403694144 842 216950508531510552 843 203903411900755968 844 219828111912260856 845 214447671107205408 846 214567441152218136 847 217238620003081056 848 225593906813604612 849 212059802362978656 850 228551004907376148 851 222967961378176320 852 223028124292868544 853 225840536103360960 854 234546172842591288 855 220409013981819456 856 237581003070003132 857 231726950731320768 858 231824821046428368 859 234746707061545056 860 243736766543407680 861 229055853626885376 862 246853958033952792 863 240787357464946176 864 240908790773344664 865 243888413305621824 866 253253655399991392 867 237970115076732768 868 256452139965891888 869 250172117108066880 870 250221495563327232 871 253359702986984064 872 263021287146163848 873 247157231140706112 874 266391005034239280 875 259806740672207232 876 259901253259437168 877 263070762342830784 878 273135115249229268 879 256660987408510752 880 276592451450340024 881 269776822117841280 882 269797866892131582 883 273122834325604704 884 283587321674980152 885 266460695549909568 886 287138893021098588 887 280002515585054400 888 280039944768786720 889 283526261849958336 890 294318267707497968 891 276548133806726688 892 297959970606310260 893 290574591978773952 894 290673421800727140 895 294195619631121408 896 305424275626372644 897 286895516341995648 898 309146304976612380 899 301519969664334912 900 301521686837605398 901 305227702288725696 902 316806489206298288 903 297643551813328896 904 320725037054548044 905 312729807264737472 906 312753640120977600 907 316529524178575200 908 328566981362632992 909 308711088841403808 910 332590488986419344 911 324325287269815680 912 324308527351845732 913 328224562042510656 914 340724469648883608 915 320049115910418240 916 344851354311371604 917 336209007938275584 918 336200553067553064 919 340302801646951200 920 353198544119359128 921 331813658961932832 922 357413634205136712 923 348490940527914048 924 348489487114558848 925 352680674285977920 926 366072069700301436 927 343821714810908832 928 370394299780263432 929 361180051621056000 930 361136693716942896 931 365474696802442272 932 379255357115099604 933 356216290090691904 934 383814823625422740 935 374167488746145024 936 374148235943407368 937 378573105430237248 938 392882965938316368 939 369084935266171200 940 397534383665834832 941 387597281513353056 942 387455102638935264 943 392099669597572992 944 406967104434100824 945 382203141838414272 946 411718879937025000 947 401327791121913120 948 401266832116204944 949 406063544751911808 950 421371644805904932 951 395749838521938528 952 426243340537422408 953 415513899980529984 954 415460048276529000 955 420366475613045376 956 436232835258188832 957 409669368967086336 958 441232810485658776 959 430166202472703808 960 429992178346384416 961 435119313882565440 962 451454578651903824 963 423967421435699808 964 456700012675552656 965 445153714567519680 966 445061143257975936 967 450215473632789600 968 467159384073479382 969 438741470992932864 970 472516179492896496 971 460620062203933152 972 460393004688045714 973 465799076566053120 974 483370878623041980 975 453903781057303680 976 488863592913203316 977 476424839242063872 978 476218069799116896 979 481883633070945984 980 499941042546317004 981 469486618989554880 982 505549463763628116 983 492749346039884352 984 492622998225182496 985 498320859303554112 986 517047410425082976 987 485415068425105536 988 522765536254275240 989 509577039383896512 990 509322106406366856 991 515269985314298400 992 534530283317024580 993 501924581729867232 994 540540513651251448 995 526779728752762368 996 526522492294038432 997 532605214957296960 998 552546448235039340 999 518872488372597312 1000 558709285938497712