Tranh Hang Động

Cho một lưới ô vuông $N\times M$, trong đó mỗi ô có thể là đá (#) hoặc trống (.). Toàn bộ viền ngoài của lưới đều là đá. Một bức tranh hợp lệ là cách tô màu một số ô trống thành nước, sao cho thỏa mãn điều kiện sau:

Nếu ô $a$ là nước, và tồn tại đường đi từ $a$ đến $b$ chỉ qua các ô trống hoặc nước không cao hơn $a$ (liền kề theo cạnh), thì $b$ cũng phải là nước.

(Ô ở hàng $i$ có "độ cao" bằng $N-i$, tức là hàng dưới cùng là thấp nhất.)

Đếm số bức tranh hợp lệ modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: $N$ và $M$ ($1\le N,M\le 1000$).
• $N$ dòng tiếp theo: mỗi dòng gồm $M$ ký tự . hoặc #.

Dữ liệu ra

Một số nguyên duy nhất — số bức tranh hợp lệ modulo ${10}^9+7$.

Ví dụ