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
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin

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

	long long n;
	cin >> n;
	string in;
	while(n) {
		in += char('0' + n % 10);
		n /= 10;
	}
	in += "--";
	reverse(in.begin(), in.end());
	map<string, int> ways;
	for(int i = 0; i < 19; ++i)
		ways[to_string(i)] = max(0, 10 - abs(i - 9));
	vector<long long> dp(size(in), 1);
	for(int i = 2; i < size(in); ++i)
		dp[i] = dp[i - 1] * ways[string() + in[i]]
			+ dp[i - 2] * ways[string() + in[i - 1] + in[i]];
	cout << dp.back();
}