F. Шинэ жил ба Цэвэрлэгээ

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лимак бол бяцхан цагаан баавгай. Түүний эцэг эх түүнд Шинэ жилийн өмнөх өдрөөс өмнө гэрээ цэвэрлээрэй гэж хэлсэн. Тэдний гэр $h$ мөр $w$ баганатай тэгш өнцөгт хүснэгт. Нүд бүр хоосон квадрат байна.

Тэр бяцхан учир гэрээ өөрөө цэвэрлэж чадахгүй. Үүний оронд тэр цэвэрлэгч робот ашиглана.

Цэвэрлэгч робот $n$ урттай тэмдэгт мөрөөр тодорхойлогдох $n$ хөдөлгөөний хэвээр ажиллана. Нэг хөдөлгөөн (тэмдэгт) роботыг дөрвөн хөрш нүдний нэгрүү нь хөдөлгөнө. Тэмдэгт бүр дараах дөрвөн тэмдэгтийн нэг байна: '$U$' (дээш), '$D$' (доош), '$L$' (зүүн), '$R$' (баруун). Нэг хөдөлгөөн хийхэд нэг минут болно.

Цэвэрлэгч робот нэг нүдэнд байрлаж тэндээсээ ажиллаж эхлэнэ. Тэгээд хана (байшингийн дөрвөн хананы нэгийг) мөргөх хүртлээ хөдөлгөөнүүдийн хэвээ давтана. Ханыг мөргөсний дараа роботыг дахин байрлуулж болох ба дахин ажиллаж эхэлнэ.

Лимак цэвэрлэгч роботыг нэг нүдэнд байрлуулах нь хангалттай байна гэдэгт итгэлгүй байна. Ингээд тэр $w*h$ удаа ажиллуулах буюу нүд бүр дээр нэг удаа байрлуулан ажиллуулахаар болсон. Магадгүй зарим нүднүүд нэгээс олон удаа цэвэрлэгдэж болох боловч энэ хэнд хамаатай гэж?

Лимак таниас нэг асуулт асууж байна. Робот байшинг цэвэрлэхийн тулд хэр их цаг зарцуулах вэ? Минутын тоог илэрхийлэх тоог олоод $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ. Цэвэрлэгч робот хэзээ ч зогсохгүй байж болно ийм тохиолдолд "$-1$"-г (хашилтгүйгээр) хэвлэ.

Роботыг байрлуулах болон ажиллуулж эхлэхэд цаг зарцуулахгүй боловч та робот ханыг мөргөх үеийн хөдөлгөөнийг тоолох ёстой. Илүү сайн ойлгохын тулд жишээнүүдийг харна уу.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $h$ ба $w$ ($1 ≤ n, h, w ≤ 500 000$) байх ба харгалзан хэвийн урт, мөрүүдийн тоо болон багануудын тоо байна.

Хоёр дахь мөрөнд $n$ урттай тэмдэгт мөр байх буюу $n$ хөдөлгөөний хэв байна. Тэмдэгт бүр '$U$', '$D$', '$L$' эсвэл '$R$' том үсгүүдийн аль нэг нь байна.

Гаралт

Хариултыг нэг мөрөнд хэвлэ.

Хэрвээ цэвэрлэгч робот хэзээ ч зогсохгүй бол "$-1$"-г (хашилтгүйгээр) хэвлэ. Бусад тохиолдолд байшинг цэвэрлэхэд шаардагдах минутын тоог $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
1 10 2
R
Гаралт
30
Оролт
3 4 6
RUL
Гаралт
134
Оролт
4 1 500000
RLRL
Гаралт
-1

Тэмдэглэл

Эхний жишээн дээр байшин $10$ мөр $2$ баганатай хүснэгт байна. Роботыг хоёр дахь баганын хаанаас ч эхлүүлсэн нэг л хөдөлгөөн (ингээд нэг минут зарцуулна) хийгээд хана мөргөх ба робот баруун тийшээ явахыг оролдох боловч баруун талд ямар ч багана байхгүй. Роботыг эхний баганын хаанаас ч эхлүүлсэн хоёр хөдөлгөөн л хийнэ. Шаардагдах нийт минутын тоо $10*1 + 10*2 = 30$ байна.

Хоёр дахь жишээн дээр ажиллаж эхэлсэн робот "$RULRULRULR...$" хөдөлгөөн хийхийг оролдоно. Хоёрдугаар мөрийн хамгийн зүүн талын нүдний хувьд робот дээд ханыг мөргөж зогсохоосоо өмнө $5$ хөдөлгөөн хийнэ.

Сэтгэгдлүүдийг ачааллаж байна...