Vasily the Bear and Beautiful Strings

Vasily the Bear 喜欢美丽字符串。一个字符串 s 称为美丽字符串是指它满足下面的两个条件： 1、s 仅由 0 和 1 构成，0 恰好出现了 n 次，1 恰好出现了 m 次。 2、能将 s 通过若干次（可能是零次）修改得到字符 g，字符 g 是0 或 1。 一次修改是指下面的操作：一个长度至少是 2 的字符串，将该字符串的最后两个字符用另一个字符代替。代替规则：如果最后两个字符都是 0，那么用 1 代替；否则，用 0 代替。例如：一次修改后，字符串” 01010”变成” 0100”，两次修改后变成”011”。禁止修改长度小于2 的字符串。 你的任务是计算总共有多少种满足条件的美丽字符串。最后结果对 10^9+7取模。 Translated by @BobHuang0724

Vasily the Bear loves beautiful strings. String $ s $ is beautiful if it meets the following criteria: 1. String $ s $ only consists of characters $ 0 $ and $ 1 $ , at that character $ 0 $ must occur in string $ s $ exactly $ n $ times, and character $ 1 $ must occur exactly $ m $ times. 2. We can obtain character $ g $ from string $ s $ with some (possibly, zero) number of modifications. The character $ g $ equals either zero or one. A modification of string with length at least two is the following operation: we replace two last characters from the string by exactly one other character. This character equals one if it replaces two zeros, otherwise it equals zero. For example, one modification transforms string "01010" into string "0100", two modifications transform it to "011". It is forbidden to modify a string with length less than two. Help the Bear, count the number of beautiful strings. As the number of beautiful strings can be rather large, print the remainder after dividing the number by $ 1000000007 $ $ (10^{9}+7) $ .

The first line of the input contains three space-separated integers $ n,m,g $ $ (0<=n,m<=10^{5},n+m>=1,0<=g<=1) $ .

Print a single integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

1 1 0

2

2 2 0

4

1 1 1

0

In the first sample the beautiful strings are: "01", "10". In the second sample the beautiful strings are: "0011", "1001", "1010", "1100". In the third sample there are no beautiful strings.