← 返回题目列表

AtCoder · summerfes2018_b

B. 太鼓专家

中文机器翻译题面 查看原题

配点 : 100 点

問題文

今年夏日祭又要开始了!
传统上,夏季节日的开始是通过鼓声来表示的。
夏祭开始时打鼓的方式是先敲几次鼓。 D ),然后击中边缘几次( K )。换句话说,鼓的演奏方式是 它由诸如 DDDD...DKKK...K 之类的字符串表示。
有时你甚至一次都没有击中面部,或者一次也没有击中边缘。

今年太鼓大师MMNMM先生被选为太鼓演奏者。
MMNMM先生把打鼓的说明写在一张纸上,以免实际演奏时出错,但粗心的MMNMM把写有打鼓说明的纸弄碎了,丢了。
我拼命寻找纸张来恢复字符串,但可能会有遗漏或错误。
MMNMM先生,请更正恢复字符串中缺失的部分。 我决定包括 ? 。

恢复的纸张信息长度为 它被给出为 N 的字符串 S 。 找出与
S 匹配的鼓演奏可能的原始方法的数量。

制約

所有测试用例都满足以下约束。

  • 1 \leq N \leq 100
  • S 的字符输出 D 或 至少 K 或 至少 ?

入力

输入是按以下格式从标准输入给出的。

N
S
  • 第一行包含一个整数 写入 N 。这是一个字符串 S 的长度是 N 。
  • 第二行包含字符串 S 。这意味着恢复的纸张信息是一个字符串 S 。

出力

在标准输出的一行上输出一个整数,表示演奏鼓的可能的原始方式的数量。


入力例 1

10
D??D?K??K?

出力例 1

2

DDDDKKKKKK 和 按字典顺序比较 DDDDDKKKKK 是两种可能的发声方式,其他方式是 与 D??D?K??K? 不匹配。


入力例 2

4
?KD?

出力例 2

0

无论你怎么玩, 响铃后 D 响铃后 K ,因此没有与该字符串匹配的声音。