package main import ( "bufio" "errors" "fmt" "io" "math" "os" "strconv" ) /*********** I/O ***********/ var ( // ReadString returns a WORD string. ReadString func() string stdout *bufio.Writer ) func init() { ReadString = newReadString(os.Stdin) stdout = bufio.NewWriter(os.Stdout) } func newReadString(ior io.Reader) func() string { r := bufio.NewScanner(ior) // r.Buffer(make([]byte, 1024), int(1e+11)) // for AtCoder r.Buffer(make([]byte, 1024), int(1e+9)) // for Codeforces // Split sets the split function for the Scanner. The default split function is ScanLines. // Split panics if it is called after scanning has started. r.Split(bufio.ScanWords) return func() string { if !r.Scan() { panic("Scan failed") } return r.Text() } } // ReadInt returns an integer. func ReadInt() int { return int(readInt64()) } func ReadInt2() (int, int) { return int(readInt64()), int(readInt64()) } func ReadInt3() (int, int, int) { return int(readInt64()), int(readInt64()), int(readInt64()) } func ReadInt4() (int, int, int, int) { return int(readInt64()), int(readInt64()), int(readInt64()), int(readInt64()) } // ReadInt64 returns as integer as int64. func ReadInt64() int64 { return readInt64() } func ReadInt64_2() (int64, int64) { return readInt64(), readInt64() } func ReadInt64_3() (int64, int64, int64) { return readInt64(), readInt64(), readInt64() } func ReadInt64_4() (int64, int64, int64, int64) { return readInt64(), readInt64(), readInt64(), readInt64() } func readInt64() int64 { i, err := strconv.ParseInt(ReadString(), 0, 64) if err != nil { panic(err.Error()) } return i } // ReadIntSlice returns an integer slice that has n integers. func ReadIntSlice(n int) []int { b := make([]int, n) for i := 0; i < n; i++ { b[i] = ReadInt() } return b } // ReadInt64Slice returns as int64 slice that has n integers. func ReadInt64Slice(n int) []int64 { b := make([]int64, n) for i := 0; i < n; i++ { b[i] = ReadInt64() } return b } // ReadFloat64 returns an float64. func ReadFloat64() float64 { return float64(readFloat64()) } func readFloat64() float64 { f, err := strconv.ParseFloat(ReadString(), 64) if err != nil { panic(err.Error()) } return f } // ReadFloatSlice returns an float64 slice that has n float64. func ReadFloat64Slice(n int) []float64 { b := make([]float64, n) for i := 0; i < n; i++ { b[i] = ReadFloat64() } return b } // ReadRuneSlice returns a rune slice. func ReadRuneSlice() []rune { return []rune(ReadString()) } /*********** Debugging ***********/ // ZeroPaddingRuneSlice returns binary expressions of integer n with zero padding. // For debugging use. func ZeroPaddingRuneSlice(n, digitsNum int) []rune { sn := fmt.Sprintf("%b", n) residualLength := digitsNum - len(sn) if residualLength <= 0 { return []rune(sn) } zeros := make([]rune, residualLength) for i := 0; i < len(zeros); i++ { zeros[i] = '0' } res := []rune{} res = append(res, zeros...) res = append(res, []rune(sn)...) return res } /*********** DP sub-functions ***********/ // ChMin accepts a pointer of integer and a target value. // If target value is SMALLER than the first argument, // then the first argument will be updated by the second argument. func ChMin(updatedValue *int, target int) bool { if *updatedValue > target { *updatedValue = target return true } return false } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false } // NthBit returns nth bit value of an argument. // n starts from 0. func NthBit(num, nth int) int { return num >> uint(nth) & 1 } // OnBit returns the integer that has nth ON bit. // If an argument has nth ON bit, OnBit returns the argument. func OnBit(num, nth int) int { return num | (1 << uint(nth)) } // OffBit returns the integer that has nth OFF bit. // If an argument has nth OFF bit, OffBit returns the argument. func OffBit(num, nth int) int { return num & ^(1 << uint(nth)) } // PopCount returns the number of ON bit of an argument. func PopCount(num int) int { res := 0 for i := 0; i < 70; i++ { if ((num >> uint(i)) & 1) == 1 { res++ } } return res } /*********** Arithmetic ***********/ // Max returns the max integer among input set. // This function needs at least 1 argument (no argument causes panic). func Max(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m < integer { m = integer } } return m } // Min returns the min integer among input set. // This function needs at least 1 argument (no argument causes panic). func Min(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m > integer { m = integer } } return m } // DigitSum returns digit sum of a decimal number. // DigitSum only accept a positive integer. func DigitSum(n int) int { if n < 0 { return -1 } res := 0 for n > 0 { res += n % 10 n /= 10 } return res } // DigitNumOfDecimal returns digits number of n. // n is non negative number. func DigitNumOfDecimal(n int) int { res := 0 for n > 0 { n /= 10 res++ } return res } // Sum returns multiple integers sum. func Sum(integers ...int) int { s := 0 for _, i := range integers { s += i } return s } // Kiriage returns Ceil(a/b) // a >= 0, b > 0 func Kiriage(a, b int) int { return (a + (b - 1)) / b } // PowInt is integer version of math.Pow // PowInt calculate a power by Binary Power (二分累乗法(O(log e))). func PowInt(a, e int) int { if a < 0 || e < 0 { panic(errors.New("[argument error]: PowInt does not accept negative integers")) } if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := PowInt(a, halfE) return half * half } return a * PowInt(a, e-1) } // AbsInt is integer version of math.Abs func AbsInt(a int) int { if a < 0 { return -a } return a } // Gcd returns the Greatest Common Divisor of two natural numbers. // Gcd only accepts two natural numbers (a, b >= 1). // 0 or negative number causes panic. // Gcd uses the Euclidean Algorithm. func Gcd(a, b int) int { if a <= 0 || b <= 0 { panic(errors.New("[argument error]: Gcd only accepts two NATURAL numbers")) } if a < b { a, b = b, a } // Euclidean Algorithm for b > 0 { div := a % b a, b = b, div } return a } // Lcm returns the Least Common Multiple of two natural numbers. // Lcd only accepts two natural numbers (a, b >= 1). // 0 or negative number causes panic. // Lcd uses the Euclidean Algorithm indirectly. func Lcm(a, b int) int { if a <= 0 || b <= 0 { panic(errors.New("[argument error]: Gcd only accepts two NATURAL numbers")) } // a = a'*gcd, b = b'*gcd, a*b = a'*b'*gcd^2 // a' and b' are relatively prime numbers // gcd consists of prime numbers, that are included in a and b gcd := Gcd(a, b) // not (a * b / gcd), because of reducing a probability of overflow return (a / gcd) * b } // Strtoi is a wrapper of `strconv.Atoi()`. // If `strconv.Atoi()` returns an error, Strtoi calls panic. func Strtoi(s string) int { if i, err := strconv.Atoi(s); err != nil { panic(errors.New("[argument error]: Strtoi only accepts integer string")) } else { return i } } // PrintIntsLine returns integers string delimited by a space. func PrintIntsLine(A ...int) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.Itoa(A[i]) res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) } /********** I/O usage **********/ //str := ReadString() //i := ReadInt() //X := ReadIntSlice(n) //S := ReadRuneSlice() //a := ReadFloat64() //A := ReadFloat64Slice(n) //str := ZeroPaddingRuneSlice(num, 32) //str := PrintIntsLine(X...) /*******************************************************************/ const MOD = 1000000000 + 7 const ALPHABET_NUM = 26 const INF_INT64 = math.MaxInt64 const INF_BIT60 = 1 << 60 var beki [400000 + 10]int var sumBeki [400000 + 10]int func main() { a, b, c := ReadInt3() ans := 0 cf := NewCombFactorial() cf.InitCF() beki[0] = 1 for i := 1; i < 400000+3; i++ { beki[i] = 2 * beki[i-1] beki[i] %= MOD } for i := 0; i < 400000+3; i++ { sumBeki[i+1] = sumBeki[i] + beki[i] sumBeki[i+1] %= MOD } for i := b + c - 1; i < a+b+c-1; i++ { m := sumBeki[i] * cf.C(i-1, c-1) m %= MOD m *= cf.C(i-c, b-1) m %= MOD ans += m ans %= MOD } fmt.Println(ans) } type CombFactorial struct { factorial, modFactorial [400001]int } func NewCombFactorial() *CombFactorial { cf := new(CombFactorial) return cf } func (c *CombFactorial) modInv(a int) int { return c.modpow(a, MOD-2) } func (c *CombFactorial) modpow(a, e int) int { if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := c.modpow(a, halfE) return half * half % MOD } return a * c.modpow(a, e-1) % MOD } func (c *CombFactorial) InitCF() { for i := 0; i <= 400000; i++ { if i == 0 { c.factorial[i] = 1 c.modFactorial[i] = c.modInv(c.factorial[i]) continue } num := i * c.factorial[i-1] num %= MOD c.factorial[i] = num c.modFactorial[i] = c.modInv(c.factorial[i]) } } func (c *CombFactorial) C(n, r int) int { res := 1 res *= c.factorial[n] res %= MOD res *= c.modFactorial[r] res %= MOD res *= c.modFactorial[n-r] res %= MOD return res } func (c *CombFactorial) P(n, r int) int { res := 1 res *= c.factorial[n] res %= MOD res *= c.modFactorial[n-r] res %= MOD return res } func (c *CombFactorial) H(n, r int) int { return c.C(n-1+r, r) } // cf = NewCombFactorial() // cf.InitCF() // res := cf.C(n, r) // 組み合わせ // res := cf.H(n, r) // 重複組合せ // res := cf.P(n, r) // 順列 var cf *CombFactorial // MODはとったか? // 遷移だけじゃなくて最後の最後でちゃんと取れよ? /*******************************************************************/