← 返回题目列表

Codeforces · 336/D

D. 瓦西里熊和美丽的琴弦

中文机器翻译题面 查看原题

瓦西里熊喜欢美丽的琴弦。如果字符串 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”。

在第三个样本中没有漂亮的字符串。