← 返回题目列表

Codeforces · 314/E

E. 塞雷贾和广场

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

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