Медведь Василий любит красивые строки. Будем называть строку s красивой, если выполнены следующие условия:
- Строка s состоит только из символов 0 и 1, причем символ 0 должен встречаться в строке s ровно n раз, а символ 1 — ровно m раз.
- За некоторое (возможно нулевое) количество модификаций из строки s можно получить любимый символ g, который равен либо нулю, либо единице.
Модификацией строки, длина которой не меньше двух, будем называть следующую операцию: из строки удаляются два последних символа, а на их место ставится ровно один другой символ, который будет равен единице, если оба удаленных символа были равны нулю, и нулю иначе. Например, в результате одной модификации из строки «01010» получится строка «0100», в результате двух — «011». Применять модификацию к строке длины меньше чем два запрещено.
Помогите Медведю, посчитайте количество красивых строк. Так как количество красивых строк может быть очень большим, выведите остаток от деления этого количества на 1000000007 (109 + 7).
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
Примечание
В первом примере красивыми являются строки «01», «10».
Во втором примере красивыми являются строки «0011», «1001», «1010», «1100».
В третьем примере красивых строк нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 0
|
2
|
|
2
|
2 2 0
|
4
|
|
3
|
1 1 1
|
0
|