Alice, Bob and Charlie are playing Card Game for Three, as below:

* At first, each of the three players has a deck consisting of some number of cards. Alice's deck has N cards, Bob's deck has M cards, and Charlie's deck has K cards. Each card has a letter `a`, `b` or `c` written on it. The orders of the cards in the decks cannot be rearranged.
* The players take turns. Alice goes first.
* If the current player's deck contains at least one card, discard the top card in the deck. Then, the player whose name begins with the letter on the discarded card, takes the next turn. (For example, if the card says `a`, Alice takes the next turn.)
* If the current player's deck is empty, the game ends and the current player wins the game.



There are 3^{N+M+K} possible patters of the three player's initial decks. Among these patterns, how many will lead to Alice's victory?

Since the answer can be large, print the count modulo 1\,000\,000\,007 (=10^9+7).

Constraints

* 1 \leq N \leq 3×10^5
* 1 \leq M \leq 3×10^5
* 1 \leq K \leq 3×10^5

Input

The input is given from Standard Input in the following format:


N M K


Output

Print the answer modulo 1\,000\,000\,007 (=10^9+7).

Examples

Input

1 1 1


Output

17


Input

4 2 2


Output

1227


Input

1000 1000 1000


Output

261790852
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 1e6 + 5 ; 
const int P = 1e9 + 7 ; 
int a, b, c, n, m, Ans, fac[N], inv[N] ; 
int fpow( int x, int k ) {
	int ans = 1, base = x ;
	while(k) {
		if( k & 1 ) ans = ans * base % P ; 
		base = base * base % P, k >>= 1 ; 
	} return ans % P ; 
}
int C( int x, int y ) {
	if( y > x || x < 0 || y < 0 ) return 0 ; 
	return fac[x] * inv[y] % P * inv[x - y] % P ; 
}
signed main()
{
	a = gi(), b = gi(), c = gi() ; 
	n = a + b + c, fac[0] = inv[0] = 1 ; 
	rep( i, 1, n ) fac[i] = fac[i - 1] * i % P, inv[i] = fpow( fac[i], P - 2 ) ;
	int f = 1, l = - c ; -- a ; 
	for( re int i = a; i < n; ++ i ) {
		int x = i - a ; 
		if( l > b ) break ; 
		Ans = ( Ans + f * C( i, a ) % P * fpow( 3, n - i - 1 ) % P ) % P ;
		f = ( f * 2 + P - C( x, b ) + P - C( x, l ) ) % P, ++ l ; 
	}
	printf("%lld\n", Ans % P ) ;
	return 0 ;
}