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
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using ll = long long;


constexpr ll options(const ll n)
{
  if (n < 10) return n + 1;
  else return std::max(19 - n, 0ll);
}


ll solve(std::string const& num_str)
{
  std::vector<ll> number(num_str.size());
  std::transform(std::begin(num_str), std::end(num_str),
                 std::begin(number), 
                 [](char x) -> ll { return x - '0'; });

  std::vector<ll> partial(number.size() + 1, 0);
  partial[0] = 1;
  partial[1] = options(number[0]);

  for (int i = 1; i < number.size(); ++i) {
    ll nx = number[i - 1] * 10 + number[i];
    partial[i + 1] = options(number[i]) * partial[i]
                   + (nx >= 10 ? options(nx) * partial[i - 1] : 0);
  }

  return partial.back();
}



int main()
{
  std::ios::sync_with_stdio(false);

  std::string number;
  std::cin >> number;

  std::cout << solve(number) << std::endl;
  return 0;
}