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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <string>
#include <array>
#include <cstdint>

using namespace std;
typedef array<array<int, 9>, 9> Comp;
typedef array<int64_t, 9> A9;

Comp precompute()
{
	array<array<int, 9>, 9> comp{};
	for (int f = 0; f < 9; ++f)
	{
		int f0 = f % 3 - 1;
		int f1 = f / 3 - 1;
		int F[2] = { f0,f1 };

		for (int g = 0; g < 9; ++g)
		{
			int g0 = g % 3 - 1;
			int g1 = g / 3 - 1;
			int G[2] = { g0,g1 };

			int h0 = -1, h1 = -1;

			for (int x = 0; x <= 1; ++x)
			{
				int y = G[x];
				int hx = y < 0 ? -1 : F[y];
				if (x == 0) h0 = hx;
				else h1 = hx;
			}

			comp[f][g] = (h0 + 1) + 3 * (h1 + 1);
		}
	}
	return comp;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Comp comp = precompute();

	string A, B, C;
	cin >> A >> B >> C;

	A9 cnt{}, nxt{};
	int64_t ans = 0;

	for (int i = 0; i < A.size(); ++i)
	{
		int a = A[i] - '0', b = B[i] - '0', c = C[i] - '0';
		auto vfc = [&](int carry) -> int
			{
				int s = a + b + carry;
				if (s % 10 != c) return 0;
				return 1 + s / 10;
			};
		int e = vfc(0) + 3 * vfc(1);

		nxt.fill(0);
		nxt[e] += 1;

		for (int f = 0; f < 9; ++f) if (cnt[f]) nxt[comp[f][e]] += cnt[f];
		cnt = nxt;
		ans += cnt[1] + cnt[4] + cnt[7];
	}
	cout << ans << endl;
	return 0;
}