CF845F Guards In The Storehouse

Polycarp owns a shop in the capital of Berland. Recently the criminal activity in the capital increased, so Polycarp is thinking about establishing some better security in the storehouse of his shop. The storehouse can be represented as a matrix with $ n $ rows and $ m $ columns. Each element of the matrix is either . (an empty space) or x (a wall). Polycarp wants to hire some guards (possibly zero) to watch for the storehouse. Each guard will be in some cell of matrix and will protect every cell to the right of his own cell and every cell to the bottom of his own cell, until the nearest wall. More formally, if the guard is standing in the cell $ (x_{0},y_{0}) $ , then he protects cell $ (x_{1},y_{1}) $ if all these conditions are met: - $ (x_{1},y_{1}) $ is an empty cell; - either $ x_{0}=x_{1} $ and $ y_{0}

The first line contains two numbers $ n $ and $ m $ — the length and the width of the storehouse ( $ 1

Output the number of suitable plans modulo $ 10^{9}+7 $ .

In the first example you have to put at least one guard, so there are three possible arrangements: one guard in the cell $ (1,1) $ , one guard in the cell $ (1,3) $ , and two guards in both these cells.