Python-сообщество

from itertools import product
#import time
#import sys
#sys.stdin, sys.stdout = open("aplusb.in", "r"), open("aplusb.out", "w")
#begin = time.time()
MOD = 10**9+7
#c = map(int, raw_input()[::-1])
c = [9]*10000
n = len(c)
r10, rn, r1_n, r2, r1_10 = range(10), range(n), range(1, n), range(2), range(1, 10)
s = [[[[0, 0] for j in r10] for i in r10] for k in rn]
for i in range(c[0]+1):
    s[0][i][c[0]-i][0] = 1
for i in range(c[0]+1, 10):
    s[0][i][10+c[0]-i][1] = 1
for k, i, j, p, p0 in product(r1_n, r10, r10, r2, r2):
    if i+j == c[k]+10*p-p0:
        s[k][i][j][p] = sum(
            s[k-1][x][y][p0]
            for x in r10 if x != i
            for y in r10 if y != j and s[k-1][x][y][p0])%MOD
print sum(s[-1][i][j][0] for i, j in product(r1_10, r1_10) if s[-1][i][j][0])%MOD
#print time.time()-begin

c = [9]*10000
n = len(c)

n = 10000
c = [9]*n

for i in range(c[0]+1, 10):
    s[0][i][10+c[0]-i][1] = 1

c[0] +1 = 10  => range(10, 10) 

for i in range(c[0]+1):
    s[0][i][c[0]-i][0] = 1

for i in range(10):
    s[0][i][9 - i][0] = 1