Around the Board, Around the Board...
Limits: 3 sec., 512 MiB
Volodymyr is a high school programmer who likes challenges. Regular school olympiads are too easy for him so he prefers university contests. In one such contest he was struggling to solve a problem which he will remember until the end of his days. After a while he decided to upsolve that problem. Brainstorming ideas and approaches for the whole evening he didn’t make any progress so he decided to take a break and play his favorite game called the snake. The rules of the game are described in the next paragraph.
Given even-sided board with height \(n\) and width \(m\). You start in a cell with coordinates \((x,y)\). Your initial length is 1. There is one fruit somewhere on the board. Each time you reach a cell with fruit, your tail increases by \(1\) instantly and a new fruit appears in a random free cell. When there are no free cells, which means that you ate \(n \cdot m-1\) fruits, you win the game. You lose the game when you collide with your body or borders.
Volodymyr had a hard time winning the game. After a while, he decided to surf the internet for guides. Who doesn’t surf the internet for solutions? He found a topic that suggested him to follow a cycle that will cover all cells and visit each exactly once. Fortunately, the grid was even-sided so the mentioned cycle would always exist. Even more, our hero already generated one for himself so you don’t have to worry about it.
Given starting position \((x,y)\) and cycle’s instructions, he noticed that sometimes he has to navigate through half of the board to reach the next fruit. Also, the time to win the game can vary a lot. Thinking about this he asked himself a question: what is the expected number of times the snake visits its starting position \((x,y)\)? After hours of figuring this out, he realized that the same question is asked in the problem he was solving. At this point it should be clear what it is all about, so, given all the information above, find the expected number of times a snake will visit its starting cell.
Input
First line contains four integers \(n\), \(m\), \(x\) and \(y\) – height and width of the board and snake’s position at the start of the game.
Next \(n\) lines contains \(m\) characters each. Each of them is
L
, R
, U
, or D
, which
stands for four cardinal directions (Left, Right, Up, and Down).
Charecter \(c_{ij}\) informs you where
to go from cell \((i,j)\). Instructions
form a correct cycle that covers the whole grid.
Output
Let the resulting expected value be represented as an irreducible fraction \(\frac{P}{Q}\).
Print \(P \cdot Q^{-1} \bmod 998244353\), where \(Q^{-1}\) is the inverse element of \(Q\) modulo \(998244353\) (such integer that \(Q \cdot Q^{-1}\) has remainder \(1\) modulo \(998244353\)).
Constraints
\(2 \le n, m \le 100\), \(n\) and \(m\) are even,
\(1 \le x \le n\),
\(1 \le y \le m\).
Samples
Input (stdin) | Output (stdout) |
---|---|
2 2 1 1 RD UL | 831870296 |
Input (stdin) | Output (stdout) |
---|---|
8 10 2 5 DLLLLLLLLL RRRRRDRDRU DLLDLLUDUL DRURRRUDRU DUDLLLLLUL DURRRRRDRU DULLLLLLUL RRRRRRRRRU | 357756310 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|