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
from collections import Counter

A = input().strip()
B = input().strip()
C = input().strip()
n = len(A)

primes = [140829051131, 14047678884195893, 424975516199991, 61007777057, 1057740279991]

c = Counter()
c[(0, 0, 0, 0, 0)] = 1
mults = [1] * len(primes)
prev = (0,) * len(primes)
for i in range(n-1, -1, -1):
  diff = int(A[i]) + int(B[i]) - int(C[i])
  key = [(prev[p] + mults[p] * diff) % primes[p] for p in range(len(primes))]
  # print(f"{i=}, {diff=}")
  key = tuple(key)
  for p in range(len(primes)):
    mults[p] = (mults[p] * 10) % primes[p]
  c[key] += 1
  prev = key

# print(c)
ans = sum((v*(v-1)) // 2 for v in c.values())
print(ans)