MOD = 10**9 + 7 N, R, G, B = map(int, input().split()) if R + G + B > N: print(0) exit() from collections import defaultdict # dp[prev_color][run_length][(r_used, g_used, b_used)] = count dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) dp[0][0][(0, 0, 0)] = 1 # Initial state: no color, run_length 0, used colors (0,0,0) for _ in range(N): new_dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) for prev_color in dp: for run_length in dp[prev_color]: for (r_used, g_used, b_used), cnt in dp[prev_color][run_length].items(): # Option 1: Leave the current cell blank new_color = 0 new_run = 0 new_dp[new_color][new_run][(r_used, g_used, b_used)] = ( new_dp[new_color][new_run][(r_used, g_used, b_used)] + cnt ) % MOD # Option 2: Paint the current cell with a color for color in [1, 2, 3]: # 1: Red, 2: Green, 3: Blue if color == prev_color: continue # Same color cannot be adjacent if prev_color != 0 and run_length >= 2: continue # Cannot have three consecutive painted cells # Check if we can use this color new_r = r_used + (1 if color == 1 else 0) new_g = g_used + (1 if color == 2 else 0) new_b = b_used + (1 if color == 3 else 0) if new_r > R or new_g > G or new_b > B: continue # Calculate new run length if prev_color == 0: # Previous was blank, reset run length new_run_length = 1 else: # Continue the run new_run_length = run_length + 1 if new_run_length > 2: continue # Cannot have run length over 2 new_dp[color][new_run_length][(new_r, new_g, new_b)] = ( new_dp[color][new_run_length][(new_r, new_g, new_b)] + cnt ) % MOD dp = new_dp # Sum all valid states where used colors match R, G, B result = 0 for prev_color in dp: for run_length in dp[prev_color]: for (r, g, b), cnt in dp[prev_color][run_length].items(): if r == R and g == G and b == B: result = (result + cnt) % MOD print(result)