#include #include #include #include // Include tuple header #include // Use std::vector using namespace std; // Define StateKey as a tuple of three integers (r, g, b) representing counts of Red, Green, Blue cells used. using StateKey = tuple; long long N; // Number of cells in the row int R, G, B; // Required number of Red, Green, Blue cells long long MOD = 1000000007; // Modulo value // State representation indices: // These indices represent the state of the suffix of the currently built sequence. // They capture information about the last one or two cells needed to check constraints. // 0: ends in W (_W) - The last cell is blank. // 1: ends in R, preceded by W (WR) - Last cell is Red, previous is Blank. // 2: ends in G, preceded by W (WG) - Last cell is Green, previous is Blank. // 3: ends in B, preceded by W (WB) - Last cell is Blue, previous is Blank. // 4: ends in R, preceded by G (GR) - Last two cells are Green then Red. // 5: ends in R, preceded by B (BR) - Last two cells are Blue then Red. // 6: ends in G, preceded by R (RG) - Last two cells are Red then Green. // 7: ends in G, preceded by B (BG) - Last two cells are Blue then Green. // 8: ends in B, preceded by R (RB) - Last two cells are Red then Blue. // 9: ends in B, preceded by G (GB) - Last two cells are Green then Blue. const int NUM_STATES = 10; // Use map for DP state storage. The key is StateKey (r, g, b). // The value is a vector of size NUM_STATES storing the number of ways to reach this (r,g,b) count ending in each of the 10 suffix states. // We use two maps to represent dp[i] and dp[i-1] to save memory. map> dp[2]; int main() { // Faster IO operations ios_base::sync_with_stdio(false); cin.tie(NULL); // Read input values cin >> N >> R >> G >> B; // Basic check for non-negative counts. Problem constraints say R,G,B >= 0 anyway. if (R < 0 || G < 0 || B < 0) { cout << 0 << endl; return 0; } // Initialize DP state int current = 0; // Index for the current DP table (dp[i]) // Base case: At step i=0 (empty prefix), we have used 0 R, G, B cells. // The state conceptually ends in W (blank), so we initialize state 0 count to 1. StateKey initial_key = make_tuple(0, 0, 0); dp[current][initial_key] = vector(NUM_STATES, 0); // Initialize vector with zeros dp[current][initial_key][0] = 1; // There's 1 way to have an empty prefix (state 0) // Iterate N times, processing one cell at a time from i=0 to N-1 for (int i = 0; i < N; ++i) { int next = 1 - current; // Index for the next DP table (dp[i+1]) dp[next].clear(); // Clear the map for the next step before filling it // Iterate through all reachable states (r, g, b) at the current step i for (auto const& [key, state_values] : dp[current]) { int r, g, b; tie(r, g, b) = key; // Extract current counts r, g, b from the key // Iterate through all 10 possible suffix states for this (r, g, b) count for (int state_idx = 0; state_idx < NUM_STATES; ++state_idx) { // If the number of ways to reach this state is 0, skip calculation if (state_values[state_idx] == 0) continue; long long current_ways = state_values[state_idx]; // Number of ways to reach this state // Try adding a Blank cell (W) // Always possible regardless of the previous state. The new state ends in W (state 0). Counts r,g,b unchanged. { StateKey next_key = make_tuple(r, g, b); // Ensure the entry for next_key exists in the dp[next] map. If not, create it and initialize with zeros. if (dp[next].find(next_key) == dp[next].end()) { dp[next][next_key] = vector(NUM_STATES, 0); } // Add current_ways to the count for state 0 at (r,g,b) in the next step. dp[next][next_key][0] = (dp[next][next_key][0] + current_ways) % MOD; } // Try adding a Red cell (R) if (r + 1 <= R) { // Check if we have not exceeded the required count R bool possible = true; int next_state_idx = -1; // Constraint 6: Cannot have RR. Check if the current state ends in R. // States ending in R are 1 (WR), 4 (GR), 5 (BR). if (state_idx == 1 || state_idx == 4 || state_idx == 5) possible = false; // Constraint 8: Cannot have 3 consecutive colored cells. Check if current state ends in 2 colored cells. // States ending in 2 colored cells are 4 through 9. if (state_idx >= 4) possible = false; if (possible) { // Determine the next state index based on the current state if (state_idx == 0) next_state_idx = 1; // Current ends W (_W), add R -> WR (state 1) else if (state_idx == 2) next_state_idx = 4; // Current ends G (WG), add R -> WGR (state 4) else if (state_idx == 3) next_state_idx = 5; // Current ends B (WB), add R -> WBR (state 5) // If current state index is 1, or 4..9, 'possible' would be false. if (next_state_idx != -1) { // If a valid transition exists StateKey next_key = make_tuple(r + 1, g, b); // Update counts: r+1 // Ensure entry exists for next_key if (dp[next].find(next_key) == dp[next].end()) { dp[next][next_key] = vector(NUM_STATES, 0); } // Add ways to the corresponding next state dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD; } } } // Try adding a Green cell (G) if (g + 1 <= G) { // Check G budget bool possible = true; int next_state_idx = -1; // Constraint 6: Cannot have GG. Check if current state ends in G. // States ending in G are 2 (WG), 6 (RG), 7 (BG). if (state_idx == 2 || state_idx == 6 || state_idx == 7) possible = false; // Constraint 8: Check if current state ends in 2 colored cells. if (state_idx >= 4) possible = false; if (possible) { if (state_idx == 0) next_state_idx = 2; // W -> WG (state 2) else if (state_idx == 1) next_state_idx = 6; // WR -> WRG (state 6) else if (state_idx == 3) next_state_idx = 7; // WB -> WBG (state 7) if (next_state_idx != -1) { StateKey next_key = make_tuple(r, g + 1, b); // Update counts: g+1 if (dp[next].find(next_key) == dp[next].end()) { dp[next][next_key] = vector(NUM_STATES, 0); } dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD; } } } // Try adding a Blue cell (B) if (b + 1 <= B) { // Check B budget bool possible = true; int next_state_idx = -1; // Constraint 6: Cannot have BB. Check if current state ends in B. // States ending in B are 3 (WB), 8 (RB), 9 (GB). if (state_idx == 3 || state_idx == 8 || state_idx == 9) possible = false; // Constraint 8: Check if current state ends in 2 colored cells. if (state_idx >= 4) possible = false; if (possible) { if (state_idx == 0) next_state_idx = 3; // W -> WB (state 3) else if (state_idx == 1) next_state_idx = 8; // WR -> WRB (state 8) else if (state_idx == 2) next_state_idx = 9; // WG -> WGB (state 9) if (next_state_idx != -1) { StateKey next_key = make_tuple(r, g, b + 1); // Update counts: b+1 if (dp[next].find(next_key) == dp[next].end()) { dp[next][next_key] = vector(NUM_STATES, 0); } dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD; } } } } } current = next; // Switch dp table index for the next iteration } // Calculate the final answer long long total_ways = 0; StateKey final_key = make_tuple(R, G, B); // The target state with exact counts R, G, B // Check if the target state (R, G, B) is reachable after N steps if (dp[current].count(final_key)) { // If reachable, get the vector of counts for the 10 suffix states const vector& final_state_values = dp[current].at(final_key); // Use .at() for const access // Sum up the ways for all possible ending states for (int state_idx = 0; state_idx < NUM_STATES; ++state_idx) { total_ways = (total_ways + final_state_values[state_idx]) % MOD; } } // Output the final answer cout << total_ways << endl; return 0; }