問題文

今年も夏祭りが始まります！
夏祭りの開始は，太鼓の音で知らされることが伝統で決まっています．
夏祭り開始の太鼓の鳴らし方は，「最初に何回か面を打つ( D で表します)をしたあと，何回か縁を打つ( K で表します)をする」と決まっています．つまり，太鼓の鳴らし方は DDDD...DKKK...K のような文字列で表されます．
一回も面を打たなかったり，一回も縁を打たなかったりすることもあります．

今年は太鼓の名人であるMMNMMさんが太鼓を鳴らす役に抜擢されました．
MMNMMさんは本番で間違えないように太鼓の鳴らし方を紙に書いておきましたが，うっかり者のMMNMMさんは太鼓の鳴らし方を書いた紙をばらばらにして無くしてしまいました．
必死に紙を探して文字列を復旧しましたが，抜けがあったり，間違いがあるかもしれません．
MMNMMさんは復旧した文字列の中で抜けているところにとりあえず ? を入れておくことにしました．

復旧された紙の情報が長さ N の文字列 S として与えられます．
S と合致する，もともとの太鼓の鳴らし方として考えられるものは何通りあるか求めてください．

制約

すべてのテストケースは以下の制約を満たします．

• 1 \leq N \leq 100
• S の各文字は D または K または ?

入力例 1

10
D??D?K??K?

出力例 1

2

DDDDKKKKKK と DDDDDKKKKK の2通りがありえる鳴らし方で、それ以外の鳴らし方は D??D?K??K? に合致しません。

入力例 2

4
?KD?

出力例 2

0

どのような鳴らし方も、 D を鳴らした後 K を鳴らすので、この文字列に合致する鳴らし方はありません。