44H - Phone Number - CodeForces Solution

import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline
    
s = input().strip()
n = len(s)
memo = {}

def dp(i,prev):
    if (i,prev) in memo:
        return memo[(i,prev)]
    if i==n:
        return 1
    nxt = int(s[i])+prev
    if nxt%2==0:
        memo[(i,prev)] = dp(i+1,nxt//2)
    else:
        memo[(i,prev)] = dp(i+1,nxt//2) + dp(i+1,nxt//2+1)
    return memo[(i,prev)]

ans = 0
for i in range(0,10):
    ans += dp(1,i)

def check(i,cur):
    if int(s[i])!=cur:
        return False
    if i==n-1:
        return True
    nxt = int(s[i+1])+(cur)
    if nxt%2==0:
        return check(i+1,nxt//2)
    else:
        if int(s[i+1])==nxt//2:
            return check(i+1,nxt//2)
        elif int(s[i+1])==nxt//2+1:
            return check(i+1,nxt//2+1)
        else:
            return False

if check(0,int(s[0])):
    print(ans-1)
else:
    print(ans)