配点 : 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 ,因此没有与该字符串匹配的声音。