問題文

整数 N, K, P および，文字 A, B からなる長さ N の文字列 S が与えられる．各 k = 1, 2, \ldots, K に対して以下の問に答えよ (各 k に関する問は別々に考えよ)．

くろうさとしろうさが問題の速解き競争を行う．問題は 1 問ずつ出題され，i 問目 (i = 1, 2, \ldots) は以下のようになる：

• i \le N かつ S の i 文字目が A である場合，確率 \frac{P}{100} でくろうさが先に解き，確率 1 - \frac{P}{100} でしろうさが先に解く．
• i \le N かつ S の i 文字目が B である場合，確率 1 - \frac{P}{100} でくろうさが先に解き，確率 \frac{P}{100} でしろうさが先に解く．
• i > N の場合，確率 \frac{1}{2} でくろうさが先に解き，確率 \frac{1}{2} でしろうさが先に解く．

「i 問目をくろうさが先に解く」という事象たちは互いに独立である．

「先に解いた問題」が k 問に到達したうさぎが現れた時点で競争を終了し，そのうさぎの優勝とする．くろうさが優勝する確率と \frac{1}{2} の大小を比較せよ．

制約

• 1 \le N \le 10^5．
• 1 \le K \le 10^5．
• 0 \le P \le 100．
• S は A, B からなる長さ N の文字列である．

入力例 1

2 2 25
AB

出力例 1

-0

k = 1 のとき，1 問目をくろうさが先に解く確率は \frac{1}{4} なので，くろうさが優勝する確率は \frac{1}{4} である．

k = 2 のとき，

• 1 問目をくろうさが先に解き，2 問目をくろうさが先に解く確率は \frac{3}{16}
• 1 問目をくろうさが先に解き，2 問目をしろうさが先に解き，3 問目をくろうさが先に解く確率は \frac{1}{32}
• 1 問目をしろうさが先に解き，2 問目をくろうさが先に解き，3 問目をくろうさが先に解く確率は \frac{9}{32}

なので，くろうさが優勝する確率は \frac{1}{2} である．

入力例 2

10 4 99
AABBBAABBB

出力例 2

++-+