1 #include <cstdio> 2 #include <algorithm> 3  4 using namespace std; 5 typedef long long ll; 6 const int N = 3000; 7 const int M = 3005; 8 const int H = 35; 9 const ll mod = 1000000000;10 11 int n;12 int maxh[H], minh[H], L[M], R[M];13 ll dp[M][H], ans[M]; 14 15 inline int read() {16     int x = 0;17     char ch = getchar();18     while (ch < ‘0‘ || ‘9‘ < ch)19         ch = getchar();20     while (‘0‘ <= ch && ch <= ‘9‘) {21         x = x * 10 + ch - ‘0‘;22         ch = getchar();23     }24     return x;25 }26 27 void pre_work() {28     int i, j;29     minh[1] = maxh[1] = 1, minh[2] = 2, maxh[2] = 3;30     for (i = 3; i <= 30; ++i)31         minh[i] = minh[i - 1] + minh[i - 2],32         maxh[i] = maxh[i - 1] << 1 | 1;33     for (i = 1; i <= 30 && minh[i] <= N; ++i)34         for (j = minh[i]; j < min(minh[i + 1], N + 1); ++j)35             R[j] = i;36     for (L[1] = 1, i = 2; i <= 30 && maxh[i - 1] <= N; ++i)37         for (j = maxh[i - 1] + 1; j <= min(maxh[i], N); ++j)38             L[j] = i;39 }40 41 void DP() {42     int i, j, h, l, r;43     dp[0][0] = dp[1][1] = 1, ans[1] = 1;44     for (i = 2; i <= N; ++i){45         for (l = 0; l < i; ++l)46             for (r = i - l - 1, h = max(0, L[i] - 2); h <= min(29, R[i] - 1); ++h) {47                 if (h) dp[i][h + 1] += dp[l][h] * dp[r][h - 1];48                 (dp[i][h + 1] += dp[l][h] * dp[r][h]) %= mod;49                 dp[i][h + 2] += dp[l][h] * dp[r][h + 1];50             }51         for (h = 1; h <= min(29, i); ++h)52             ans[i] += dp[i][h];53         ans[i] %= mod;54     }55 }56 57 int main() {58     pre_work();59     DP();60     while ((n = read()) != 0)61         printf(n >= 38 ? "%09lld\n" : "%lld\n", ans[n]);62     return 0;63 }

 1 #include <cstdio> 2  3 using namespace std; 4 const long long ans[3005] = {0, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 16088, 36900, 82984, 174374, 346048, 653096, 1199384, 2160732, 3812464, 6617304, 11307920, 18978577, 31327104, 51931296, 90400704, 170054336, 341729616, 711634072, 491256624, 84996748, 246978752, 360863368, 970232968, 784743460, 510498224, 166545624, 52102480, 293458982, 360103104, 376725248, 176834992, 275731496, 954496368, 300625128, 414063440, 433951772, 310322560, 249708880, 811887600, 938737368, 864074336, 71770480, 448334368, 690385169, 500412928, 511348096, 358818624, 434524320, 948108160, 468289216, 650489344, 526806528, 302230656, 30608880, 751558192, 753974936, 535251360, 634709584, 25955872, 475657868, 623272896, 157046656, 780889712, 505696136, 184012880, 923143544, 725654512, 179238116, 193093504, 648778256, 195169008, 403948504, 362621408, 864754992, 328296992, 732797990, 909857024, 100434624, 750503552, 294983424, 658676064, 27643600, 820941984, 605847528, 419698560, 33053008, 700157392, 284353768, 173377888, 534200240, 364198816, 612120092, 328301952, 511927808, 765916000, 791204688, 955687520, 494289936, 435348256, 445938776, 748964608, 786203936, 5329504, 811664240, 5235904, 660865504, 340971072, 871030033, 686708224, 267286528, 937673472, 767666048, 539442304, 298792896, 390380672, 372720800, 288230400, 15133824, 425853568, 727404736, 189572608, 59891456, 799414656, 960291328, 113612416, 244620032, 545004832, 798627312, 946809824, 551285200, 544833952, 234031384, 610934016, 354837728, 93055264, 807835472, 10965696, 162396768, 932303552, 52823692, 732816640, 839707584, 49841792, 474600320, 992794336, 588125712, 348645152, 598947016, 325494912, 52194800, 194699248, 141172088, 861231136, 603581200, 753023456, 40378596, 97468800, 918820352, 485205984, 910903824, 638643296, 400297488, 155822624, 403697496, 943586048, 549090720, 294336736, 473898800, 380465856, 449011168, 685336128, 269563942, 38168576, 239393024, 562957696, 973458112, 832738048, 489663616, 497243648, 125980288, 334921984, 12147232, 500452256, 817917648, 527342784, 939825760, 98792128, 617267688, 837879168, 814150400, 775773792, 165143376, 485814816, 591824688, 561589088, 764832360, 623511808, 100080160, 296566240, 855122352, 74772928, 909202272, 177895488, 537422876, 288112640, 821416320, 161867520, 514818560, 473732800, 934477728, 101335360, 348175056, 55250688, 418945312, 149612576, 210908176, 127587264, 549849312, 924159040, 780987480, 451649280, 237824000, 125234624, 975001888, 195767232, 378458528, 503547712, 254463088, 443395072, 286591040, 541436608, 861880800, 479836544, 847018944, 880962176, 554525969, 424632832, 600944128, 723718144, 939867136, 343530496, 102447360, 423660032, 102498688, 432941056, 532155776, 879801216, 83339712, 120469248, 348120960, 857805056, 627426464, 29088768, 55353344, 18714880, 134613120, 827029760, 144271232, 316520704, 690852544, 269748736, 907547648, 651153408, 228088576, 395804416, 511092608, 797881344, 495818240, 779948032, 175160448, 10316544, 497932032, 825706048, 415726048, 107442112, 889617776, 669746432, 814177696, 111243680, 121352144, 514538176, 201625184, 894976320, 121367832, 559719168, 674217472, 731617856, 243881184, 275351872, 453462752, 444249024, 352973392, 276406272, 681023040, 59616448, 203589216, 755607680, 163871040, 138264960, 795041420, 666269696, 856695040, 968040320, 289797568, 106498304, 18414208, 766482944, 37576960, 163313920, 66802848, 210581536, 618699280, 898110400, 638234080, 106440384, 721866952, 41274496, 856897792, 566408992, 583363056, 697223520, 164104464, 403304224, 777345016, 260482816, 113265248, 145095072, 50358544, 6186304, 981862176, 73460928, 414450404, 868483072, 22464896, 538498304, 120805376, 416365504, 237988128, 138046528, 150512528, 710048000, 622539552, 907216416, 373368848, 154506176, 989574112, 636967488, 391317848, 284671744, 893899776, 460700352, 512962976, 613114560, 761463072, 178527296, 99263024, 428680192, 832214080, 95321280, 240288224, 282881408, 852686272, 457263744, 175459366, 786828800, 142502912, 554002944, 237278464, 917246720, 45813376, 132910848, 205309120, 118127616, 617532160, 129750272, 563649152, 537049600, 791844352, 640221952, 309879424, 697511680, 833636864, 751416768, 553640992, 94978112, 628245088, 876532416, 753616848, 189451264, 622135872, 545828800, 505964128, 320717952, 662888512, 641919616, 215155176, 817519104, 884425088, 472105216, 433767680, 977497280, 49989792, 123953984, 519965648, 616946432, 955813984, 895668832, 371680560, 16202560, 941883040, 514595008, 95687784, 317220608, 77707776, 45864896, 664881696, 859485888, 89673760, 345931328, 194959024, 835483648, 594401088, 739508160, 918295904, 83771776, 487197632, 585232000, 780267036, 189414912, 393669632, 65787136, 164059008, 282492928, 757031168, 526655488, 750216960, 147328000, 537648704, 69579584, 581926304, 11365248, 138688704, 50578816, 431849168, 985873664, 19136000, 956960192, 471058208, 229958976, 236602848, 664013248, 811573520, 331145216, 971900224, 543612608, 741343968, 377436544, 40366016, 35149440, 834309720, 162202112, 663868672, 69648896, 213387264, 493090688, 501939776, 385350272, 708991520, 645157376, 478234432, 100312384, 910484896, 92683648, 914066112, 259057792, 813944432, 742197248, 959000064, 14813056, 496663616, 404128128, 805794112, 511393920, 542852576, 742640128, 236958848, 943847808, 480152000, 634774272, 825492352, 199630080, 343462161, 684392448, 774540288, 187437056, 17732096, 49687040, 913434112, 74095616, 877187072, 414193664, 431921152, 192972288, 863458048, 912988672, 215823360, 906795008, 309535616, 46519296, 560357888, 873360640, 215591808, 828457216, 718919296, 578739456, 434788800, 710876672, 488945920, 229635840, 104622976, 819292672, 301387008, 956274688, 696471200, 753969152, 990047232, 956698624, 767802368, 160029696, 640841984, 734804480, 84993664, 179514368, 401547008, 745927424, 992981376, 234452992, 346382592, 655297024, 459830976, 903272960, 278735360, 707682816, 656745472, 530337792, 162754048, 504847360, 274491136, 747104256, 906305792, 814063872, 293868416, 644393984, 590823424, 842058752, 913747968, 148910080, 60902912, 900275456, 118542976, 130709504, 730353920, 869691904, 571679744, 963057664, 71779520, 174352832, 951486944, 927053440, 632602688, 695485568, 70038384, 469481216, 940976640, 263197888, 626695584, 263289920, 568116832, 162415296, 684570832, 736619008, 697940544, 914668992, 278103648, 376080768, 717446336, 365266048, 703640344, 804047360, 118261504, 641732096, 237145600, 147727488, 734355904, 483957632, 955278304, 492067840, 479851968, 279694272, 36902624, 406700672, 859736128, 155624320, 768678992, 537524736, 574381568, 548356480, 508144704, 595361664, 807753024, 984454784, 14146656, 136683520, 390770560, 419688576, 679017792, 188401408, 572954240, 31147264, 815651468, 569578496, 14120960, 123345408, 948904192, 749048576, 974429312, 777620224, 117212096, 302796800, 785054976, 119766272, 238423168, 75894784, 856072192, 215962880, 843505920, 318511872, 644150784, 510240960, 566955168, 812036928, 932414944, 30228928, 437929232, 71840768, 80281920, 839718592, 406735328, 40526464, 859669568, 619708544, 327101128, 68226048, 192608896, 951686912, 698744576, 758039616, 201100768, 229551552, 869691248, 701795584, 118618144, 199506976, 235364112, 840145344, 52297440, 565114944, 385735672, 378791168, 757201408, 214467904, 869376096, 233604672, 654976608, 678859456, 78179344, 734297088, 826256320, 560384832, 637921056, 987870336, 984516416, 138145152, 207502052, 723073024, 782273536, 124333312, 82099072, 232553472, 466232064, 854459392, 227097856, 177174016, 266791744, 735060032, 420847392, 751442304, 642250688, 467839360, 777467280, 74540800, 292105216, 265689536, 514868000, 358282560, 599475168, 653300160, 25309968, 921247232, 472520512, 797515456, 697025504, 734733696, 810961856, 859371648, 703432536, 487481856, 347514624, 691877376, 966082560, 404559744, 712188736, 789792896, 457398944, 850364416, 134146624, 165547584, 398801184, 43731840, 951709120, 901058688, 225528368, 330118144, 438340608, 843833728, 985740864, 723137920, 71549248, 910808704, 703748576, 415727104, 916864128, 380327296, 973509568, 683614976, 596900736, 630078720, 478384166, 520077312, 812687360, 311520256, 661197824, 392231424, 681198592, 390083072, 44190976, 98740224, 295534848, 444491520, 444162688, 320869888, 543096576, 823876096, 435647168, 553824768, 146808320, 494367744, 307879168, 830535680, 285862656, 162650624, 339157632, 116667392, 758773248, 459096576, 451322880, 377856512, 485246208, 330571776, 619593344, 442206720, 348045056, 243344896, 642708480, 827578240, 969969728, 226195584, 73577760, 420483584, 948437184, 689994432, 539851360, 467666560, 102171456, 28185984, 792468432, 153383424, 967058944, 926358912, 386894400, 430878592, 893534784, 480485504, 30883936, 594594304, 852936064, 859709568, 721331264, 727133440, 268454272, 217405696, 803676648, 720716800, 213824000, 884210432, 325693312, 106860032, 846521088, 403214848, 440834048, 411249152, 222949952, 128935744, 840243872, 597857152, 649318592, 893101440, 305637328, 819703040, 950336512, 359628096, 16789600, 468233664, 940455328, 970627904, 50481712, 249043456, 724451776, 106499136, 55441568, 610187904, 363959616, 700918656, 620357736, 485129216, 281701632, 65586688, 797987328, 762008960, 422949440, 743064704, 814888224, 782188032, 659113024, 353922624, 169038368, 102423424, 152668608, 951665280, 599098032, 157979648, 80702976, 760560512, 834796352, 523901824, 321384512, 322573952, 248528224, 299880448, 70675072, 504798592, 370787264, 106193152, 198931840, 269195008, 555726364, 448803328, 753762304, 516976640, 404776448, 468888576, 773287680, 264293376, 754597248, 894410240, 49873920, 37513216, 186436352, 302988800, 120015360, 308415488, 447404288, 807384064, 776774144, 581223296, 966903872, 679505536, 272790208, 642709888, 217814432, 477240320, 822003840, 71439232, 709545664, 459470592, 884127360, 721338624, 149220048, 908627968, 797781760, 356526080, 622006784, 140852608, 905517120, 760461440, 982585376, 929006592, 332853184, 764667840, 412086752, 405849728, 817640512, 456524160, 466256144, 107839488, 387357184, 505990016, 903756096, 388368256, 588523840, 184448128, 656833760, 607778816, 910468224, 313700224, 118308800, 439292672, 725408128, 493056768, 857356376, 385496064, 846945280, 534321152, 18385152, 449134080, 841249792, 502099968, 172350976, 469531136, 686674560, 556696192, 300498496, 63742720, 676667776, 46763264, 663933984, 884857344, 996736000, 524261248, 301037888, 691750528, 888102080, 214663040, 669878688, 752066048, 823083136, 501103488, 136911552, 608109824, 613112704, 734673664, 175466608, 256510464, 542642176, 602698752, 547961344, 583782144, 740052096, 645433600, 723196992, 500193792, 69721216, 958372992, 898824000, 377954560, 434157440, 480942336, 519999456, 595795456, 982915584, 773418752, 676557440, 481737984, 575989888, 17395456, 853862848, 339638272, 6952704, 106125056, 540361088, 391682048, 942466304, 549112832, 198298385, 251279872, 978163200, 131404800, 780035584, 740944896, 374855680, 403911168, 963103232, 848214016, 744768000, 893798400, 955546112, 498280960, 949625856, 135431168, 402078720, 307565568, 663347200, 789044736, 835772928, 879969792, 824732160, 126530560, 631782656, 299908608, 594232320, 367850496, 235840000, 996408832, 960724480, 778310656, 817758080, 918313472, 875264000, 797228544, 867886080, 191902208, 924208896, 487904768, 840755072, 245379584, 695137024, 412046592, 910054016, 511005696, 888600832, 921495040, 647691712, 338329600, 905242624, 854643712, 471933184, 256710144, 830233856, 932033024, 5909888, 75062784, 38045696, 859802624, 596451584, 957753856, 238868992, 444895232, 940039840, 85631488, 947264512, 558288384, 925790208, 992448000, 128988160, 273187328, 727951360, 538970624, 744160768, 475745280, 245623040, 718452736, 969947136, 397848064, 502058624, 806852608, 530469376, 4609536, 601513728, 181294080, 552173312, 952832000, 718521216, 479221760, 872718848, 589416960, 441738496, 426259968, 322993152, 636653568, 190523584, 61834752, 316647936, 177546240, 669971968, 348308480, 41042432, 655103488, 125173760, 736324096, 908726272, 168775680, 215891456, 565922304, 58951168, 911216128, 119341824, 864381952, 675119616, 719565824, 687661824, 734852096, 41902848, 808102400, 1787264, 8833536, 338338304, 160024576, 305699328, 901613056, 26177536, 749109248, 925389824, 557708800, 520852480, 593444864, 413071360, 209221120, 668766464, 909933056, 334722176, 321958912, 579092480, 162772480, 97689856, 923604992, 629277696, 234935296, 764150272, 457857536, 203662336, 594473600, 138583232, 307621248, 982892096, 589286528, 277723616, 390486528, 810851712, 51940480, 303782976, 45183744, 550263168, 483811072, 195303280, 119749120, 574497536, 593632256, 991963648, 32035712, 793886528, 598907008, 595899552, 504306688, 499808960, 789107904, 82246752, 797953152, 698087744, 64924032, 846810320, 424435200, 131104768, 205808000, 72249920, 148056448, 423743552, 85042816, 695403616, 695830016, 19596928, 341289856, 796560576, 379421440, 335520128, 195054336, 704614168, 642138112, 230093824, 342317056, 306277632, 491163136, 930551296, 139185664, 291079168, 951294464, 576725376, 662002048, 67040704, 185062144, 684440704, 574852864, 888090592, 157330432, 643423232, 759924352, 173400000, 981882752, 225019456, 532120704, 147509984, 372774400, 558156672, 894177920, 15067712, 897618688, 145015936, 538948352, 607958608, 767561216, 983854592, 903601152, 810712576, 90144000, 484501632, 56298752, 174846528, 910349824, 558624384, 31890560, 543184704, 235227392, 449014656, 991555328, 206097504, 707127296, 678084096, 632197888, 237356416, 315691264, 58617216, 95574272, 633150272, 198662656, 511840000, 633450752, 308191360, 744441344, 420291328, 609421312, 213727372, 418232832, 330982400, 297607168, 242733056, 49508864, 698092544, 64388608, 814588160, 850490368, 435156224, 55835392, 450840704, 652748288, 447272192, 679689728, 54665664, 709251584, 653165056, 247575552, 855688960, 776396288, 524512000, 524048896, 671064704, 708572672, 258202112, 635902976, 502130176, 903303168, 344168192, 332860416, 614447872, 48197632, 564505344, 222031360, 837139456, 54552448, 968858432, 449464448, 889658784, 431080960, 858372544, 406992832, 238396896, 1482368, 100144704, 396498304, 591484688, 292044288, 570484736, 686136704, 629417280, 941257088, 530505536, 152413824, 951675360, 802113024, 609926016, 291078272, 901245504, 354386176, 482843520, 451800832, 795176136, 433234944, 634102272, 304251136, 874937472, 479594496, 559004928, 315874304, 926226944, 257581568, 530704576, 417822144, 162339296, 316627072, 605007936, 214972032, 664299376, 725006080, 668520960, 120267712, 860707360, 421309760, 707513824, 147533760, 812344848, 302326272, 816060224, 624141504, 348091104, 24598400, 547572160, 539784832, 197346296, 681633280, 235787520, 133547008, 732269568, 228829824, 173386944, 605187968, 492429152, 552549376, 607023296, 332226240, 655014496, 696946304, 666481984, 21369728, 10020368, 474648576, 91253248, 224895616, 362547136, 399351424, 599795392, 680883584, 170518304, 760406528, 445593472, 763751552, 578881856, 916736768, 539572352, 474755840, 166917348, 421041152, 911228416, 693057024, 899704832, 203149824, 973010688, 682167808, 566382976, 863071744, 711179776, 592270336, 309645056, 233421824, 241110016, 784763392, 738319616, 307573248, 510190592, 717804928, 426880832, 955829376, 400434112, 801482624, 270326048, 27236352, 136935552, 602000768, 788431296, 200506624, 467494528, 42714368, 367655312, 947847680, 361170688, 484621824, 2085888, 37392768, 653101632, 220564096, 378869280, 470525952, 481334208, 629160384, 902842848, 438480000, 838447680, 270136192, 400181008, 106477568, 668388352, 130893696, 266921792, 438955392, 834522944, 408712320, 508784608, 398375936, 115690624, 794238336, 262317504, 260312832, 526865792, 497185536, 934100312, 148880896, 205977600, 102093824, 809536768, 768175616, 723458560, 733164544, 395912192, 402212864, 975103616, 923443840, 507202368, 553068800, 911500672, 601630464, 818858144, 323253248, 471847424, 417110912, 478811200, 522981504, 157177792, 57517440, 579973920, 481325568, 591278720, 986792320, 530477504, 206776064, 782827392, 437857536, 176555568, 357619200, 725770240, 296582144, 409870336, 941205760, 168341120, 107143424, 976410176, 629061632, 968430720, 30416000, 88745280, 568711424, 288231296, 36830976, 353853920, 112779776, 989328896, 923513600, 985306240, 218662656, 417857664, 502609664, 603901376, 635292672, 874040064, 745810176, 368704384, 212393984, 919779072, 87492608, 377158182, 295789056, 80340480, 800179200, 971070464, 876719104, 956875776, 266336256, 583073792, 398030848, 280086016, 650089984, 992693760, 636087296, 468796416, 849301504, 205779200, 334051328, 477336576, 759994368, 189933312, 648415744, 741816064, 663376384, 713056896, 746219520, 171194880, 725726720, 51969280, 763445760, 214868992, 697226240, 373204160, 731453952, 507233280, 398911488, 310717440, 322465280, 835845632, 363455488, 272982272, 263134720, 542450688, 799467008, 663054080, 750390272, 776073216, 243121664, 523471488, 959777280, 191944704, 90347008, 846558208, 6282752, 8944128, 924731392, 391406080, 195031552, 529341440, 440991232, 408499456, 540343296, 711432704, 848566784, 753333376, 303007744, 368977408, 679374336, 286542080, 516243456, 766500352, 929061888, 41552896, 581041664, 440798336, 970624128, 408701504, 141632768, 898931072, 530598144, 963776288, 661315072, 696642560, 729239680, 512637632, 915944320, 166155584, 264791680, 766517856, 319129600, 172453760, 834195584, 874432832, 884389120, 788534912, 221491968, 421570512, 248349696, 491539968, 253037056, 126955520, 502301952, 264732800, 816446208, 712006720, 133810176, 154518144, 772846208, 747420224, 28620544, 937528704, 262700800, 655269472, 252593664, 158245888, 718437632, 953519488, 292889856, 174435200, 683014400, 199580224, 922116608, 699674368, 91475200, 280542080, 584185344, 125067520, 492534784, 975734760, 605728768, 98478080, 954412544, 975158272, 75299328, 163292928, 264378880, 40400768, 265237504, 978938368, 491446272, 541013248, 706933248, 503625216, 327619072, 604149248, 847922688, 9202688, 45069696, 34049088, 297400448, 630849728, 961768320, 950080672, 189283328, 318591104, 319880576, 288065728, 994247936, 818439808, 205515008, 960798160, 183618560, 756876032, 730000384, 208776704, 442096768, 242948800, 719447936, 364958048, 932557824, 867328320, 722336064, 104140192, 969035136, 407487168, 230151296, 726195760, 265541120, 827908608, 832877184, 598496704, 919218304, 266684864, 440407424, 800477856, 713524736, 841051520, 149512832, 339745088, 876758784, 212937856, 179845888, 418657896, 891757568, 434445312, 603107840, 996230912, 991027712, 319219712, 789462528, 809727488, 438623744, 361802368, 402953856, 560843328, 922624256, 345935744, 411612416, 274835744, 814255104, 347456000, 799476608, 387845184, 392003712, 406330816, 934704512, 383555104, 494846464, 361687680, 727488384, 973417920, 562522880, 672754048, 901122304, 503024816, 966638080, 400665088, 718730240, 683328512, 64534272, 611022976, 288919808, 97897280, 619404800, 900825216, 160354432, 551548992, 855790848, 708060544, 801157888, 761839968, 463570944, 28562432, 525449984, 345727616, 336184576, 371381376, 269362432, 822261184, 469729792, 446334208, 118955776, 165092224, 906804736, 575332096, 721893376, 195203100, 656048640, 992351744, 678120448, 494240768, 312379904, 314698752, 189934592, 413699584, 127036928, 367881216, 284724736, 400044800, 747264000, 73478656, 708388352, 691775360, 609853952, 942381568, 443718144, 790965248, 860050432, 635853312, 94294528, 26983168, 981454336, 838593024, 94950400, 579395072, 964016640, 521440768, 507771904, 238485760, 204137472, 570467328, 639428608, 263133184, 135474432, 950348928, 260976384, 567193152, 574227968, 318889344, 213579136, 753051328, 607396096, 762947200, 709543680, 971887008, 261024768, 450968576, 812330240, 436369024, 573191936, 933427840, 777132800, 373361856, 73200640, 680160000, 629599488, 577936000, 618623488, 688752384, 834718720, 680995024, 398040576, 554630656, 602520064, 469838592, 472791040, 753539584, 363307008, 313992192, 346926080, 154497664, 571817600, 781840960, 159548672, 877128576, 734954752, 364488736, 241363968, 938322432, 296274560, 132733376, 583035776, 655920192, 859126400, 666910688, 290717696, 969259392, 571325568, 719875136, 903406848, 896596096, 776673536, 861938960, 396892672, 554260480, 152518144, 320519680, 162437376, 170958976, 220110080, 924746048, 313070080, 280710784, 83296384, 626323776, 718082816, 513799040, 451358464, 644492512, 953931264, 47220736, 992205568, 619687040, 157289728, 708247168, 618055936, 329575360, 245748224, 332708608, 393857792, 282962816, 147730432, 569485056, 519490048, 525295704, 561701888, 689703424, 735651328, 515330048, 45641216, 753129984, 271665152, 465690368, 777958912, 236824576, 546201600, 585107968, 59947008, 265226752, 941522432, 711974400, 815492096, 739075072, 919684864, 415575680, 697939712, 834947456, 837725440, 217309760, 62121984, 739012352, 618061568, 120652672, 196350464, 93733632, 131336704, 87854624, 165698560, 328298496, 253822976, 812825600, 464424704, 869402752, 531066624, 59296576, 739339776, 39300480, 532935552, 410261184, 259377408, 135896704, 214601472, 591295392, 136937984, 53500416, 258551040, 416292480, 735014144, 8911488, 757315840, 264662208, 289253376, 564188928, 998338816, 708933504, 749543936, 610444544, 861304832, 316877424, 720907776, 133031424, 280160256, 624125952, 901776896, 433760768, 104350208, 585502208, 281776128, 94161152, 586106624, 170612352, 464560128, 77732096, 191088640, 8735808, 696024064, 327518208, 964067072, 199530624, 127491328, 112724864, 400975616, 550516544, 304968192, 404084480, 263965952, 60905856, 426164224, 451088640, 858235904, 769599456, 500110848, 787713536, 815852032, 224214016, 964701184, 124444416, 52596224, 99283072, 655768064, 535163648, 316451584, 389630080, 317510656, 282112768, 118462976, 641919424, 776924160, 382193664, 530681856, 260371712, 27118080, 958639360, 495328256, 148628352, 956046336, 679448576, 662698496, 984233216, 362857984, 918642688, 978923520, 45725969, 600631808, 441119232, 712744448, 687369216, 345545216, 738495488, 998056448, 593305088, 627006976, 269536768, 728878080, 429721600, 846814720, 145928192, 379458560, 902239232, 337814016, 248363520, 773329920, 215181312, 300692480, 435977728, 387620864, 863454720, 206284288, 566544384, 128536064, 638379008, 512051712, 960489984, 762293248, 756831232, 900768768, 746795520, 817834496, 953074176, 229020160, 633916928, 648155648, 235197952, 407905792, 937214464, 662357504, 867061760, 465940992, 672636416, 547040256, 302352640, 568244224, 310017024, 815878656, 702142464, 628976640, 456087552, 81750016, 39520768, 642970112, 429342208, 53346816, 706868224, 439266304, 637666816, 108447744, 827859840, 521216512, 959307264, 310456832, 699905536, 166579712, 451591168, 356686848, 796062208, 682716672, 236249600, 108169216, 19299072, 264425472, 287152640, 652585472, 469738880, 476498432, 896770048, 651430912, 526946048, 447594496, 56027904, 520520704, 696013952, 189850112, 179561472, 634071552, 70737664, 589986816, 641028608, 874984448, 618939840, 557532672, 322344960, 461051392, 476892160, 770281472, 306243584, 841111040, 445796608, 300641792, 148939264, 791479808, 349592320, 457962496, 853110784, 584118272, 116817792, 801864192, 407178752, 725947392, 72524800, 597056512, 229395456, 148515840, 68755200, 910711296, 470337536, 408402432, 618152448, 401264128, 181604352, 770232320, 662893728, 93979136, 418102784, 919132672, 999239680, 383539712, 28984832, 779949568, 646873600, 754230272, 274492416, 695634944, 143741952, 462935040, 110188544, 154374656, 272718336, 623735808, 301778432, 165934080, 710259200, 28964352, 57256960, 505480704, 131852032, 844490752, 992847360, 921733632, 822233088, 811573760, 91862528, 905390592, 683906176, 730952704, 614386176, 790963712, 864616960, 124535808, 669196800, 520323584, 469790976, 750585344, 6202880, 39457792, 189067008, 698889728, 561252352, 470395904, 243386752, 91910144, 479022080, 869242368, 739469824, 688594432, 309297664, 8306176, 479336704, 875679232, 890317824, 891805696, 769587712, 389033984, 989570048, 140310528, 254932160, 606104064, 664675840, 492294144, 680334336, 349319680, 595630592, 464013312, 46551552, 166360576, 257161728, 311820288, 464402944, 133968384, 743232512, 574310400, 874359296, 566200320, 984909824, 897721344, 955375104, 808748032, 637142528, 282401280, 928114688, 336946688, 957867008, 139785728, 662847488, 596903424, 228315136, 156258304, 878077184, 28847104, 885765632, 760316416, 968053248, 869664768, 781483008, 215681024, 324171008, 348280832, 41165312, 941573632, 527083264, 878424576, 529836544, 150603776, 132073344, 241230336, 984546304, 93100544, 670551040, 648300032, 470994432, 858387456, 35365888, 194914304, 934809088, 454004736, 382642688, 866464256, 248793088, 723158016, 470871552, 596681728, 903578112, 25894400, 745580544, 355539968, 230439424, 447189504, 913591296, 359497728, 752130048, 647930368, 346501888, 44998656, 426048512, 28057600, 973791872, 81201664, 964327424, 500604416, 556003840, 197318144, 334988800, 93826048, 630611712, 232521216, 933284352, 958054400, 854402560, 651157504, 986608128, 124938752, 527035904, 226854912, 871733760, 820864000, 371097600, 841863936, 849033088, 947840256, 123458752, 826224128, 211906688, 676458624, 382227008, 649128192, 841700736, 925253888, 409587680, 415344640, 524428288, 821942016, 660289408, 548911360, 956645760, 476539136, 670195264, 475385344, 849265920, 75157760, 220624256, 119029760, 565260032, 1269248, 522678640, 95025664, 924598272, 816328192, 383456000, 500352000, 13445632, 787862528, 9814528, 966151168, 622356608, 383707776, 562245952, 365556992, 342387072, 465975552, 410475680, 559935488, 670368256, 899585152, 452270272, 126083456, 747622720, 48611968, 472442976, 247122432, 541267328, 584737920, 217861440, 490587392, 539696768, 29469440, 434195152, 127029760, 685178880, 7587840, 576200192, 916525824, 546230912, 916265728, 528016448, 864370688, 585461376, 850749056, 951581760, 550288640, 756234624, 219976448, 504044640, 153527808, 277952512, 966655744, 903029888, 682498304, 89237120, 938263808, 314541248, 429138944, 589603584, 688667392, 931366272, 309328896, 873974016, 241871360, 628107544, 352574976, 464851968, 599418880, 200868864, 981737984, 271870976, 561503232, 27953920, 705192448, 600979968, 829291008, 273163776, 771334656, 848713216, 837473792, 918645248, 339310080, 851380736, 80507136, 452322688, 67438848, 865291392, 539296512, 727887808, 161593344, 926811904, 490044672, 9809024, 785315328, 481782528, 524446208, 433809376, 933978112, 952124416, 26363392, 579133440, 130230528, 442642304, 429175552, 901530560, 123713536, 460816512, 481012352, 80317504, 332288768, 35947904, 752042752, 916268768, 100037632, 691210240, 54513920, 449915264, 438890240, 878845312, 92506880, 429628992, 644466688, 392143104, 854730496, 414419584, 686224384, 641384192, 803920384, 371604560, 51350016, 431191040, 31232, 88910848, 668491776, 157191680, 987325952, 700615680, 338861568, 667858688, 754667264, 42974336, 22034432, 756654848, 64261120, 728988224, 130342400, 693551616, 837363968, 190769280, 314290944, 728204672, 406462208, 593738048, 103480320, 142993152, 761336064, 754766720, 333393920, 855689472, 482043392, 723997280, 358390784, 349416960, 293483520, 475947008, 496176128, 179980544, 345876992, 617129344, 226380288, 842460416, 390465280, 498862976, 296728576, 444841216, 394548736, 148277568, 349194752, 74371072, 540454400, 979572480, 197366784, 81612032, 425664000, 599762048, 22398976, 340777984, 189064704, 105777408, 379544576, 496028672, 341877248, 957625484, 682391040, 647912448, 201170944, 241286144, 839063040, 112410624, 826003968, 349751808, 850998272, 493180416, 642105856, 121459200, 479954432, 727409664, 194192384, 273983744, 483161600, 436433920, 874522112, 995901184, 459346944, 147593472, 247043584, 741600896, 715802624, 808643584, 267048448, 344112896, 505513472, 725780992, 677786112, 450789312, 605686272, 590819840, 101075456, 258637312, 776445440, 456084480, 739875840, 626267904, 580727808, 625658880, 71345152, 973636352, 875730432, 300998656, 940276224, 518047872, 564911616, 410867712, 150529536, 193974272, 169203712, 732767232, 125257216, 436736000, 295628800, 955421696, 256390144, 414858496, 711473152, 845818368, 897109504, 414506240, 291777024, 547145728, 350711296, 108229376, 165619712, 213861376, 341335552, 100908032, 446239232, 553678464, 924893312, 397113664, 800651520, 513961344, 825702144, 869052320, 558251520, 733744128, 846766208, 309285824, 221472640, 265324608, 563602048, 527059424, 928914432, 709900160, 440006784, 511588416, 449731328, 767088768, 136154368, 63571216, 967133696, 770959360, 565337600, 999996928, 59461376, 40397440, 243449600, 921946944, 412673024, 594866304, 184452224, 491085632, 359162112, 653215616, 996061440, 273238496, 620796416, 906457600, 948005632, 324208512, 700975360, 535070592, 456647936, 72185408, 654392832, 7637248, 354759424, 653582720, 309523456, 499069184, 133221888, 200973512, 771273216, 216885248, 718820864, 44144128, 530051584, 74548480, 839918080, 810034816, 563384832, 452018688, 953555456, 309269248, 186791424, 837428224, 605263872, 174372352, 295547392, 960648704, 464693888, 926963392, 588819328, 866755136, 778783872, 397602272, 566067712, 429303168, 774071424, 438130240, 252018944, 408703360, 480455424, 804992880, 563590656, 799135488, 871728640, 883459584, 524152192, 829070912, 389310592, 786785568, 542966272, 931771840, 105958336, 554044384, 455101568, 593057856, 827862912, 655786000, 40588800, 880224256, 499835776, 214562624, 784434560, 598171456, 265058432, 902991584, 808576000, 124789376, 254443392, 880455616, 419827968, 819384704, 173022464, 977816056, 483427840, 733403136, 459196928, 959673600, 96271872, 341490688, 323502080, 781707264, 294026240, 686701952, 909245824, 226745536, 145802496, 69285504, 473622272, 422845792, 931038720, 745667072, 860331136, 234584768, 129416576, 43021120, 846159488, 730653792, 45962752, 357743488, 240149120, 703181120, 16932608, 12555904, 974220032, 430947344, 880302592, 646883328, 840555520, 731497472, 857457920, 462929792, 427653376, 549248448, 703565824, 273405824, 164824960, 558517440, 615185152, 879020672, 838196992, 747534624, 953359360, 240090112, 14135552, 333328256, 144485632, 925268864, 573876992, 768310592, 927727104, 552495360, 825717504, 285531264, 564803072, 753040640, 725511680, 211294948, 595539456, 844576256, 723471872, 111536128, 500495360, 270169088, 722566656, 756769280, 873398784, 909309952, 90144256, 611474176, 861094400, 687091712, 330394112, 244915072, 485852160, 224509440, 938093568, 414407168, 557349376, 721602560, 473491968, 713867520, 51100672, 532337664, 189061632, 684388864, 553750528, 797197824, 555892736, 266365696, 478139392, 595224064, 674425856, 181094912, 963950848, 550185600, 543424256, 872956736, 852359168, 496602496, 16786816, 623034304, 915923712, 363704448, 434648320, 454770976, 116569600, 414142464, 563106560, 635202688, 242013952, 9527424, 844477184, 230813632, 325934080, 698525440, 59300096, 398042752, 244669952, 966939904, 613185536, 99074448, 190259200, 697553920, 392414720, 38216448, 934643712, 847104000, 531427840, 83562496, 50496512, 673165952, 300613760, 268184640, 235516160, 627867008, 852495104, 641548832, 742511104, 138265088, 41801344, 476522944, 215939456, 441673792, 577318016, 921603552, 640115200, 623278976, 794460288, 32261696, 212803328, 222643840, 361693440, 304497424, 763894784, 348738560, 741879296, 956550144, 256653568, 209056896, 744272640, 876776256, 584072704, 692315776, 813101696, 335977792, 111034112, 150518656, 890609920, 933139424, 611127808, 885211648, 558527744, 193053312, 665765632, 605200512, 464855808, 923960256, 497188352, 998764800, 706331392, 784904064, 734484480, 384455936, 193083904, 678420312, 896372224, 202094592, 251539968, 455005696, 302971904, 432368640, 717877760, 313457920, 397130752, 296763392, 12879360, 325554688, 811761152, 947457536, 412841472, 515364864, 446125056, 647041024, 928193280, 359932032, 729489664, 470577024, 422805248, 624065856, 289844224, 234522368, 291803904, 553447808, 142352896, 826876160, 757957632, 216532640, 282544128, 102835200, 311161856, 658576384, 820694272, 646446208, 390644480, 124089920, 60406784, 848877952, 849304960, 959909312, 832173824, 862279296, 892250368, 969198368, 908113920, 110174720, 795565824, 580301952, 941383424, 890795136, 182357248, 288855488, 411004416}; 5  6 inline int read() { 7     int x = 0; 8     char ch = getchar(); 9     while (ch < ‘0‘ || ‘9‘ < ch)10         ch = getchar();11     while (‘0‘ <= ch && ch <= ‘9‘) {12         x = x * 10 + ch - ‘0‘;13         ch = getchar();14     }15     return x;16 }17 18 int main() {19     int n;20     while ((n = read()) != 0)21         printf(n >= 38 ? "%09lld\n" : "%lld\n", ans[n]);22 }