stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define rint register int

#define gc() getchar()

inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}

vector<int> e[1025]; int f[1025][5025], X[1025], n;

void DP(int p){for(auto v:e[p]) for(rint i = (DP(v),X[p]); ~i; f[p][i] = min(i>=X[v]?f[p][i-X[v]]+f[v][X[v]]:INF,i>=f[v][X[v]]?f[p][i-f[v][X[v]]]+X[v]:INF), i--);}

int main(){n = read(); for(rint i = 2; i <= n; e[read()].push_back(i), i++); for(rint i = 1; i <= n; X[i++] = read()); DP(1); puts(f[1][X[1]]<INF?"POSSIBLE":"IMPOSSIBLE"); return 0;}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define min(a,b) ((a)<(b)?(a):(b))

#define reg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

#define endfile fclose(stdin);fclose(stdout);

namespace IO{

    char buf[1<<15],*S,*T;

    inline char gc(){

        if (S==T){

            T=(S=buf)+fread(buf,1,1<<15,stdin);

            if (S==T)return EOF;

        }

		return *S++;

    }

    inline int read(){

        reg int x;reg bool f;reg char c;

        for(f=0;(c=gc())<'0'||c>'9';f=c=='-');

        for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));

        return f?-x:x;

    }

}

const int MN=1005;

const int inf=0x3f3f3f3f;

int n,a[MN],f[MN],g[2][MN*5];

int to[MN],nxt[MN],h[MN],cnt;

inline void ins(int s,int t){to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;}

bool dfs(int st){

	if(!h[st]){f[st]=0;return true;}

	for(reg int i=h[st];i;i=nxt[i])if(!dfs(to[i]))return false;

	reg int pos=0;memset(g[1],0x3f,sizeof(g[1]));g[1][0]=0;

	for(reg int i=h[st];i;i=nxt[i],pos^=1){

		memset(g[pos],0x3f,sizeof(g[pos]));

		for(reg int j=0;j<=a[st];j++){

			if(j>=f[to[i]])g[pos][j]=min(g[pos][j],g[pos^1][j-f[to[i]]]+a[to[i]]);

			if(j>=a[to[i]])g[pos][j]=min(g[pos][j],g[pos^1][j-a[to[i]]]+f[to[i]]);

		}

	}

	reg int res=inf;

	for(reg int i=0;i<=a[st];i++)res=min(res,g[pos^1][i]);

	if(res==inf)return false;f[st]=res;return true;

}

