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: competition

Starter code:

Solutions:
# coding: utf-8
# Your code here!
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
    #cnt = 0
    #bad = 0
    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
    #print(sum(dp),"sum")

ans = (pow(10,n,MOD)-sum(dp))
print((ans%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)

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()