Problem:
 Score : 700 points    Problem Statement 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 1 3 5 7 5      Sample Output 1 1  Here, the only sequence that contains a 5,7,5 -Haiku is [5, 7, 5] .       Sample Input 2 4 5 7 5      Sample Output 2 34       Sample Input 3 37 4 2 3      Sample Output 3 863912418       Sample Input 4 40 5 7 5      Sample Output 4 562805100

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,X,Y,Z = 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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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
cnt = 1
for i in range(N):
    cnt *= 10
    cnt %= mod
for x in dp[N]:
    cnt -= x
    cnt %= mod
print(cnt)

Solution (Python):
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)

Solution (Python):


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)

Solution (Python):


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 not (S2 & check) == check:
                dp[i+1][S2&msk2] += dp[i][S]
                dp[i+1][S2&msk2] %= MOD
total = pow(10, N, MOD)
cnt = 0
for S in range(1<<(M-1)):
    cnt += dp[N][S]
    cnt %= MOD
print((total-cnt)%MOD)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,X,Y,Z = II()

max_val = (1<<17)-1
dp = [[0]*(max_val+1) for _ in range(N+1)]

for k in range(1,11):
    dp[1][1<<(k-1)] = 1

for i in range(1,N):
    for j in range(1,max_val+1):
        for k in range(1,11):
            val = ((j<<k) + (1<<(k-1))) & max_val
            if (val>>(Z-1)&1) and (val>>(Z+Y-1)&1) and (val>>(Z+Y+X-1)&1):
                continue
            else:
                dp[i+1][val] += dp[i][j]
                dp[i+1][val] %= mod

temp = 0
for j in range(1,max_val+1):
    temp += dp[N][j]
    temp %= mod

ans = (pow(10,N,mod)-temp)%mod
print(ans)

Solution (Python):
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))&(t-1)
            if m&haiku == haiku:
                continue
            else:
                dp[i+1][m]+=dp[i][k]
                dp[i+1][m]%=mo
sub=0
for i in range(t):
    sub+=dp[n][i]
ans=pow(10,n,mo)-sub
print(ans%mo)

Solution (Python):
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)

Solution (Python):
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
dp[0]=1


for i in range(n):
    tm=[i for i in dp]
    dp=[0]*t
    for k in range(t):
        for d in range(10):
            m=((k<<(d+1))+(1<<d))
            if m&haiku == haiku:
                continue
            else:
                dp[int(m)%t]+=tm[k]
                dp[int(m)%t]%=mo
sub=0
for i in range(t):
    sub+=dp[i]
ans=pow(10,n,mo)-sub
print(ans%mo)

show(ans,sub)
show(dp)
show(n,t,n*t*10)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)


if __name__ == '__main__':
  main()

Solution (Python):

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


if __name__ == "__main__":
    C()

Solution (Python):
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)

Solution (Python):
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)
s=set()
for i in range(mask+1):
    if i & forbit:
        s.add(i)
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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])

Solution (Python):
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)] 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):
    for j in range(mask):
        for k in range(1,11):
            nmask=(j<<k)|(1<<(k-1))
            if nmask&ng==ng:
                continue
            nmask&=mask-1
            dp[i+1][nmask]=(dp[i+1][nmask]+dp[i][j])%mod
print((pow(10,n,mod)-sum(dp[n]))%mod)