Submission

Score: 0

User: foldnut

Problemset: กองไฟ

Language: cpp

Time: 0.001 second

Submitted On: 2025-12-01 19:17:51

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MD = 1e9 + 7;
ll n, A, B, C, ans, dp[155][55][55][55][4];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> A >> B >> C;
    if(A != 0){
        dp[0][0][0][0][0] = 1;
        for(int i = 1;i<=n - 1;i++){
            for(int a = 0;a<=A - 1;a++){
                for(int b = 0;b<=B;b++){
                    for(int c = 0;c<=C;c++){
                        if(a - 1 >= 0){
                            dp[i][a][b][c][1] = (dp[i - 1][a - 1][b][c][0] + dp[i - 1][a - 1][b][c][2] + dp[i - 1][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i][a][b][c][2] = (dp[i - 1][a][b - 1][c][0] + dp[i - 1][a][b - 1][c][1] + dp[i - 1][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i][a][b][c][3] = (dp[i - 1][a][b][c - 1][0] + dp[i - 1][a][b][c - 1][1] + dp[i - 1][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[n - 1][A - 1][B][C][0] + dp[n - 1][A - 1][B][C][2] + dp[n - 1][A - 1][B][C][3]) % MD;
        memset(dp, 0, sizeof dp);
    }
    if(B != 0){
        dp[0][0][0][0][0] = 1;
        for(int i = 1;i<=n - 1;i++){
            for(int a = 0;a<=A;a++){
                for(int b = 0;b<=B - 1;b++){
                    for(int c = 0;c<=C;c++){
                        if(a - 1 >= 0){
                            dp[i][a][b][c][1] = (dp[i - 1][a - 1][b][c][0] + dp[i - 1][a - 1][b][c][2] + dp[i - 1][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i][a][b][c][2] = (dp[i - 1][a][b - 1][c][0] + dp[i - 1][a][b - 1][c][1] + dp[i - 1][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i][a][b][c][3] = (dp[i - 1][a][b][c - 1][0] + dp[i - 1][a][b][c - 1][1] + dp[i - 1][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[n - 1][A][B - 1][C][0] + dp[n - 1][A][B - 1][C][1] + dp[n - 1][A][B - 1][C][3]) % MD;
        memset(dp, 0, sizeof dp);
    }
    if(C != 0){
        dp[0][0][0][0][0] = 1;
        for(int i = 1;i<=n - 1;i++){
            for(int a = 0;a<=A;a++){
                for(int b = 0;b<=B;b++){
                    for(int c = 0;c<=C - 1;c++){
                        if(a - 1 >= 0){
                            dp[i][a][b][c][1] = (dp[i - 1][a - 1][b][c][0] + dp[i - 1][a - 1][b][c][2] + dp[i - 1][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i][a][b][c][2] = (dp[i - 1][a][b - 1][c][0] + dp[i - 1][a][b - 1][c][1] + dp[i - 1][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i][a][b][c][3] = (dp[i - 1][a][b][c - 1][0] + dp[i - 1][a][b][c - 1][1] + dp[i - 1][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[n - 1][A][B][C - 1][0] + dp[n - 1][A][B][C - 1][1] + dp[n - 1][A][B][C - 1][2]) % MD;
    }
    cout << ans;
}