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
#include <iostream>
#include <string>
#include <algorithm>

#define DEBUG(n) //cerr<<n

using namespace std;
typedef long long LL;

int inline num(char ch) {
	return ch-'0';
}

LL inline comb(int num) {
	DEBUG("comb("<<num<<") = "<<num+1<<endl);
	return num+1;
}

LL inline comb2(int num) {
	DEBUG("comb2("<<num<<") = "<<(9-num)<<endl);
	return (9-num);
}

int main() {
	ios_base::sync_with_stdio(0);
	string wyn;
	cin>>wyn;
	//iterating from the end
	LL wyn1 = 1;
	LL wyn2 = 1;
	LL curWyn;
	char lastCh = 0;
	for(auto iter=wyn.rbegin(); iter!=wyn.rend(); ++iter) {
		char ch = *iter;
		curWyn = 0LL;
		if(ch=='1' && lastCh)
			curWyn += comb2(num(lastCh)) * wyn2;
		curWyn += comb(num(ch)) * wyn1;
		wyn2 = wyn1;
		wyn1 = curWyn;
		lastCh = ch;
		DEBUG("ch " << ch << " -> wyn = " << curWyn << endl);
	}
	cout<<curWyn;
	return 0;
}