H問題 - Reft and Light

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

Cさんは座標\((0,0)\)にいます。 その後、CさんはL、R、U 、D のみからなる長さ\(N\)の文字列\(T\)であらわされる手順に沿って、グリッド上を\(N\)回移動しようとしました。

\(i=1,2,\cdots ,N\)について、\(T\)の\(i\)文字目の文字\(T_i\)は\(i\)回目の移動の内容を表します。移動の内容は以下のように決定されます。

• Lのとき、左に 1マス移動したことを表す。すなわち、移動前のマスを\((i,j)\)とするとき、移動後のマスは\((i,j-1)\)である。
• Rのとき、右に1マス移動したことを表す。すなわち、移動前のマスを\((i,j)\)とするとき、移動後のマスは\((i,j+1)\)である。
• Uのとき、上に1マス移動したことを表す。すなわち、移動前のマスを\((i,j)\)とするとき、移動後のマスは\((i-1,j)\)である。
• Dのとき、下に1マス移動したことを表す。すなわち、移動前のマスを\((i,j)\)とするとき、移動後のマスは\((i+1,j)\)である。

しかしCさんは方向音痴なうえ英弱なので\(L\)と\(R\)を一定の確率\(\frac{A}{B}\)で間違えます。

Cさんが移動した後、本来の手順通りに移動したときの目的地にいる確率\(r\)は必ず有理数であらわされるので、それを\(\bmod {127237991}\)で求めてください。(\({127237991}\)は素数です。)

「確率を\(\bmod {127237991}\)で求める」とは求める確率\(r\)が既約分数\(\frac{X}{Y}\)であらわされるとき、\(YZ \equiv X \space \pmod {127237991}\)を満たす\(0\)以上\({127237991}-1\)以下の整数\(Z\)が一意に定まるので、それを求めるということです。

制約

• \(0 \leq N \leq 2 \times 10^5\)
• \(0 \leq A \leq B < 127237991\)
• \(B \neq 0\)
• 入力はすべて整数である。

入力

N A B
T

出力

r

確率\(r\)を\(\bmod {127237991}\)で求めて出力せよ。

入力例1

4 1 2
UULR

出力例1

63618996

Cさんの移動した経路がUULR、またはUURLのとき、本来の目的地にいます。 確率は\(\frac{1}{2}\)で、それを\(\bmod {127237991}\)で求めると\(63618996\)となりこれを出力します。

入力例2

4 1 1
UDLL

出力例2

0

左右を逆だと思っているCさんも存在します。