D. Медведь Василий и красивые строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Медведь Василий любит красивые строки. Будем называть строку s красивой, если выполнены следующие условия:

  1. Строка s состоит только из символов 0 и 1, причем символ 0 должен встречаться в строке s ровно n раз, а символ 1 — ровно m раз.
  2. За некоторое (возможно нулевое) количество модификаций из строки s можно получить любимый символ g, который равен либо нулю, либо единице.

Модификацией строки, длина которой не меньше двух, будем называть следующую операцию: из строки удаляются два последних символа, а на их место ставится ровно один другой символ, который будет равен единице, если оба удаленных символа были равны нулю, и нулю иначе. Например, в результате одной модификации из строки «01010» получится строка «0100», в результате двух — «011». Применять модификацию к строке длины меньше чем два запрещено.

Помогите Медведю, посчитайте количество красивых строк. Так как количество красивых строк может быть очень большим, выведите остаток от деления этого количества на 1000000007 (109 + 7).

Входные данные

В первой строке входных данных записаны три целых числа через пробел n, m, g (0 ≤ n, m ≤ 105, n + m ≥ 1, 0 ≤ g ≤ 1).

Выходные данные

Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1 1 0
Выходные данные
2
Входные данные
2 2 0
Выходные данные
4
Входные данные
1 1 1
Выходные данные
0
Примечание

В первом примере красивыми являются строки «01», «10».

Во втором примере красивыми являются строки «0011», «1001», «1010», «1100».

В третьем примере красивых строк нет.