Famine

Time limit2sMemory limit1024 MB

Summary

Count the ways to mark each cell of an n by m grid as starving or fed, respecting fixed cells, so every 2x2 square has two of each, modulo 1e9+7.

Level: Medium6 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Statement

And when he had opened the third seal, I heard the third beast say, Come and see.

And I beheld, and lo a black horse; and he that sat on him had a pair of balances in his hand.

And I heard a voice in the midst of the four beasts say, A measure of wheat for a penny, and three measures of barley for a penny; and see thou hurt not the oil and the wine.

Revelation of John the Divine

The end of the world is near, yet Famine, the Third Horseman of the Apocalypse, still cannot tell which cities deserve punishment and which do not. He decided to practice on one small country first.

The country is a grid of $n \times m$ cells, and each cell is one city. Famine can either afflict a city with famine or spare it. Some cities have enough food to last until the next end of the world, so Famine cannot make them starve. Other cities never had any food, so they starve no matter what.

The judgment must be fair. In every $2 \times 2$ square, the number of starving cities must equal the number of fed cities. Count the different ways to split the cities of this country into starving and fed cities.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 10^{3}$ ), the size of the country. Each of the next $n$ lines contains $m$ characters. A '+' means the city cannot starve, a '-' means the city starves no matter what, and a '.' means Famine may choose either way for that city.

Output

Print the number of different ways to afflict the country with famine, modulo $10^{9} + 7$ .

Examples1

Example 1
Input
```
3 2
+.
..
.-
```
Expected output
```
2
```