Sereja 在平面上画了 n 个点,编号为 i (1 ≤ i ≤ n) 的点的坐标为 (i, 0)。然后Sereja 用一个或大或小的英文字母标记每个点。 Sereja 不喜欢字母“x”,所以他没有用它来标记点。 Sereja 认为,如果满足以下条件,则这些点标记得很漂亮:
- 所有点都可以分成对,这样每个点都属于一对;
- 每对中横坐标较小的点将标有小英文字母,横坐标较大的点将标有相同的大英文字母;
- 如果我们在每一对上构建一个正方形,则该对的点将是正方形的相对点,它们之间的线段将是正方形的对角线,那么在生成的正方形中将不会有任何相交或接触的正方形。
小 Petya 擦掉了标记点的一些小字母和所有大字母。现在,Sereja 想知道有多少种方法可以返回删除的字母,以便将点标记得漂亮。
输入
第一行包含整数 n 点数 (1 ≤ n ≤ 105)。第二行包含一个由 n 个小英文字母和问号组成的序列 - 字母序列,用于标记点,按照点的 x 坐标递增的顺序。问号表示没有字母的点(Petya 删除了它们)。保证输入字符串不包含字母“x”。
输出
在一行中打印对 4294967296 取模的问题的答案。如果无法返回删除的字母,则打印数字 0。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 a???
输出 #1
50
输入 #2
4 abc?
输出 #2
0
输入 #3
6 abc???
输出 #3
1