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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxExp = 18;
ll n, powers[maxExp + 4], ans[maxExp + 4], possibilities[104];
const bool deb3 = 0;

int getDigit(int exp, int length)
{
	if(length > exp + 1)
		length = exp + 1;
	
						if(deb3) printf("getDigit %d %d   -->   %lld / %lld = %lld\n", exp, length,
						(n / powers[exp - length + 1]),  powers[length], (n / powers[exp - length + 1]) % powers[length]);
	
	return (n / powers[exp - length + 1]) % powers[length];
}

int main()
{
	powers[0] = 1;
	for(int i = 1; i < maxExp + 1; i ++)
		powers[i] = powers[i - 1] * 10;
	
	for(int i = 0; i < 10; i ++)
		possibilities[i] = i + 1;
	for(int i = 10; i < 19; i ++)
		possibilities[i] = 19 - i;
	
	scanf("%lld", &n);
	
	ans[0] = 1;
	for(int l = 1; l < maxExp + 1; l ++)
	{
		ans[l] += ans[l - 1] * possibilities[getDigit(l - 1, 1)];
		if(l > 1 && (getDigit(l - 1, 1) == 1)) ans[l] += ans[l - 2] * possibilities[getDigit(l - 1, 2)];
							if(deb3) printf("ans[%d] = %lld\n\n", l, ans[l]);
	}
	
	printf("%lld\n", ans[maxExp]);
}