Submission

Score: 100

User: kittipos

Problemset: กองไฟ

Language: cpp

Time: 0.059 second

Submitted On: 2026-03-09 22:56:25

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+7;

vector<vector<vector<vector<vector<int>>>>> dp;

int solve(vector<int> left, int prev, int start) {

    if (dp[left[0]][left[1]][left[2]][prev][start] != -1) {
        return dp[left[0]][left[1]][left[2]][prev][start];
    }

    int sum = 0;
    bool fork = false;
    for (int i = 0; i < 3; i++) {
        if (left[i] == 0) continue;
        fork = true;
        if (prev == i) continue;
        vector<int> new_left = left;
        new_left[i]--;

        sum += solve(new_left, i, start);
        sum %= MOD;
    }

    if (!fork) {
        // cout << "done" << endl;
        if (prev == start) {
            return 0;
        } else {
            return 1;
        }
    }
    dp[left[0]][left[1]][left[2]][prev][start] = sum;
    return sum;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> left;
    left.resize(3);
    for (int i = 0; i < 3; i++) {
        cin >> left[i];
    }

    dp.assign(
        left[0]+1,
        vector<vector<vector<vector<int>>>>(
            left[1]+1,
            vector<vector<vector<int>>>(
                left[2]+1,
                vector<vector<int>>(
                    3,
                    vector<int>(
                        3, -1
                    )
                )
            )
        )
    );

    int sum = 0;
    for (int i = 0; i < 3; i++) {
        vector<int> new_left = left;
        if (new_left[i] == 0) continue;

        new_left[i]--;
        sum += solve(new_left, i, i);
        // cout << sum << endl;
        sum %= MOD;
    }
    cout << sum;

    return 0;
}