Задача 101. Лягушка-попрыгун

Автор:Михалев Ю.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:1  

Условие

Лягушка попала в пруд с кувшинками, который можно представить в виде сетки N на M (в узлах сетки находятся кувшинки). Теперь она хочет попасть с нижнего левого угла пруда в верхний правый, прыгая только по кувшинкам.

Сама лягушка может прыгать только одним из следующих способов:

1. Прыгнуть на 2 клетки вверх

2. Прыгнуть на 2 клетки вправо

3. Прыгнуть на 1 клетку по-диагонали

Лягушка не может выходить за границы сетки

Требуется найти, сколькими способами лягушка может попасть из нижнего левого угла пруда в верхний правый. Ответ взять по модулю 1000000007.

Формат входных данных

Входные данные состоят из двух чисел, записанных через пробел: N и M

Формат выходных данных

Выходные данные должны содержать только одно число - количество способов добраться из нижнего левого угла в верхний правый, взятое по модулю 1000000007

Ограничения

2 ≤ N ≤ 103

2 ≤ M ≤ 103

Примеры тестов

Стандартный вход Стандартный выход
1
3 3
3
2
5 2
0
3
4 4
7

0.083s 0.010s 15