Поликарп — директор магазина в столице Берляндии. Недавно уровень преступности в столице возрос, поэтому Поликарп озаботился охраной склада своего магазина.
Склад можно представить как матрицу из n строк и m столбцов. Каждый элемент матрицы — либо . (пустая клетка), либо x (стена).
Поликарп хочет нанять некоторое количество охранников (возможно, ни одного) на склад. Каждый охранник будет стоять в какой-то клетке и наблюдать за клетками справа и снизу от него (до ближайшей стены). Формально, если охранник стоит в клетке (x0, y0), то он охраняет клетку (x1, y1), если выполняются все следующие условия:
- (x1, y1) — пустая клетка;
- либо x0 = x1 и y0 ≤ y1, либо x0 ≤ x1 и y0 = y1;
- между клетками (x0, y0) и (x1, y1) нет стен. Между этими клетками могут быть охранники, т. е. охранники могут "смотреть" друг сквозь друга.
Охранники могут стоять только в пустых клетках (и охранять только пустые клетки). План охраны — некоторое множество клеток, в которых должны стоять охранники (естественно, два плана различны, если существует клетка, которая присутствует только в одном из планов). Поликарп называет план подходящим, если существует не более чем одна пустая клетка, которую никто не охраняет.
Поликарп хочет узнать количество подходящих планов. Так как оно может быть очень большим, выведите его по модулю 109 + 7.
Примечание
В первом примере есть три возможных плана: один охранник в клетке (1, 1), один охранник в клетке (1, 3), и два охранника в обеих клетках.