AtCoder Regular Contest 058 - Iroha and Haiku

Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.
Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.
Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?
Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to contain an X,Y,Z-Haiku if and only if there exist four indices x, y, z, w (0 ≦ x < y < z < w ≦ N) such that all of the following are satisfied:
 - a_x + a_{x+1} + ... + a_{y-1} = X
 - a_y + a_{y+1} + ... + a_{z-1} = Y
 - a_z + a_{z+1} + ... + a_{w-1} = Z
Since the answer can be extremely large, print the number modulo 10^9+7.

-----Constraints-----
 - 3 ≦ N ≦ 40
 - 1 ≦ X ≦ 5
 - 1 ≦ Y ≦ 7
 - 1 ≦ Z ≦ 5

-----Input-----
The input is given from Standard Input in the following format:
N X Y Z

-----Output-----
Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.

-----Sample Input-----
3 5 7 5

-----Sample Output-----
1

Here, the only sequence that contains a 5,7,5-Haiku is [5, 7, 5].

Difficulty: VERY_HARD

Starter code:

Solutions:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, X, Y, Z) = list(map(int, read().split()))
N = 1 << X + Y + Z
NX = 1 << X
NY = 1 << X + Y
NZ = 1 << X + Y + Z
MX = (1 << X) - 1
MY = (1 << Y + X) - (1 << X)
MZ = (1 << X + Y + Z) - (1 << Y + X)
MMX = MX << 1
MMY = MY << 1
MMZ = MZ << 1
dp = [0] * N
dp[1] = 1
MOD = 10 ** 9 + 7
for _ in range(n):
	ndp = [0] * N
	for mask in range(N):
		if dp[mask] == 0:
			continue
		mx = mask & MX
		my = mask & MY
		mz = mask & MZ
		for j in range(1, 11):
			nmx = mx << j
			nmx &= MMX
			nmy = my << j
			nmy &= MMY
			nmz = mz << j
			nmz &= MMZ
			nmask = nmx | nmy | nmz | 1
			if not nmask & 1 << X + Y + Z:
				ndp[nmask] += dp[mask]
				ndp[nmask] %= MOD
	dp = ndp
ans = pow(10, n, MOD) - sum(dp)
print(ans % MOD)


(N, X, Y, Z) = [int(_) for _ in input().split()]
mod = 10 ** 9 + 7
dp = [0] * 2 ** (X + Y + Z)
dp[0] = 1
al = 2 ** (X + Y + Z) - 1
ng = (2 ** Z + 2 ** (Y + Z) + 2 ** (X + Y + Z)) // 2
for _ in range(N):
	dpn = [0] * 2 ** (X + Y + Z)
	for i in range(1, 11):
		for b in range(2 ** (X + Y + Z)):
			nb = (b << i | 1 << i - 1) & al
			if ng & nb == ng:
				continue
			dpn[nb] += dp[b]
	for b in range(2 ** (X + Y + Z)):
		dpn[b] %= mod
	dp = dpn
ans = 10 ** N % mod
ans -= sum(dp)
ans %= mod
print(ans)


(N, X, Y, Z) = map(int, input().split())
mod = 10 ** 9 + 7
forbit = (1 << X + Y + Z - 1) + (1 << Y + Z - 1) + (1 << Z - 1)
mask = (1 << X + Y + Z) - 1
dp = [[0] * (mask + 1) for i in range(N + 1)]
dp[0][0] = 1
for n in range(1, N + 1):
	for i in range(mask + 1):
		for k in range(10):
			t = (i << k + 1 | 1 << k) & mask
			if t & forbit == forbit:
				continue
			dp[n][t] += dp[n - 1][i]
			dp[n][t] %= mod
ans = pow(10, N, mod)
for i in range(mask + 1):
	ans -= dp[N][i]
	ans %= mod
print(ans)


