Девочка Маша очень любит зимние виды спорта, и сегодня ей предстоит пройти лыжный слалом.
Трасса схематически представляет из себя клетчатый прямоугольник n × m. На поле размещены прямоугольные препятствия, занимающие некоторые клетки. Маша должна добраться из клетки с координатами (1, 1), в клетку (n, m). При этом из каждой клетки можно перейти либо на одну клетку вверх, либо на одну клетку вправо. В клетки, в которых расположены препятствия, попадать нельзя.
Таким образом, каждое препятствие можно обойти двумя способами: оно останется либо слева от траектории движения по трассе, либо справа. Маша любит разнообразие, и ей интересно, сколько существует различных способов пройти трассу. Проходы трассы считаются различными, если существует хотя бы одно препятствие, которое в одном проходе находится слева, а в другом справа от траектории Маши.
Ваша задача — помочь Маше узнать количество различных способов пройти трассу. Ответ может быть большим и Машу устроит значение по модулю 109 + 7.
На рисунках ниже разобраны тесты из условия. 
