ICPC Central K

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1800 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nguồn: ICPC Central 2021

Participants are given a maze which is a map of size \(h \times w\), which contain cells denoted by one of the following symbols:

#: Obstacle cell.
+: From this cell, the car can move to the adjacent square (Left, Right, Up, Down).
L: From this cell, the car can only move left.
R: From this cell, the car can only move right.
U: From this cell, the car can only move up.
D: From this cell, the car can only move down.

Each time unit, the car moves \(1\) cell according to the symbol of the map. Mr. Tuan wants to know how many valid ways to move in all the time \(t\) allows (starting from any position). Note that, car hitting an obstacle or leaving the map are considered illegal and do not count as a valid way.

Input

The first line contains \(3\) natural numbers \(h, w\) and \(t\).
Next \(h\) lines contains the symbols of maze.

Constraints

\(1 \le h \cdot w \le 100\)
\(1 \le t \le 10^9\)

Output

Print the number of valid way. Since result may be too big, print it after taking modulo \(10^9 + 7\).

Example

Test 1

Input

2 2 10
RD
UL

Output

Note

Explanation Example 1: From any coordinate, there is one valid move. So there are \(4\) ways in total.

Test 2

Input

3 3 2
RD#
U+#
#LR

Output

Note

Explanation Example 2: From coordinates \((1,1)\) there is one valid way to move, RD. From coordinates \((1,2)\) there are \(3\) valid ways to move: DU, DL, DR. From coordinates \((2,1)\) there is \(1\) way UR. From coordinates \((2,2)\) there are \(2\) ways: UD, LU. The other coordinates with no valid way of moving. So there are \(7\) ways in total.

Bình luận

Tải bình luận...

Không có bình luận nào.