Submission

Score: 100

User: Ninstroyer

Problemset: กองไฟ

Language: cpp

Time: 0.009 second

Submitted On: 2026-01-03 20:10:21

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 1e9+7;

ll n,a,b,c;
ll dp[51][51][51][3][3]; // i,j,k, first, last (0=A,1=B,2=C)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> a >> b >> c;

    // Initialize: first student color = last student initially
    if(a>0) dp[1][0][0][0][0] = 1;
    if(b>0) dp[0][1][0][1][1] = 1;
    if(c>0) dp[0][0][1][2][2] = 1;

    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                for(int first=0;first<3;first++){
                    for(int last=0;last<3;last++){
                        ll cur = dp[i][j][k][first][last];
                        if(cur==0) continue;

                        // Add A
                        if(i<a && last!=0){
                            dp[i+1][j][k][first][0] = (dp[i+1][j][k][first][0] + cur) % mod;
                        }
                        // Add B
                        if(j<b && last!=1){
                            dp[i][j+1][k][first][1] = (dp[i][j+1][k][first][1] + cur) % mod;
                        }
                        // Add C
                        if(k<c && last!=2){
                            dp[i][j][k+1][first][2] = (dp[i][j][k+1][first][2] + cur) % mod;
                        }
                    }
                }
            }
        }
    }

    ll res = 0;
    // Only count sequences where last != first
    for(int first=0;first<3;first++){
        for(int last=0;last<3;last++){
            if(last != first){
                res = (res + dp[a][b][c][first][last]) % mod;
            }
        }
    }

    cout << res << "\n";
}