int main(){

	//file("division");

n=IO::read();

	for(reg int i=2;i<=n;i++)ins(IO::read(),i);

	for(reg int i=1;i<=n;i++)a[i]=IO::read();

	puts(dfs(1)?"POSSIBLE":"IMPOSSIBLE");endfile;

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <bitset>

#define N 1005

using namespace std;

int n, s, x[N], y[N];

vector<int> a[N];

bitset<1<<20> bs;



int main() {

	int i, j, t;

	cin>>n;

	for(i=2; i<=n; i++) cin>>t, a[t].push_back(i);

	for(i=1; i<=n; i++) cin>>x[i];

	for(i=n; i>=1; i--) {

		bs = 1;

		s = 0;

		for(j=0; j<a[i].size(); j++) {

			t = a[i][j];

			bs = bs<<x[t] | bs<<y[t];

			s += x[t] + y[t];

		}

		for(j=x[i]; j>=0 && !bs[j]; j--);

		if(j<0) {cout<<"IMPOSSIBLE"; return 0;}

		else y[i] = s - j;

	}

	cout<<"POSSIBLE";

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <bitset>

#define N 1005

using namespace std;

int n, s, x[N], y[N];

vector<int> a[N];

bitset<5005> bs;



int main() {

	int i, j, t;

	cin>>n;

	for(i=2; i<=n; i++) cin>>t, a[t].push_back(i);

	for(i=1; i<=n; i++) cin>>x[i];

	for(i=n; i>=1; i--) {

		bs = 1;

		s = 0;

		for(j=0; j<a[i].size(); j++) {

			t = a[i][j];

			bs = bs<<x[t] | bs<<y[t];

			s += x[t] + y[t];

		}

		for(j=x[i]; j>=0 && !bs[j]; j--);

		if(j<0) {cout<<"IMPOSSIBLE"; return 0;}

		else y[i] = s - j;

	}

	cout<<"POSSIBLE";

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5+1;

 

 

int n,fa[N],tot[N],fr[N],a[N],b[N],c[N],cnt,head[N];

 

struct nd{int ne,to;}e[N];

 

void in(int x,int y){e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;}

int w1[5001],q[N];

void dfs(int x)

{

	for(int i=head[x];i;i=e[i].ne)dfs(e[i].to);

	if(!fr[x])return;

	q[0]=0;

	int ret=tot[x],tot1=0;

	for(int i=head[x];i;i=e[i].ne)

	{

		ret-=min(a[e[i].to],b[e[i].to]);

		q[++q[0]]=abs(a[e[i].to]-b[e[i].to]);

		tot1+=a[e[i].to]+b[e[i].to];

	}

	if(ret<0){cout<<"IMPOSSIBLE";exit(0);}

memset(w1,0,sizeof(w1));

	w1[0]=x;

	for(int i=1;i<=q[0];++i)

	for(int t=5000;t>=q[i];--t)

	if(w1[t-q[i]]==x)w1[t]=x;

	for(int i=ret;i>=0;--i)

	if(w1[i]==x){ret-=i;break;}

	a[x]=tot[x];b[x]=tot1+ret-a[x];

	return;

}

 

int main()

{

	scanf("%d",&n);

	for(int i=2;i<=n;++i)

	scanf("%d",&fa[i]),in(fa[i],i),fr[fa[i]]++;

	for(int i=1;i<=n;++i)

	{

		scanf("%d",&tot[i]);

		if(!fr[i])a[i]=tot[i],b[i]=0;

	}

	dfs(1);

	cout<<"POSSIBLE";

 

 

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>



using std::min;

using std::abs;



const int MAXN=1005,MAXW=5005;

int n;

int he[MAXN],w[MAXN],blk[MAXN],wht[MAXN];



struct line{

	int to,nex;

	line(int to=0,int nex=0):to(to),nex(nex){}

}ed[MAXN];



inline void addE(int u,int v){

	static int cnt=0;

	ed[++cnt]=line(v,he[u]);

	he[u]=cnt;

}



bool treeDP(int u){

	static int tmp[MAXN];

	static bool can[MAXW];

	for(int i=he[u];i;i=ed[i].nex){

		if(!treeDP(ed[i].to)) return false;

	}

	if(!he[u]){

		blk[u]=w[u];

		return true;

	}

	int need=w[u],sum=0;

	tmp[0]=0;

	for(int i=he[u],v;i;i=ed[i].nex){

		v=ed[i].to;

		need-=min(blk[v],wht[v]);

		if(need<0) return false;

		tmp[++tmp[0]]=abs(blk[v]-wht[v]);

		sum+=blk[v]+wht[v];

	}

	memset(can,false,sizeof(can));

	can[0]=true;

	for(int i=1;i<=tmp[0];++i){

		for(int j=MAXW-1;j>=tmp[i];--j)

			can[j]|=can[j-tmp[i]];

	}

	for(int i=need;i>=0;--i){

		if(can[i]){

			need-=i;

			break;

		}

	}

	blk[u]=w[u],wht[u]=sum-blk[u]+need;

	return true;

}



int main(){

	scanf("%d",&n);

	for(int i=2,fa;i<=n;++i){

		scanf("%d",&fa);

		addE(fa,i);

	}

	for(int i=1;i<=n;++i)

 		scanf("%d",&w[i]);

	if(treeDP(1)) printf("POSSIBLE");

	else printf("IMPOSSIBLE");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5+1;

 

 

int n,fa[N],tot[N],fr[N],blk[N],wht[N],c[N],cnt,head[N];

 

struct nd{int ne,to;}e[N];

 

void in(int x,int y){e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;}

int can[5001],tmp[N];

bool dfs(int x)

{

	for(int i=head[x];i;i=e[i].ne) if(!dfs(e[i].to)) return false;

	if(!head[x]){

		blk[x]=tot[x];

		return true;

	}

	tmp[0]=0;

	int ret=tot[x],tot1=0;

	for(int i=head[x];i;i=e[i].ne)

	{

			ret-=min(blk[e[i].to],wht[e[i].to]);

			if(ret<0) return false;

			tmp[++tmp[0]]=abs(blk[e[i].to]-wht[e[i].to]);

			tot1+=blk[e[i].to]+wht[e[i].to];

	}

	memset(can,0,sizeof(can));

	can[0]=1;

	for(int i=1;i<=tmp[0];++i)

	for(int t=5000;t>=tmp[i];--t)

		can[t]|=can[t-tmp[i]];

	for(int i=ret;i>=0;--i)

	if(can[i]){ret-=i;break;}

	blk[x]=tot[x];wht[x]=tot1+ret-blk[x];

	return true;

}

 

int main()

{

	scanf("%d",&n);

	for(int i=2;i<=n;++i)

	scanf("%d",&fa[i]),in(fa[i],i);

	for(int i=1;i<=n;++i)

	{

		scanf("%d",&tot[i]);

	}

	if(dfs(1)) cout<<"POSSIBLE";

	else cout<<"IMPOSSIBLE";

 

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>



using std::min;

using std::abs;



const int MAXN=1005,MAXW=5005;

int n;

int he[MAXN],w[MAXN],blk[MAXN],wht[MAXN];



struct line{

	int to,nex;

	line(int to=0,int nex=0):to(to),nex(nex){}

}ed[MAXN];



inline void addE(int u,int v){

	static int cnt=0;

	ed[++cnt]=line(v,he[u]);

	he[u]=cnt;

}



bool treeDP(int u){

	static int tmp[MAXN];

	static bool can[MAXW];

	for(int i=he[u];i;i=ed[i].nex){

		if(!treeDP(ed[i].to)) return false;

	}

	if(!he[u]){

		blk[u]=w[u];

		return true;

	}

	int need=w[u],sum=0;

	tmp[0]=0;

	for(int i=he[u],v;i;i=ed[i].nex){

		v=ed[i].to;

		need-=min(blk[v],wht[v]);

		if(need<0) return false;

		tmp[++tmp[0]]=abs(blk[v]-wht[v]);

		sum+=blk[v]+wht[v];

	}

	memset(can,false,sizeof(can));

	can[0]=true;

	for(int i=1;i<=tmp[0];++i){

		for(int j=MAXW-1;j>=tmp[i];--j)

			can[j]|=can[j-tmp[i]];

	}

	for(int i=need;i>=0;--i){

		if(can[i]){

			need-=i;

			break;

		}

	}

	blk[u]=w[u],wht[u]=sum-blk[u]+need;

	return true;

}



int main(){

	scanf("%d",&n);

	for(int i=2,fa;i<=n;++i){

		scanf("%d",&fa);

		addE(fa,i);

	}

	for(int i=1;i<=n;++i)

 		scanf("%d",&w[i]);

	if(treeDP(1)) printf("POSSIBLE");

	else printf("IMPOSSIBLE");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
# include <bits/stdc++.h>



# define pb push_back

# define fr first

# define sc second

# define mk make_pair



using namespace std;



typedef long long ll;

const int inf = 1e9 + 7;

const int N = 5e3 + 1;



int n, x[N], y[N];

vector <int> g[N];



void dfs(int v){

      vector <int> dp(N, 1e9);

      dp[0] = 0;

      for(int to : g[v]){

            dfs(to);

            vector <int> old(N, 1e9);

            for(int i = 0; i <= 5000; i ++){

                  if(i + x[to] <= 5000) old[i + x[to]] = min(old[i + x[to]], dp[i] + y[to]);

                  if(i + y[to] <= 5000) old[i + y[to]] = min(old[i + y[to]], dp[i] + x[to]);

            }

            dp = old;

      }

      for(int i = 0; i <= x[v]; i ++)

            y[v] = min(y[v], dp[i]);

      if(y[v] == 1e9){

            puts("IMPOSSIBLE");

            exit(0);

      }

}



int main(){

      scanf("%d", &n);



      for(int i = 2; i <= n; i ++){

            int p;

            scanf("%d", &p);

            g[p].pb(i);

      }



      for(int i = 1; i <= n; i ++){

            scanf("%d", &x[i]);

            y[i] = 1e9;

      }



      dfs(1);



      puts("POSSIBLE");

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<climits>

#define N 1010

#define MXV 5010

#define INF (INT_MAX/2-10)

#define debug(x) cerr<<#x<<"="<<x

#define sp <<" "

#define ln <<endl

using namespace std;

struct edges{

	int to,pre;

}e[N];int f[N],dp[MXV],X[N],h[N],etop;

inline int add_edge(int u,int v)

{

	return e[++etop].to=v,e[etop].pre=h[u],h[u]=etop;

}

int dfs(int x)

{

	for(int i=h[x];i;i=e[i].pre)

		if(!dfs(e[i].to)) return 0;

	for(int i=1;i<=X[x];i++) dp[i]=INF;

	for(int i=h[x]+(dp[0]=0);i;i=e[i].pre)

	{

		int a=X[e[i].to],b=f[e[i].to];

//		debug(x)sp,debug(e[i].to)sp,debug(a)sp,debug(b)ln;

		for(int j=X[x],t;j>=min(a,b);j--)

		{

			t=dp[j],dp[j]=INF;

			if(j>=a) dp[j]=min(dp[j],(a?dp[j-a]:t)+b);

			if(j>=b) dp[j]=min(dp[j],(b?dp[j-b]:t)+a);

		}

		for(int j=0;j<min(a,b);j++) dp[j]=INF;

	}

	for(int i=0;i<=X[x];i++) f[x]=min(f[x],dp[i]);

//	debug(x)sp,debug(f[x])ln;

	return f[x]<INF;

}

int main()

{

	int n;scanf("%d",&n);

	for(int i=2,x;i<=n;i++) scanf("%d",&x),add_edge(x,i);

	for(int i=1;i<=n;i++) scanf("%d",&X[i]),f[i]=INF;

	return !printf("%s\n",dfs(1)?"POSSIBLE":"IMPOSSIBLE");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define rint register int

#define gc() getchar()

inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}

vector<int> e[1025]; int f[1025][5025], X[1025], n;

void DP(int p){for(auto v:e[p]) for(rint i = (DP(v),X[p]); ~i; f[p][i] = min(i>=X[v]?f[p][i-X[v]]+f[v][X[v]]:INF,i>=f[v][X[v]]?f[p][i-f[v][X[v]]]+X[v]:INF), i--);}

int main(){n = read(); for(rint i = 2; i <= n; e[read()].push_back(i), i++); for(rint i = 1; i <= n; X[i++] = read()); DP(1); puts(f[1][X[1]]<INF?"POSSIBLE":"IMPOSSIBLE"); return 0;}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define min(a,b) ((a)<(b)?(a):(b))

#define reg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

#define endfile fclose(stdin);fclose(stdout);

namespace IO{

    char buf[1<<15],*S,*T;

    inline char gc(){

        if (S==T){

            T=(S=buf)+fread(buf,1,1<<15,stdin);

            if (S==T)return EOF;

        }

		return *S++;

    }

    inline int read(){

        reg int x;reg bool f;reg char c;

        for(f=0;(c=gc())<'0'||c>'9';f=c=='-');

        for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));

        return f?-x:x;

    }

    const int _outlim=1<<20;

    char outbuf[_outlim+5];int cnt;

    inline void pc(char c){

        outbuf[cnt++]=c;

        if (cnt==_outlim)

            fwrite(outbuf,1,cnt,stdout),cnt=0;

    }

    inline void ps(char *c){

    	reg int lim=strlen(c);

    	for(reg int i=0;i<=lim;i++)pc(c[i]);

	}

    inline void ps(const char *c){

    	reg int lim=strlen(c);

    	for(reg int i=0;i<=lim;i++)pc(c[i]);

	}

    inline void write(int x){

        if(x>9)write(x/10);pc(x%10^'0');

    }

    inline void end(){

        if(cnt)fwrite(outbuf,1,cnt,stdout);endfile;

    }

}

const int MN=1005;

const int inf=0x3f3f3f3f;

int n,a[MN],f[MN],g[2][MN*5];

int to[MN],nxt[MN],h[MN],cnt;

inline void ins(int s,int t){to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;}

bool dfs(int st){

	if(!h[st]){f[st]=0;return true;}

	for(reg int i=h[st];i;i=nxt[i])if(!dfs(to[i]))return false;

	reg int pos=1;memset(g[1],0x3f,sizeof(g[1]));g[1][0]=0;

	for(reg int i=h[st];i;i=nxt[i]){

		pos^=1;memset(g[pos],0x3f,sizeof(g[pos]));

		for(reg int j=0;j<=a[st];j++){

			if(j>=f[to[i]])g[pos][j]=min(g[pos][j],g[pos^1][j-f[to[i]]]+a[to[i]]);

			if(j>=a[to[i]])g[pos][j]=min(g[pos][j],g[pos^1][j-a[to[i]]]+f[to[i]]);

		}

	}

	reg int res=inf;

	for(reg int i=0;i<=a[st];i++)res=min(res,g[pos][i]);

	if(res==inf)return false;f[st]=res;return true;

}

int main(){

	//file("division");

	n=IO::read();

	for(reg int i=2;i<=n;i++)ins(IO::read(),i);

	for(reg int i=1;i<=n;i++)a[i]=IO::read(); 

	//IO::ps(dfs(1)?"POSSIBLE":"IMPOSSIBLE");IO::pc('\n');IO::end();

	puts(dfs(1)?"POSSIBLE":"IMPOSSIBLE");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<vector>

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define il inline

using namespace std;

typedef long long ll;

const int maxn=8010,inf=2e8;

il int gi ( ){

    int o=0,fl=1;

    char ch=getchar();

    while(!isdigit(ch))fl^=ch=='-',ch=getchar();

    while(isdigit(ch))o=o*10+ch-'0',ch=getchar();

    return fl?o:-o;

}

vector<int>p[maxn];

char s[maxn];

int f[maxn],v[maxn],dp[maxn],n;

il void dfs(int x){

    for(int i=0;i<p[x].size();i++)dfs(p[x][i]);

    memset(dp,0x3f,sizeof(dp));dp[0]=0;

    for(int ii=0;ii<p[x].size();ii++){

        int k=p[x][ii];

        for(int i=v[x];~i;--i){

            int tmp=inf;

            if(i>=v[k])tmp=min(tmp,dp[i-v[k]]+f[k]);

            if(i>=f[k])tmp=min(tmp,dp[i-f[k]]+v[k]);

            dp[i]=tmp;

        }

    }

    for(int i=v[x];i>=0;i--)

        f[x]=min(f[x],dp[i]);

    return;

}

int main(){

	n=gi();

	for(int i=2;i<=n;++i)p[gi()].push_back(i);

	for(int i=1;i<=n;++i)v[i]=gi(),f[i]=2e9;

	dfs(1);

	if(f[1]==inf)printf("IM");

	puts("POSSIBLE");

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

const int Max_N=1e3;

int N,Num,clck=0,fa[Max_N+10]={},X[Max_N+10]={},sum[Max_N+10]={},f[2][5*Max_N+10]={},lin[Max_N+10]={};

struct kk{

	int Id,Next;

} e[Max_N*2+10]={};

inline void insert(int x,int y){

	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y;

}

inline bool chck(int x){

	for(int i=lin[x];i;i=e[i].Next){

		if(!chck(e[i].Id)) return false;

		sum[x]+=sum[e[i].Id];

	}

	memset(f,0,sizeof(f)); f[0][0]=1;

	int g=1;

	for(int i=lin[x];i;i=e[i].Next,g^=1){

	 memset(f[g],0,sizeof(f[g])); 

	 for(int j=X[x];j>=0;j--){

	    if(j+X[e[i].Id]<=X[x]) f[g][j+X[e[i].Id]]|=f[g^1][j];

	 	if(j+(sum[e[i].Id]-X[e[i].Id])<=X[x]) f[g][j+(sum[e[i].Id]-X[e[i].Id])]|=f[g^1][j]; 

	 }

	} 

	for(int i=X[x];i>=0;i--){

		if(f[g^1][i]){

			sum[x]+=X[x]-i;

			return true;

		}

	}

	return false;

}

int main(){

	scanf("%d",&N);

	for(int i=2;i<=N;i++) {

		scanf("%d",&fa[i]);

		insert(fa[i],i); 

	}

	for(int i=1;i<=N;i++) scanf("%d",&X[i]);

	if(chck(1)) puts("POSSIBLE");

	else puts("IMPOSSIBLE");

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



const ll MOD = 1e9+7;



int n, m, k;

ll fac[900100];

ll fnv[900100];

ll f[600100];

ll p[600100];



ll po(ll a, ll n) {

    if (!n) return 1;

    ll t = po(a,n/2);

    return t*t%MOD*(n%2?a:1)%MOD;

}



ll comb(ll n, ll r) {

    if (r<0||r>n) return 0;

    return fac[n]*fnv[r]%MOD*fnv[n-r]%MOD;

}



int main() {

    int i;

    scanf("%d%d%d",&n,&m,&k);

    fac[0] = 1; for (i=1;i<=n+m+k;i++) fac[i]=fac[i-1]*i%MOD;

    for (i=0;i<=n+m+k;i++) fnv[i]=po(fac[i],MOD-2);

    f[m+k] = comb(m+k,m); for (i=m+k-1;i>=0;i--) f[i] = (MOD+1)/2*(f[i+1]+comb(i,i-m)+comb(i,k))%MOD;

    p[0] = 1; for (i=1;i<=m+k;i++) p[i]=p[i-1]*3%MOD;

    ll ans = 0;

    for (i=0;i<=m+k;i++) ans = ans+comb(n-1+i,n-1)*p[m+k-i]%MOD*f[i]%MOD;

    printf("%lld\n",ans%MOD);



    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



const ll MOD = 1e9+7;



int n, m, k;

ll fac[900100];

ll inv[900100];

ll fnv[900100];

ll f[600100];

ll p[600100];



ll po(ll a, ll n) {

    if (!n) return 1;

    ll t = po(a,n/2);

    return t*t%MOD*(n%2?a:1)%MOD;

}



ll comb(ll n, ll r) {

    if (r<0||r>n) return 0;

    return fac[n]*fnv[r]%MOD*fnv[n-r]%MOD;

}



int main() {

    int i;

    scanf("%d%d%d",&n,&m,&k);

    fac[0] = 1; for (i=1;i<=n+m+k;i++) fac[i]=fac[i-1]*i%MOD;

    inv[1] = 1; for (i=2;i<=n+m+k;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;

    fnv[0] = 1; for (i=1;i<=n+m+k;i++) fnv[i]=fnv[i-1]*inv[i]%MOD;

    f[m+k] = comb(m+k,m); for (i=m+k-1;i>=0;i--) f[i] = (MOD+1)/2*(f[i+1]+comb(i,i-m)+comb(i,k))%MOD;

    p[0] = 1; for (i=1;i<=m+k;i++) p[i]=p[i-1]*3%MOD;

    ll ans = 0;

    for (i=0;i<=m+k;i++) ans = ans+comb(n-1+i,n-1)*p[m+k-i]%MOD*f[i]%MOD;

    printf("%lld\n",ans%MOD);



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define per(i,a,b) for(int i=a;i>=b;i--)

#define gpf(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

typedef long long ll;

const ll md = 1e9 + 7;

const int N = 1000000;

ll n, m, k;

ll fac[N], inv[N], m3[N];



ll fm(ll x, ll y){

	ll res = 1;

	while (y){

		if (y & 1) res = (res * x) % md;

		y /= 2;

		x = (x * x) % md;

	}

	return res;

}



ll C(int x, int y){

	if (y < 0) return 0;

	if (x < y) return 0;

	ll res = ((fac[x] * inv[x - y]) % md * inv[y]) % md;

	return res;

}



int main(){

	scanf("%lld%lld%lld", &n, &m, &k);

	fac[0] = 1;

	rep(i, 1, n + m + k) fac[i] = (fac[i - 1] * i) % md;

	rep(i, 1, n + m + k) inv[i] = fm(fac[i], md - 2);

	m3[0] = 1;

	rep(i, 1, n + m + k) m3[i] = (m3[i - 1] * 3) % md;

	inv[0] = 1;

	ll ans = 0;

	ll t = 1;

	rep(i, 0, m + k){

		ll tt = C(n + i - 1, n - 1) * t % md;

		tt = tt * m3[m + k - i] % md;

		ans = (ans + tt) % md;

		t = ((t * 2 + md - C(i, m)) % md + md - C(i, i - k)) % md;

	}

	printf("%lld\n", ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <algorithm>



typedef long long LL;



const int maxn = 1e6 + 20;

const int mod = 1e9 + 7;



int N, M, K, sum;

LL fac[maxn];

LL inv[maxn];

LL pw[maxn];

 

LL powermod(LL x,LL y)

{

	LL z = 1;

	

	while(y)

	{

		if(y & 1) z = z * x % mod;

		x = x * x % mod, y >>= 1;

	}

	

	return z;

}

LL combine(LL x,LL y)

{

	if(y < 0 || y > x) return 0;

	return fac[x] * inv[y] % mod * inv[x - y] % mod;

}

int main()

{

	scanf("%d%d%d", &N, &M, &K);

	sum = N + M + K;

	

	pw[0] = fac[0] = inv[0] = 1;

	for(int i = 1; i <= sum; i++)

	{

		pw[i] = pw[i - 1] * 3 % mod;

		fac[i] = fac[i - 1] * i % mod;

	}

	

	inv[sum] = powermod(fac[sum], mod - 2);

	for(int i = sum - 1; i >= 1; i--)

	{

		inv[i] = inv[i + 1] * (i + 1) % mod;

	}

	

	LL s = 1, ans = 0;

	

	for(int i = 0; i <= M + K; i++)

	{

		ans += s * combine(N - 1 + i, N - 1) % mod * pw[M + K - i] % mod;

		s = s * 2 - combine(i, M) - combine(i, K);

		s = (s % mod + mod) % mod;

	}

	ans %= mod;

	

	printf("%d", (int) ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

const long long mod=1e9+7;

long long jc[6060606],_jc[6060606];

long long pow(long long n,long long k)

{

	long long ret=1;

	while(k>0)

	{

		if(k&1)

			ret=ret*n%mod;

		n=n*n%mod;

		k/=2;

	}

	return ret;

}

long long C(int n,int m)

{

	return jc[n]*_jc[m]%mod*_jc[n-m]%mod;

}

int main()

{

	int n,m,k;

	cin>>n>>m>>k;

	jc[0]=1;

	_jc[0]=1;

	for(int i=1;i<=n+m+k;i++)

	{

		jc[i]=jc[i-1]*i%mod;

		_jc[i]=pow(jc[i],mod-2);

	}

	long long tmp=1,ans=0;

	for(int i=0;i<=m+k;i++)

	{

		ans=(ans+C(n+i-1,i)*tmp%mod*pow(3,m+k-i)%mod)%mod;

		tmp*=2;

		if(i+1>k)

			tmp-=C(i,i-k); 

		if(i+1>m)

			tmp-=C(i,m);

		tmp+=2*mod;

		tmp%=mod;

	}

	cout<<ans<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <algorithm>



typedef long long LL;



const int maxn = 1e6 + 20;

const int mod = 1e9 + 7;



int N, M, K, sum;

LL fac[maxn];

LL inv[maxn];

LL pw[maxn];

 

LL powermod(LL x,LL y)

{

	LL z = 1;

	

	while(y)

	{

		if(y & 1) z = z * x % mod;

		x = x * x % mod, y >>= 1;

	}

	

	return z;

}

LL combine(LL x,LL y)

{

	if(y < 0 || y > x) return 0;

	return fac[x] * inv[y] % mod * inv[x - y] % mod;

}

int main()

{

	scanf("%d%d%d", &N, &M, &K);

	sum = N + M + K;

	

	pw[0] = fac[0] = inv[0] = 1;

	for(int i = 1; i <= sum; i++)

	{

		pw[i] = pw[i - 1] * 3 % mod;

		fac[i] = fac[i - 1] * i % mod;

	}

	

	inv[sum] = powermod(fac[sum], mod - 2);

	for(int i = sum - 1; i >= 1; i--)

	{

		inv[i] = inv[i + 1] * (i + 1) % mod;

	}

	

	LL s = 1, ans = 0;

	

	for(int i = 0; i <= M + K; i++)

	{

		ans += s * combine(N - 1 + i, N - 1) % mod * pw[M + K - i] % mod;

		s = s * 2 - combine(i, M) - combine(i, K);

		s = (s % mod + mod) % mod;

	}

	ans %= mod;

	

	printf("%d", (int) ans);

	return 0;

}

// Fastest known solution for this problem: