stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
# 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");

}


// Faster C++ solution for the same problem (measured speedup: 1.196561160621133x):
#include <bits/stdc++.h>



#define INF 0x3f3f3f3f



template<typename T>

inline int cmin(T &x, T y) {

	return x > y ? x = y, 1 : 0;

}



const int MAXN = 1009, MAXW = 5009;



int n, w[MAXN];

struct Edge { 

	int ver, nxt; 

} e[MAXN];

int head[MAXN], tot = 0;



inline void Add(int x, int y) {

	e[++tot].ver = y, e[tot].nxt = head[x], head[x] = tot;

}



int f[MAXN], g[MAXW];



void Dfs(int x) {

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

		int y = e[i].ver;

		Dfs(y); // 要先知道所有儿子节点的信息 

	}

	

	memset(g, 0x3f, sizeof g);

	g[0] = 0;

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

		int y = e[i].ver;

		for (int j = w[x]; ~j; --j) {

			int trans = INF; // 特判 j = 0 的情况 

			if (j >= w[y])

				cmin(trans, g[j - w[y]] + f[y]);

			if (j >= f[y])

				cmin(trans, g[j - f[y]] + w[y]);

			g[j] = trans;

		}

	}

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

		cmin(f[x], g[i]);

}



int main() {

	scanf("%d", &n);

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

		int f;

		scanf("%d", &f);

		Add(f, i);

	}

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

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



	memset(f, 0x3f, sizeof f);



	Dfs(1);



	puts(f[1] == INF ? "IMPOSSIBLE" : "POSSIBLE");



	return 0;

}
// Slower C++ solution:
#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;}

// Faster C++ solution for the same problem (measured speedup: 4.938431470301294x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.1166034601600867x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.3057201622103356x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.2985305222105767x):
#include<bits/stdc++.h>



#define mo 1000000007



using namespace std;



int fac[900030],inv[900030],Pow3[900030];



int power(int x,int m)

{

	int nowans=1;

	while(m)

	{

		if(m&1)nowans=1ll*nowans*x%mo;

		x=1ll*x*x%mo;

		m>>=1;

	}

	return nowans;

}



inline int C(int n,int m)

{

	if(n<m)return 0;

	return (int)(1ll*fac[n]*inv[m]%mo*inv[n-m]%mo);

}



int main()

{

	int n,m,k,N;

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

	N=n+m+k;

	Pow3[0]=1;

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

		Pow3[i]=3ll*Pow3[i-1]%mo;

	fac[0]=1;

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

		fac[i]=1ll*fac[i-1]*i%mo;

	inv[N]=power(fac[N],mo-2);

	for(int i=N;i;i--)

		inv[i-1]=1ll*inv[i]*i%mo;

	int ans=0,nowans=1;

	for(int l=n+1;l<=N+1;l++)

	{

		ans+=1ll*C(l-2,n-1)*nowans%mo*Pow3[N+1-l]%mo;

		if(ans>=mo)ans-=mo;

		nowans=nowans*2%mo;

		nowans-=(C(l-(n+1),m)+C(l-(n+1),k))%mo;

		if(nowans<0)nowans+=mo;

	}

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

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.2755542889708684x):
#include<cstring>

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;



typedef long long ll;

const int maxn = 900010,rhl = 1000000007;

int N,M,K; ll jie[maxn],inv[maxn],mi[maxn];



inline ll qsm(ll a,int b)

{

	ll ret = 1;

	for (;b;b >>= 1,(a *= a) %= rhl) if (b&1) (ret *= a) %= rhl;

	return ret;

}



inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');

	return ret*f;

}



inline ll C(int n,int m) { if (n < m||m < 0) return 0; return jie[n]*inv[m]%rhl*inv[n-m]%rhl; }



int main()

{

	//freopen("H.in","r",stdin);

	//freopen("H.out","w",stdout);

	N = gi(); M = gi(); K = gi();

	jie[0] = mi[0] = 1;

	for (int i = 1;i <= N+M+K;++i)

	{

		mi[i] = mi[i-1]*3LL; while (mi[i] >= rhl) mi[i] -= rhl;

		jie[i] = jie[i-1]*(ll)i; if (jie[i] >= rhl) jie[i] %= rhl;

	}

	inv[N+M+K] = qsm(jie[N+M+K],rhl-2);

	for (int i = N+M+K;i;--i)

	{

		inv[i-1] = inv[i]*(ll)i;

		if (inv[i-1] >= rhl) inv[i-1] %= rhl;

	}

	ll sum = 1,ans = 0;

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

	{

		ll tm = C(N+i-1,i)*mi[M+K-i]%rhl;

		ans += tm*sum%rhl; if (ans >= rhl) ans %= rhl;

		sum <<= 1; if (sum >= rhl) sum -= rhl;

		sum -= C(i,i-K)+C(i,M); while (sum < 0) sum += rhl;

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3955377579871557x):
#include<cstring>

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;



typedef long long ll;

const int maxn = 900010,rhl = 1000000007;

int N,M,K; ll jie[maxn],inv[maxn],mi[maxn];



inline ll qsm(ll a,int b)

{

	ll ret = 1;

	for (;b;b >>= 1,(a *= a) %= rhl) if (b&1) (ret *= a) %= rhl;

	return ret;

}



inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');

	return ret*f;

}



inline ll C(int n,int m) { if (n < m||m < 0) return 0; return jie[n]*inv[m]%rhl*inv[n-m]%rhl; }



int main()

{

	//freopen("H.in","r",stdin);

	//freopen("H.out","w",stdout);

	N = gi(); M = gi(); K = gi();

	jie[0] = mi[0] = 1;

	for (int i = 1;i <= N+M+K;++i)

	{

		mi[i] = mi[i-1]*3LL; while (mi[i] >= rhl) mi[i] -= rhl;

		jie[i] = jie[i-1]*(ll)i; if (jie[i] >= rhl) jie[i] %= rhl;

	}

	inv[N+M+K] = qsm(jie[N+M+K],rhl-2);

	for (int i = N+M+K;i;--i)

	{

		inv[i-1] = inv[i]*(ll)i;

		if (inv[i-1] >= rhl) inv[i-1] %= rhl;

	}

	ll sum = 1,ans = 0;

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

	{

		ll tm = C(N+i-1,i)*mi[M+K-i]%rhl;

		ans += tm*sum%rhl; if (ans >= rhl) ans %= rhl;

		sum <<= 1; if (sum >= rhl) sum -= rhl;

		sum -= C(i,i-K)+C(i,M); while (sum < 0) sum += rhl;

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.259161811189239x):
#include <bits/stdc++.h>

using namespace std;



const int Mod = 1e9 + 7;

const int N = 9e5 + 10;



int n, m, k;

long long fac[N], vfac[N];



long long mpow( long long a, int b ) {

	long long rt;

	for( rt = 1; b; b >>= 1, a = (a * a) % Mod )

		if( b & 1 ) rt = (rt * a) % Mod;

	return rt;

}

void init( int n ) {

	fac[0] = 1;

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

		fac[i] = (fac[i-1] * i) % Mod;

	vfac[n]  = mpow( fac[n], Mod - 2 );

	for( int i = n - 1; i >= 0; i-- )

		vfac[i] = vfac[i+1] * (i + 1) % Mod;

}

long long comb( int n, int m ) {

	return fac[n] * vfac[n-m] % Mod * vfac[m] % Mod;

}

int main() {

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

	if( m < k )

	   	swap( m, k );

	init( m + k + n );

	long long sum = 0;

	long long ans = 0;

	for( int s = 0; s <= m + k; s++ ) {

		if( s == 0 ) 

			sum = 1;

		else if( s <= k ) 

			sum = (sum<<1) % Mod;

		else if( s <= m ) 

			sum = ((sum<<1) + Mod - comb(s-1,s-k-1)) % Mod;

		else 

			sum = ((sum<<1) + Mod - comb(s-1,s-k-1) + Mod - comb(s-1,m)) % Mod;

		long long sub = sum * comb(n-1+s,n-1) % Mod * mpow(3,m+k-s) % Mod;

		ans = (ans + sub) % Mod;

	}

	cout << ans << endl;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.271342821232559x):
#include <bits/stdc++.h>

using namespace std;



const int Mod = 1e9 + 7;

const int N = 9e5 + 10;



int n, m, k;

long long fac[N], vfac[N];



long long mpow( long long a, int b ) {

	long long rt;

	for( rt = 1; b; b >>= 1, a = (a * a) % Mod )

		if( b & 1 ) rt = (rt * a) % Mod;

	return rt;

}

void init( int n ) {

	fac[0] = 1;

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

		fac[i] = (fac[i-1] * i) % Mod;

	vfac[n]  = mpow( fac[n], Mod - 2 );

	for( int i = n - 1; i >= 0; i-- )

		vfac[i] = vfac[i+1] * (i + 1) % Mod;

}

long long comb( int n, int m ) {

	return fac[n] * vfac[n-m] % Mod * vfac[m] % Mod;

}

int main() {

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

	if( m < k ) swap( m, k );

	init( m + k + n );

	long long sum = 0, ans = 0;

	for( int s = 0; s <= m + k; s++ ) {

		if( s == 0 ) 

			sum = 1;

		 else if( s <= k ) 

			sum = (sum<<1) % Mod;

	 else if( s <= m ) 

			sum = ((sum<<1) + Mod - comb(s-1,s-k-1)) % Mod;

		 else 

			sum = ((sum<<1) + Mod - comb(s-1,s-k-1) + Mod - comb(s-1,m)) % Mod;

		

		long long sub = sum * comb(n-1+s,n-1) % Mod * mpow(3,m+k-s) % Mod;

		ans = (ans + sub) % Mod;

	}

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

}
// Slower C++ solution:
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

using namespace std;



const int MOD = 1e9 + 7;



int n, m, k;

int pow1[1010101], pow2[1010101];

int fac[1010101], rev[1010101], ifac[1010101];



int c(int a, int b)

{

	long long ret = fac[b];

	ret = ret * ifac[a];

	ret %= MOD;

	ret = ret * ifac[b - a];

	ret %= MOD;

	return (int)ret;

}



int main()

{

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

	pow1[0] = fac[0] = ifac[0] = rev[0] = pow2[0] = 1;

	ifac[1] = rev[1] = 1;

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

	{

		pow1[i] = pow1[i - 1] * 3ll % MOD;

		pow2[i] = pow2[i - 1] * 2 % MOD;

		fac[i] = fac[i - 1] * 1ll * i % MOD;

		if(i >= 2)

		{

			rev[i] = MOD - 1ll * (MOD / i) * rev[MOD % i] % MOD;

			ifac[i] = 1ll * ifac[i - 1] * rev[i] % MOD;

		}

	}

	if(m > k)

		swap(m, k);

	int ans = 0;

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

	{

		ans += 1ll * pow2[i] * c(i, i + n - 1) % MOD * pow1[m + k - i] % MOD;

		if(ans >= MOD)

			ans -= MOD;

	}

	int lst = pow2[m];

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

	{

		lst = lst<<1;

		lst -= c(m, i - 1);

		if(lst >= MOD)

			lst -= MOD;

		if(i > k)

			lst -= c(i - k - 1, i - 1);

		while(lst < 0)

			lst += MOD;

		while(lst >= MOD)

			lst -= MOD;

		ans += 1ll * lst * c(i, i + n - 1) % MOD * pow1[m + k - i] % MOD;

		if(ans >= MOD)

			ans -= MOD;

	}

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

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.9738771223581797x):
#include <cstdio>

using namespace std;



typedef long long ll;



const int maxn = 9e5 + 5;

const int mod = 1e9 + 7;



int n, m, k, Q;

ll ans;

ll f[maxn], fac[maxn], inv[maxn], bin[maxn];



ll power(ll b, int k)

{

    ll res = 1;

    for(; k; k >>= 1, b = b * b % mod)

        if(k & 1)

            res = res * b % mod;

    return res;

}



ll C(int n, int m)

{

    if(m > n)

        return 0;

    return fac[n] * inv[m] % mod * inv[n - m] % mod;

}



int main()

{

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

    Q = m + k;

    f[0] = fac[0] = bin[0] = inv[0] = 1;

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

    {

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

        inv[i] = power(fac[i], mod - 2);

    }

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

    {

        f[i] = ((f[i - 1] << 1) - C(i - 1, m) - C(i - 1, k) + (mod << 1)) % mod;

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

    }

    for(int i = 0; i <= Q; i++)

    {

        ll tmp = C(i + n - 1, n - 1) * f[i] % mod * bin[Q - i] % mod;

        ans += tmp;

        if(ans >= mod)

            ans -= mod;

    }

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

    return 0;

}