Escaping the Garden

The dictator has divided his garden into an \(n\times m\) grid. In each cell a marker is placed that points in one of the four directions: left (L), right (R), up (U) or down (D). When the dictator starts at any cell, he will follow the arrow in that cell and move to the adjacent cell in that direction. If the arrow points outside the grid then he leaves the garden. Some cells have already been assigned a fixed arrow (L, R, U or D) while others are undecided, marked as .. The task is to replace every . by one of the four directions so that, no matter which cell the dictator starts in, he will eventually leave the garden.

In other words, if we view the grid as a directed graph (each cell points to one adjacent cell according to its arrow, or to nowhere if the arrow leads out of bounds), then for every starting cell the following process must eventually take you outside the grid – in particular, there must be no cycle in the graph.

Calculate the number of ways to replace each . with a letter from {L,R,U,D} so that the condition holds. Since the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 1000)\), denoting the number of rows and columns of the garden.

The following \(n\) lines each contain a string of length \(m\), consisting of the characters L, R, U, D and .. Here, . denotes an undecided cell, which can be replaced by any of the four directions.

outputFormat

Output one integer – the number of valid replacement assignments modulo \(10^9+7\).

sample

1 1
.

4