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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;

#define int int64_t

const int64_t mod = 1e9+7;
const int maxn = 1e6+10;
int inf;


/*
case:
1. a[i] + b[i] = c[i]
2. a[i] + b[i] + carry = c[i]

dp[i][0/1] = ile jest poprawnych początków dla spójnego podciągu kończącego sie w i z danym carry

ans = suma po dp[i][0]
*/

string as, bs, cs;
char ac[maxn];
char bc[maxn];
char cc[maxn];
int a[maxn];
int b[maxn];
int c[maxn];
int dp[maxn][2];
int n;

void tc()
{
    cin >> as >> bs >> cs;
    n = as.length();

    for (int i = 1; i <= n; i++)
    {
        ac[i] = as[i-1];
        bc[i] = bs[i-1];
        cc[i] = cs[i-1];
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = ac[i] - '0';
        b[i] = bc[i] - '0';
        c[i] = cc[i] - '0';
    }

    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = dp[i][1] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] + b[i] == c[i])
        {
            dp[i][0]++;
        }
        if (a[i] + b[i] + 1 == c[i])
        {
            dp[i][1]++;
        }

        int carry = (a[i] + b[i]) / 10;
        int last_digit = (a[i] + b[i]) % 10;
        if (carry == 0 && last_digit == c[i])
        {
            dp[i][0] += dp[i-1][0];
        }
        if (carry == 1 && last_digit == c[i])
        {
            dp[i][0] += dp[i-1][1];
        }

        carry = (a[i] + b[i] + 1) / 10;
        last_digit = (a[i] + b[i] + 1) % 10;
        if (carry == 0 && last_digit == c[i])
        {
            dp[i][1] += dp[i-1][0];
        }
        if (carry == 1 && last_digit == c[i])
        {
            dp[i][1] += dp[i-1][1];
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += dp[i][0];
    }
    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	inf = numeric_limits<int>::max()/2;

    int T = 1;
    //cin >> T;
    while (T--) tc();

    return 0;
}