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
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define deb(x) cerr << x << ' '

const int N=20;
int T[N];
unsigned long long DP[N][2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, i;
    string s;
    cin >> s;
    n=s.size();
    for(i=0; i<n; i++)
        T[i]=(int)(s[i]-'0');
    
    DP[n][0]=1;
    for(i=n-1; i>=0; i--)
    {
        DP[i][0] = (T[i]+1)*(DP[i+1][0]+DP[i+1][1]);
        if(DP[i][0]<0)
            cout << "ups";
        if(( i<n ) && ( (T[i]*10+T[i+1])>9 ) && ( (T[i]*10+T[i+1])<19 ))
            DP[i][1] = (19-10*T[i]-T[i+1])*(DP[i+2][0]+DP[i+2][1]);
        if(DP[i][1]<0)
            cout << "ups";
    }
    cout << DP[0][0]+DP[0][1] << '\n';
    return 0;
}