mod = 10 ** 9 + 7
(N, X, Y, Z) = map(int, input().split())
num = 1 << X + Y + Z - 1
ng = ((1 << X) + 1 << Y) + 1 << Z - 1
dp = [[0] * num for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(1, 11):
		for k in range(num):
			K = k * 2 + 1 << j - 1
			if K & ng != ng:
				K &= num - 1
				dp[i + 1][K] += dp[i][k]
				dp[i + 1][K] %= mod
print((10 ** N % mod - sum(dp[N]) % mod) % mod)


(n, x, y, z) = map(int, input().split())
mod = 10 ** 9 + 7
forbit = (1 << x + y + z - 1) + (1 << y + z - 1) + (1 << z - 1)
mask = (1 << x + y + z) - 1
l1 = set()
for i in range(mask + 1):
	if i & forbit:
		l1.add(i)
d = [[0] * (mask + 1) for i in range(n + 1)]
d[0][0] = 1
for j in range(n):
	for i in range(mask + 1):
		for k in range(10):
			t = (i << k + 1 | 1 << k) & mask
			if t & forbit == forbit:
				continue
			d[j + 1][t] += d[j][i]
			d[j + 1][t] %= mod
answer = 10 ** n % mod
for i in range(mask + 1):
	answer -= d[n][i]
	answer %= mod
print(answer)


def examE(mod):
	(N, X, Y, Z) = LI()
	L = 2 ** (X + Y + Z - 1)
	XYZ = 1 << X + Y + Z - 1 | 1 << Y + Z - 1 | 1 << Z - 1
	dp = [[0] * L for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(N):
		for j in range(L):
			for k in range(1, 11):
				next = j << k | 1 << k - 1
				if next & XYZ == XYZ:
					continue
				else:
					dp[i + 1][next % L] += dp[i][j]
					dp[i + 1][next % L] %= mod
	ans = pow(10, N, mod) - sum(dp[-1]) % mod
	if ans < 0:
		ans += mod
	print(ans)
import sys
import copy
import bisect
import heapq
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
inf = float('inf')
examE(mod)


(n, x, y, z) = map(int, input().split())
s = x + y + z
MOD = 10 ** 9 + 7
dp = [[0] * (1 << s) for _ in range(n + 1)]
dp[0][0] = 1
mask = (1 << s) - 1
for i in range(n):
	for j in range(1 << s):
		for k in range(1, 11):
			t = (j << k | 1 << k - 1) & mask
			if t >> z - 1 & 1 and t >> y + z - 1 & 1 and t >> x + y + z - 1 & 1:
				continue
			dp[i + 1][t] += dp[i][j]
			dp[i + 1][t] %= MOD
ans = pow(10, n, MOD) - sum(dp[n])
ans %= MOD
print(ans)


(N, X, Y, Z) = map(int, input().split())
m = 2 ** (X + Y + Z)
S = [0] * m
L = max(X, Y, Z)
ss = set()
tt = set()
Z0 = 1 << Z - 1
Y0 = 1 << Z + Y - 1
X0 = 1 << X + Z + Y - 1
for i in range(m):
	if i & Z0 and i & Y0 and i & X0:
		ss.add(i)
MASK = 2 ** (X + Y + Z) - 1
MOD = 10 ** 9 + 7
S[0] = 1
for i in range(N):
	T = [0] * m
	for s in range(m):
		if s in ss:
			continue
		b = s << 1 | 1
		for k in range(1, L + 1):
			t = b << k - 1 & MASK
			T[t] = (T[t] + S[s]) % MOD
		for k in range(L + 1, 11):
			T[0] = (T[0] + S[s]) % MOD
	S = T
ans = 0
for s in range(m):
	if s in ss:
		continue
	ans = (ans + S[s]) % MOD
ans = (pow(10, N, MOD) + MOD - ans) % MOD
print(ans)


def inpl():
	return [int(i) for i in input().split()]

def nextb(b, k):
	b <<= 1
	b += 1
	b <<= k - 1
	return b
mod = 10 ** 9 + 7
(N, x, y, z) = inpl()
xyz = 2 ** (x + y + z - 1) + 2 ** (y + z - 1) + 2 ** (z - 1)
W = 2 ** (x + y + z - 1)
dp = [[0] * W for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(W):
		for k in range(1, 11):
			nj = nextb(j, k)
			if nj & xyz != xyz:
				dp[i + 1][nj % W] = (dp[i + 1][nj % W] + dp[i][j]) % mod
print((10 ** N % mod - sum(dp[-1]) % mod) % mod)


(N, X, Y, Z) = map(int, input().split())
MOD = 10 ** 9 + 7
ng = (1 << Z - 1) + (1 << Y + Z - 1) + (1 << X + Y + Z - 1)
S = (1 << X + Y + Z) - 1
dp = [[0] * (S + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
	for j in range(S + 1):
		for k in range(1, 11):
			s = (j << k | 1 << k - 1) & S
			if s & ng == ng:
				continue
			dp[i][s] += dp[i - 1][j]
			dp[i][s] %= MOD
ans = pow(10, N, MOD)
num = 0
for i in range(S + 1):
	num += dp[N][i]
	num %= MOD
print((ans - num + MOD) % MOD)


mod = 10 ** 9 + 7
(N, X, Y, Z) = map(int, input().split())
Num = 1 << X + Y + Z - 1
ng = ((1 << X) + 1 << Y) + 1 << Z - 1
dp = [[0] * Num for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for k in range(Num):
		for j in range(1, 11):
			a = k << j | 1 << j - 1
			if a & ng != ng:
				a &= Num - 1
				dp[i + 1][a] += dp[i][k]
				dp[i + 1][a] %= mod
print((10 ** N % mod - sum(dp[N]) % mod) % mod)


MOD = 10 ** 9 + 7
(N, X, Y, Z) = map(int, input().split())
pow2_XYZ = 2 ** (X + Y + Z)
flg = [False] * pow2_XYZ
mask = ((1 << X) + 1 << Y) + 1 << Z - 1
for hist in range(pow2_XYZ):
	if hist & mask == mask:
		flg[hist] = True
h2s = [[0] * 10 for i in range(pow2_XYZ)]
for hist in range(pow2_XYZ):
	for A in range(1, 11):
		h2s[hist][A - 1] = ((hist << A) + (1 << A - 1)) % pow2_XYZ
dp = [[0] * pow2_XYZ for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for hist in range(pow2_XYZ):
		if dp[i][hist] == 0:
			continue
		for A in range(1, 11):
			h2 = h2s[hist][A - 1]
			if not flg[h2]:
				dp[i + 1][h2] += dp[i][hist]
	dp[i + 1] = list(map(lambda x: x % MOD, dp[i + 1]))
num = sum(dp[N]) % MOD
print((10 ** N - num) % MOD)


(N, X, Y, Z) = map(int, input().split())
p = 10 ** 9 + 7
m = 1
m <<= X
m += 1
m <<= Y
m += 1
m <<= Z - 1
L = 2 ** (X + Y + Z - 1)
M = [[0 for _ in range(10)] for _ in range(L)]
for i in range(L):
	for j in range(10):
		k = i << j + 1
		k += 1 << j
		M[i][j] = k % L if k & m != m else -1
DP = [[0 for _ in range(L)] for _ in range(N + 1)]
DP[0][0] = 1
for i in range(N):
	for j in range(L):
		if DP[i][j] == 0:
			continue
		DP[i][j] %= p
		for k in range(10):
			l = M[j][k]
			if l < 0:
				continue
			DP[i + 1][l] += DP[i][j]
cnt = 10 ** N % p
print((cnt - sum(DP[N]) % p) % p)


(n, x, y, z) = map(int, input().split())
mod = 10 ** 9 + 7
mask = 1 << x + y + z - 1
dp = [[0 for i in range(mask + 1)] for j in range(n + 1)]
dp[0][0] = 1
ng = 1 << x + y + z - 1 | 1 << y + z - 1 | 1 << z - 1
for i in range(n):
	dp[i + 1][mask] = dp[i][mask] * 10 % mod
	for j in range(mask):
		for k in range(1, 11):
			nmask = j << k | 1 << k - 1
			if nmask & ng == ng:
				nmask = mask
			else:
				nmask &= mask - 1
			dp[i + 1][nmask] = (dp[i + 1][nmask] + dp[i][j]) % mod
print(dp[n][mask])


MOD = pow(10, 9) + 7

def main():
	(n, x, y, z) = map(int, input().split())
	ngnum = pow(2, z - 1) + pow(2, y + z - 1) + pow(2, x + y + z - 1)
	mask = pow(2, x + y + z) - 1
	dp = [[0 for _ in range(mask + 1)] for _ in range(n + 1)]
	ans = 1
	for _ in range(n):
		ans = ans * 10 % MOD
	dp[0][0] = 1
	for i in range(n):
		for j in range(mask + 1):
			if dp[i][j] == 0:
				continue
			for d in range(1, 11):
				t = j * pow(2, d) | pow(2, d - 1)
				if t & ngnum == ngnum:
					continue
				t &= mask
				dp[i + 1][t] = (dp[i + 1][t] + dp[i][j]) % MOD
	for i in range(mask + 1):
		ans = (ans + MOD - dp[n][i]) % MOD
	print(ans)
main()


mod = 10 ** 9 + 7
(n, x, y, z) = map(int, input().split())
xyz = 2 ** (x + y + z - 1) + 2 ** (y + z - 1) + 2 ** (z - 1)
w = 2 ** (x + y + z - 1)
dp = [[0] * w for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(w):
		for k in range(1, 11):
			nj = j + j + 1 << k - 1
			if nj & xyz != xyz:
				dp[i + 1][nj % w] = (dp[i + 1][nj % w] + dp[i][j]) % mod
print((pow(10, n, mod) - sum(dp[-1]) % mod) % mod)


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
input = sys.stdin.readline
show_flg = False
(n, X, Y, Z) = MI()
t = 1 << X + Y + Z
haiku = (1 << X + Y + Z) + (1 << Y + Z) + (1 << Z) >> 1
dp = [[0] * t for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for k in range(t):
		for d in range(10):
			m = (k << d + 1) + (1 << d)
			if m & haiku == haiku:
				continue
			else:
				dp[i + 1][int(m) % t] += dp[i][k]
				dp[i + 1][int(m) % t] %= mo
sub = 0
for i in range(t):
	sub += dp[n][i]
ans = pow(10, n, mo) - sub
print(ans % mo)


(n, x, y, z) = map(int, input().split())
mod = 10 ** 9 + 7
simple_xyz = 1 << x + y + z - 1 | 1 << y + z - 1 | 1 << z - 1

def isnotxyz(b):
	return b & simple_xyz != simple_xyz
dp = [[0] * (1 << x + y + z - 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for b in range(1 << x + y + z - 1):
		if dp[i][b] == 0:
			continue
		for j in range(10):
			new_b = (b << 1 | 1) << j & (1 << x + y + z) - 1
			if isnotxyz(new_b):
				new_b &= (1 << x + y + z - 1) - 1
				dp[i + 1][new_b] += dp[i][b]
				dp[i + 1][new_b] %= mod

def summod(a, mod):
	res = 0
	for ai in a:
		res += ai
		res %= mod
	return res
print((pow(10, n, mod) - sum(dp[n])) % mod)


import sys
input = sys.stdin.readline
import numpy as np
(N, X, Y, Z) = map(int, input().split())
MOD = 10 ** 9 + 7
L = max(10, X + Y + Z)
dp = np.zeros(1 << L + 1, dtype=np.int64)
rng = np.arange(1 << L + 1, dtype=np.int64)
x575 = (1 << Z) + (1 << Y + Z) + (1 << X + Y + Z)
bad = x575 & rng == x575
dp[1] = 1
for n in range(N):
	prev = dp
	dp = np.zeros_like(prev)
	for i in range(1, 11):
		dp[1::1 << i] += prev.reshape(1 << i, 1 << L + 1 - i).sum(axis=0)
	dp[bad] = 0
	dp %= MOD
answer = pow(10, N, MOD) - dp.sum()
answer %= MOD
print(answer)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def A():
	return

def B():
	return

def C():
	(n, x, y, z) = LI()
	po2 = [1 << i for i in range(x + y + z + 1)]
	max = po2[x + y + z]
	ng = po2[x + y + z - 1] | po2[y + z - 1] | po2[z - 1]
	dp = [[0 for i in range(max)] for i in range(n + 1)]
	dp[0][0] = 1
	mask = max - 1
	for i in range(n):
		for j in range(max):
			for k in range(1, 11):
				t = j << k | 1 << k - 1
				if t & ng != ng:
					t &= mask
					dp[i + 1][t] += dp[i][j]
					dp[i + 1][t] %= mod
	ans = pow(10, n, mod)
	for i in range(max):
		ans -= dp[n][i]
		ans %= mod
	print(ans)

def D():
	return

def E():
	return

def F():
	return

def G():
	return

def H():
	return
C()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, X, Y, Z) = MAP()
M = X + Y + Z
check = 1 << X + Y + Z - 1 | 1 << Y + Z - 1 | 1 << Z - 1
dp = list2d(N + 1, 1 << M - 1, 0)
dp[0][0] = 1
msk1 = (1 << M) - 1
msk2 = (1 << M - 1) - 1
for i in range(N):
	for S in range(1 << M - 1):
		if not dp[i][S]:
			continue
		for j in range(10):
			S2 = (S << 1 | 1) << j & msk1
			if S2 & check != check:
				dp[i + 1][S2 & msk2] += dp[i][S]
				dp[i + 1][S2 & msk2] %= MOD
total = pow(10, N, MOD)
print((total - sum(dp[N]) % MOD) % MOD)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	(N, x, y, z) = list(map(int, input().split()))
	s = x + y + z
	m = max(x, y, z)
	mask_x = (1 << x + 1) - 1
	mask_y = (1 << y) - 1
	mask_z = (1 << z) - 1
	dp = [0] * (1 << s)
	dp[1] = 1
	for _ in range(N):
		dp_new = [0] * (1 << s)
		for state in range(1 << s):
			if dp[state] == 0:
				continue
			state_x = state & mask_x
			state_y = state >> x + 1 & mask_y
			state_z = state >> x + y + 1 & mask_z
			for w in range(1, m + 1):
				if z - w - 1 >= 0:
					if state_z >> z - w - 1 & 1:
						continue
				if w == z and state_y >> y - 1 & 1:
					continue
				state_new = state_x << w & mask_x | (state_y << w & mask_y) << x + 1 | (state_z << w & mask_z) << x + y + 1 | 1
				if state_x >> x & 1 and w <= y:
					state_new |= 1 << w + x
				if state_y >> y - 1 & 1 and w <= z:
					state_new |= 1 << w + x + y
				dp_new[state_new] = (dp_new[state_new] + dp[state]) % mod
			dp_new[1] = (dp_new[1] + dp[state] * (10 - m) % mod) % mod
		dp = dp_new
	ans = pow(10, N, mod)
	for a in dp:
		ans = (ans - a) % mod
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, X, Y, Z) = map(int, input().split())
MOD = 10 ** 9 + 7
D = 2 ** (X + Y + Z - 1)
XYZ = 1 << X + Y + Z - 1 | 1 << Y + Z - 1 | 1 << Z - 1
dp = [[0] * D for _ in range(N + 1)]
dp[0][0] = 1
for right in range(N):
	for mask in range(D):
		for nextA in range(1, 11):
			newMask = mask << nextA | 1 << nextA - 1
			if newMask & XYZ != XYZ:
				dp[right + 1][newMask % D] += dp[right][mask]
				dp[right + 1][newMask % D] %= MOD
ans = pow(10, N, MOD) - sum(dp[-1])
print(ans % MOD)


(N, x, y, z) = map(int, input().split())
mask = 2 ** (x + y + z) - 1
mod = 10 ** 9 + 7
ng = 2 ** (x + y + z - 1) + 2 ** (y + z - 1) + 2 ** (z - 1)
dp = [[0 for i in range(mask + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(mask + 1):
		for k in range(1, 11):
			if mask & (j << k) + (1 << k - 1) & ng != ng:
				dp[i + 1][mask & (j << k) + (1 << k - 1)] += dp[i][j]
			dp[i + 1][j] %= mod
ans = 10 ** N % mod
for j in range(mask + 1):
	ans -= dp[N][j]
	ans %= mod
print(ans)


MOD = 1000000007

def dfs(total, arr):
	if total == 0:
		return [arr]
	ret = []
	for i in range(1, total + 1):
		ret += dfs(total - i, arr + [i])
	return ret
(N, X, Y, Z) = map(int, input().split())
(xx, yy, zz) = [dfs(n, []) for n in [X, Y, Z]]
NN = 2 ** (X + Y + Z)
NS = 2 ** (X + Y + Z - 1)
isxyz = [False] * NN
for x in xx:
	for y in yy:
		for z in zz:
			tmp = 0
			for a in x + y + z:
				tmp = tmp << a
				tmp += 2 ** (a - 1)
			isxyz[tmp] = True
dp = [[0] * NS for _ in range(N + 1)]
dp[0][0] = 1
mask1 = NN - 1
mask2 = NS - 1
for i in range(N):
	for src in range(NS):
		for k in range(1, 11):
			if dp[i][src] == 0:
				continue
			state = (src << k) + 2 ** (k - 1) & mask1
			if isxyz[state] is False:
				dst = state & mask2
				dp[i + 1][dst] = (dp[i + 1][dst] + dp[i][src]) % MOD
ans = 0
for v in dp[N]:
	ans = (ans + v) % MOD
total = 10 ** N % MOD
print((total - ans + MOD) % MOD)