Змійка

Обмеження: 3 сек., 512 МіБ

Володимир — школяр-програміст, який любить розв’язувати складні задачі. Звичайні шкільні олімпіади для нього занадто прості, тому він надає перевагу університетським змаганням. На одному з таких змагань він не розв’язав задачу, яку пам’ятатиме до кінця своїх днів. Попри невдачу під час змагань, він вирішив доздати задачу. Після невдалого мозкового штурму ідей він захотів відпочити й пограти в його улюблену гру «Змійка». Правила гри описані в наступному абзаці.

Дано поле парних розмірів довжиною \(n\) та шириною \(m\). Ви починаєте в клітинці \((x, y)\). Ваша початкова довжина — 1. Десь посеред дошки є фрукт. Щоразу коли ви опиняєтесь у клітинці з фруктом, ваш хвіст миттєво росте на 1 і новий фрукт з’являється у випадковій вільній клітинці. Коли більше не існує вільних клітинок, що означає те, що ви з’їли \(n \cdot m-1\) фруктів, ви перемагаєте. Ви програєте, коли стикаєтесь із межами поля або своїм тілом.

Володимиру ніяк не вдавалося перемогти. Через деякий час він наважився пошукати поради в інтернеті. Хто ж не шукає розв’язки в інтернеті? Він знайшов на форумі тему, у якій пропонували рухатися циклом по полю так, щоб відвідати всі клітинки рівно один раз. На щастя, поле має сторони парної довжини, отже такий цикл завжди існує. Ба більше, наш герой уже згенерував собі такий цикл, тож ви не повинні про це турбуватись.

Маючи стартову позицію \((x, y)\) та інструкції циклу, він помітив, що інколи йому потрібно обійти половину дошки, щоб дістатися до наступного фрукта. Також час, потрібний для перемоги, може сильно відрізнятись у залежності від позицій фруктів. Думаючи про це, він поставив перед собою запитання: яка ж очікувана кількість відвідувань початкової клітинки \((x, y)\)? Після дуже довгих роздумів, він зрозумів, що це питання — перефразована задача, яку він розв’язував під час університетських змагань. Думаю, в цей момент усе повинно стати на свої місця.

Отже, маючи інформацію наведену вище, знайдіть очікувану кількість відвідувань початкової клітинки.

Вхідні дані

Перший рядок містить чотири цілих числа \(n\), \(m\), \(x\) і \(y\) — висоту й ширину поля та позицію змійки на початку гри.

Наступні \(n\) рядків містять \(m\) символів, кожен із яких — це L, R, U або D, що відповідає за чотири напрямки руху (ліворуч, праворуч, угору й униз). Символ \(c_{ij}\) каже вам, куди піти з клітинки \((i, j)\). Інструкції утворюють коректний цикл, який повністю покриває поле.

Вихідні дані

Відповідь до задачі може бути представлена як нескоротний дріб \(\frac{p}{q}\).

Виведіть \(p \cdot q^{-1} \bmod 998244353\), де \(q^{-1}\) обернений елемент до \(q\) за модулем простого числа 998244353 (таке число, що \(q \cdot q^{-1}\) має остачу 1 за модулем 998244353).

Обмеження

\(2 \le n, m \le 100\),

\(n\) і \(m\) парні,

\(1 \le x \le n\),

\(1 \le y \le m\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 2 1 1 RD UL	831870296

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
8 10 2 5 DLLLLLLLLL RRRRRDRDRU DLLDLLUDUL DRURRRUDRU DUDLLLLLUL DURRRRRDRU DULLLLLLUL RRRRRRRRRU	357756310