Submission

Score: 20

User: hmmm

Problemset: กองไฟ

Language: cpp

Time: 0.004 second

Submitted On: 2025-06-24 21:48:02

#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
const int N=25,MOD=1e9+7;
int dp[N][N][N][5][5],n,a,b,c;

inline ll rec(int x,int y,int z,int w,int t){
	if(dp[x][y][z][w][t]!=-1) return dp[x][y][z][w][t];
    
    if(x+y+z==n-1){
        // cout << x << ' ' << y << ' ' << z << ' ' << w << ' ' << t << "\n";
        if(x+1==a && w!=1 && t!=1) return 1;
        if(y+1==b && w!=2 && t!=2) return 1;
        if(z+1==c && w!=3 && t!=3) return 1;
        return 0;
    }
    ll cnt=0;
    if(x+1<=a && w!=1) cnt+=rec(x+1,y,z,1,t),cnt%=MOD;
    if(y+1<=b && w!=2) cnt+=rec(x,y+1,z,2,t),cnt%=MOD;
    if(z+1<=c && w!=3) cnt+=rec(x,y,z+1,3,t),cnt%=MOD;
    return dp[x][y][z][w][t]=cnt;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	memset(dp,-1,sizeof dp);
	cin >> n >> a >> b >> c;
	ll sum=0;
	if(a>0) sum+=rec(1,0,0,1,1),sum%=MOD;
	if(b>0) sum+=rec(0,1,0,2,2),sum%=MOD;
	if(c>0) sum+=rec(0,0,1,3,3),sum%=MOD;
	cout << sum;
}