瓦西里熊喜欢美丽的琴弦。如果字符串 s 满足以下条件,则它是美丽的:
1. 字符串 s 仅由字符 0 和 1 组成,此时字符 0 必须在字符串 s 中恰好出现 n 次,字符 1 必须恰好出现 m 次。
2. We can obtain character g from string s with some (possibly, zero) number of modifications.字符 g 等于 0 或 1。
长度至少为 2 的字符串的修改是以下操作:我们用另一个字符替换字符串中的最后两个字符。 This character equals one if it replaces two zeros, otherwise it equals zero.例如,一次修改将字符串“01010”转换为字符串“0100”,两次修改将其转换为“011”。禁止修改长度小于2的字符串。
帮助小熊,数数美丽的绳子。由于漂亮字符串的数量可能相当大,因此打印该数字除以 1000000007 (109 + 7) 后的余数。
输入
输入的第一行包含三个空格分隔的整数 n, m, g (0 ≤ n, m ≤ 105, n + m ≥ 1, 0 ≤ g ≤ 1)。
输出
打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
1 1 0
输出 #1
2
输入 #2
2 2 0
输出 #2
4
输入 #3
1 1 1
输出 #3
0
注意
在第一个示例中,漂亮的字符串是:“01”、“10”。
在第二个示例中,漂亮的字符串是:“0011”、“1001”、“1010”、“1100”。
在第三个样本中没有漂亮的字符串。