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
#include<iostream>
#include<map>

std::map<long long int, long long int> cache;

long long int singleDigitCombs(int c) {
	if(c < 0 || c > 18) return 0;
	return 10-abs(c-9);
}

long long int sumCombinations(long long int current) {
	if(current == 0) {
		return 1;
	}
	std::map<long long int, long long int>::iterator it = cache.find(current);
	if(it != cache.end()) {
		return it->second;
	}
	int dbl = current % 100;
	int sng = current % 10;
	int dblCmbs = (dbl > 9) ? singleDigitCombs(dbl) : 0;
	long long int val;
	if(dblCmbs > 0) {
		val = dblCmbs * sumCombinations(current / 100) + singleDigitCombs(sng) * sumCombinations(current / 10);
	} else {
		val = singleDigitCombs(sng) * sumCombinations(current / 10);
	}
	cache.insert(std::pair<long long int, long long int>(current, val));
	return val;
}

int main() {
	long long int number;
	std::cin >> number;
	printf("%lld", sumCombinations(number));
	return 0;
}