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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=1e6+5,P1=1e9+7,P2=998244353;

int n,pw1[N],pw2[N],h1,h2;
char s1[N],s2[N],s3[N];
map<pair<int,int>,int> mp;
ll ans;

int main(){
    scanf("%s%s%s",s1+1,s2+1,s3+1),n=strlen(s1+1);
    for(int i=pw1[0]=1;i<=n;i++)pw1[i]=pw1[i-1]*10ll%P1;
    for(int i=pw2[0]=1;i<=n;i++)pw2[i]=pw2[i-1]*10ll%P2;
    mp[make_pair(0,0)]++;
    for(int i=1;i<=n;i++){
        int x=(s1[i]-'0')+(s2[i]-'0')-(s3[i]-'0');
        h1=(h1+(ll)(P1+x)*pw1[n-i])%P1,
        h2=(h2+(ll)(P2+x)*pw2[n-i])%P2;
        pair<int,int> w(h1,h2);
        ans+=mp[w],mp[w]++;
    }
    printf("%lld\n",ans);
    return 0;
}