1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>

long long apb(char *n, long long *c)
{
    long long r = 0LL;

    if (!*n)
        return 1LL;

    if (*c >= 0)
        return *c;

    if (*n == '1' && n[1] && n[1] < '9')
        r += ('9' - n[1]) * apb(n + 2, c + 2);

    r += (*n - '0' + 1) * apb(n + 1, c + 1);

    *c = r;
    return r;
}

int main(void)
{
    char n[20];
    long long c[20];

    scanf("%s", n);
    memset(c, -1, sizeof(c));
    printf("%lld\n", apb(n, c));

    return 0;
}