import sys
#sys.stdin, sys.stdout = open("aplusb.in", "r"), open("aplusb.out", "w")
MOD = 10**9+7
#c = map(int, raw_input())[::-1]
c = [9]*10000
n = len(c)
s = [[[[0 for p in xrange(2)] for j in xrange(10)] for i in xrange(10)] for k in xrange(n)]
for i in xrange(c[0]+1):
    s[0][i][c[0]-i][0] = 1
for i in xrange(c[0]+1, 10):
    s[0][i][10+c[0]-i][1] = 1
def f1():
    return sum([
        s[k-1][x][y][0] \
        for x in xrange(10) if x != i \
        for y in xrange(10) if y != j \
        if s[k-1][x][y][0]])%MOD
def f2():
    return sum([
        s[k-1][x][y][1] \
        for x in xrange(10) if x != i \
        for y in xrange(10) if y != j \
        if s[k-1][x][y][1]])%MOD
for k in xrange(1, n):
    for i in xrange(10):
        for j in xrange(10):
            for p in xrange(2):
                s[k][i][j][p] = f1() if i+j == 10*p+c[k] else \
                                f2() if i+j == 10*p+c[k]-1 else 0
print sum([s[n-1][i][j][0] for i in xrange(1, 10) for j in xrange(1, 10) if s[n-1][i][j][0]])%MOD

from array import array
d1 = 2
d2 = 10 * d1
d3 = 10 * d2
a = array("I", [0]*d3*10000)
k = 9999
i = 9
j = 9
p = 1
a[k*d3 + i*d2 + j*d1 + p] = 1
print a

$ cat 1.py 
for i in xrange(10000):
  for j in xrange(10):
    for k in xrange(10):
      for p in xrange(2):
        pass

$ time python 1.py 
real    0m0.358s
user    0m0.356s
sys     0m0.000s

import sys
from array import array
MOD = 10**9+7
c = [9]*10000
n = len(c)
a = array("f", [0]*100)
s = [[a for p in xrange(2)]
        for k in xrange(n)]
for i in xrange(c[0]+1):
    s[0][0][i*10 + (c[0]-i)] = 1
for i in xrange(c[0]+1, 10):
    s[0][1][i*10 + (10+c[0]-i)] = 1